{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T22:38:03Z","timestamp":1778279883035,"version":"3.51.4"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2023,12,15]],"date-time":"2023-12-15T00:00:00Z","timestamp":1702598400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,12,15]],"date-time":"2023-12-15T00:00:00Z","timestamp":1702598400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100018542","name":"Sichuan Natural Science Foundation","doi-asserted-by":"crossref","award":["2023NSFSC0059"],"award-info":[{"award-number":["2023NSFSC0059"]}],"id":[{"id":"10.13039\/501100018542","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62372095"],"award-info":[{"award-number":["62372095"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2024,5]]},"DOI":"10.1007\/s00453-023-01197-x","type":"journal-article","created":{"date-parts":[[2023,12,15]],"date-time":"2023-12-15T12:01:51Z","timestamp":1702641711000},"page":"1293-1334","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Maximum Weighted Independent Set: Effective Reductions and Fast Algorithms on Sparse Graphs"],"prefix":"10.1007","volume":"86","author":[{"given":"Mingyu","family":"Xiao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sen","family":"Huang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaoyu","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,12,15]]},"reference":[{"key":"1197_CR1","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/j.tcs.2015.09.023","volume":"609","author":"T Akiba","year":"2016","unstructured":"Akiba, T., Iwata, Y.: Branch-and-reduce exponential\/FPT algorithms in practice: a case study of vertex cover. Theoret. Comput. Sci. 609, 211\u2013225 (2016)","journal-title":"Theoret. Comput. Sci."},{"issue":"5","key":"1197_CR2","doi-asserted-by":"publisher","first-page":"773","DOI":"10.1109\/TVCG.2006.136","volume":"12","author":"K Been","year":"2006","unstructured":"Been, K., Daiches, E., Yap, C.K.: Dynamic map labeling. IEEE Trans. Vis. Comput. Graph. 12(5), 773\u2013780 (2006)","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"key":"1197_CR3","unstructured":"Beigel, R.: Finding maximum independent sets in sparse and general graphs. In: Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 856\u2013857 (1999)"},{"issue":"1","key":"1197_CR4","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1007\/s00453-010-9460-7","volume":"62","author":"N Bourgeois","year":"2012","unstructured":"Bourgeois, N., Escoffier, B., Paschos, V.T., van Rooij, J.M.M.: Fast algorithms for max independent set. Algorithmica 62(1), 382\u2013415 (2012)","journal-title":"Algorithmica"},{"key":"1197_CR5","doi-asserted-by":"crossref","unstructured":"Bourgeois, N., Escoffier, B., Paschos, V.T.: An O*(1.0977$${}^{\\text{n}}$$) exact algorithm for max independent set in sparse graphs. In: Parameterized and Exact Computation, pp. 55\u201365 (2008)","DOI":"10.1007\/978-3-540-79723-4_7"},{"issue":"2","key":"1197_CR6","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1006\/jagm.2001.1186","volume":"41","author":"J Chen","year":"2001","unstructured":"Chen, J., Kanj, I.A., Jia, W.: Vertex cover: further observations and further improvements. J. Algorithms 41(2), 280\u2013301 (2001)","journal-title":"J. Algorithms"},{"issue":"4","key":"1197_CR7","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s00453-004-1145-7","volume":"43","author":"J Chen","year":"2005","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Labeled search trees and amortized analysis: improved upper bounds for NP-hard problems. Algorithmica 43(4), 245\u2013273 (2005)","journal-title":"Algorithmica"},{"key":"1197_CR8","unstructured":"Dahll\u00f6f, V., Jonsson, P.: An algorithm for counting maximum weighted independent sets and its applications. In: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 292\u2013298 (2002)"},{"issue":"1\u20133","key":"1197_CR9","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/j.tcs.2004.10.037","volume":"332","author":"V Dahll\u00f6f","year":"2005","unstructured":"Dahll\u00f6f, V., Jonsson, P., Wahlstr\u00f6m, M.: Counting models for 2SAT and 3SAT formulae. Theoret. Comput. Sci. 332(1\u20133), 265\u2013291 (2005)","journal-title":"Theoret. Comput. Sci."},{"key":"1197_CR10","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Gaspers, S., Saurabh, S.: Branching and treewidth based exact algorithms. In: Proceedings of Seventeenth International Symposium on Algorithms and Computation. Lecture Notes in Computer Science, vol. 4288, pp. 16\u201325 (2006)","DOI":"10.1007\/11940128_4"},{"issue":"2","key":"1197_CR11","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/s00453-007-9133-3","volume":"54","author":"FV Fomin","year":"2009","unstructured":"Fomin, F.V., Gaspers, S., Saurabh, S., Stepanov, A.A.: On two techniques of combining branching and treewidth. Algorithmica 54(2), 181\u2013207 (2009)","journal-title":"Algorithmica"},{"issue":"5","key":"1197_CR12","doi-asserted-by":"publisher","first-page":"25:1","DOI":"10.1145\/1552285.1552286","volume":"56","author":"FV Fomin","year":"2009","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: A measure and conquer approach for the analysis of exact algorithms. J. ACM 56(5), 25:1-25:32 (2009)","journal-title":"J. ACM"},{"key":"1197_CR13","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Kratsch, D.: Exact exponential algorithms. In: Texts in Theoretical Computer Science. An EATCS Series. Springer (2010)","DOI":"10.1007\/978-3-642-16533-7"},{"key":"1197_CR14","doi-asserted-by":"crossref","unstructured":"F\u00fcrer, M., Kasiviswanathan, S.P.: Algorithms for counting 2-SAT solutions and colorings with applications. In: Proceedings of Third International Algorithmic on Aspects in Information and Management, pp. 47\u201357 (2007)","DOI":"10.1007\/978-3-540-72870-2_5"},{"key":"1197_CR15","unstructured":"Issac, D., Jaiswal, R.: An O*(1.0821$${}^{{{n}}}$$)-time algorithm for computing maximum independent set in graphs with bounded degree 3. CoRR (2013). arXiv:1308.1351"},{"key":"1197_CR16","doi-asserted-by":"crossref","unstructured":"Jian, T.: An $$O(2^{0.304\\text{ n }}$$) algorithm for solving maximum independent set problem. IEEE Trans. Comput. 35(9), 847\u2013851 (1986)","DOI":"10.1109\/TC.1986.1676847"},{"key":"1197_CR17","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Proceedings of a Symposium on the Complexity of Computer Computations, pp. 85\u2013103. The IBM Research Symposia Series (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"1197_CR18","unstructured":"Kneis, J., Langer, A., Rossmanith, P.: A fine-grained analysis of a simple independent set algorithm. In: Proceedings of IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a04, pp. 287\u2013298 (2009)"},{"key":"1197_CR19","doi-asserted-by":"crossref","unstructured":"Lamm, S., Schulz, C., Strash, D., Williger, R., Zhang, H.: Exactly solving the maximum weight independent set problem on large real-world graphs. In: Proceedings of Algorithm Engineering and Experiments, pp. 144\u2013158 (2019)","DOI":"10.1137\/1.9781611975499.12"},{"key":"1197_CR20","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1016\/j.tcs.2016.06.006","volume":"640","author":"CS Liao","year":"2016","unstructured":"Liao, C.S., Liang, C.W., Poon, S.H.: Approximation algorithms on consistent dynamic map labeling. Theoret. Comput. Sci. 640, 84\u201393 (2016)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"1197_CR21","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1016\/j.dam.2004.02.017","volume":"145","author":"RM McConnell","year":"2005","unstructured":"McConnell, R.M., de Montgolfier, F.: Linear-time modular decomposition of directed graphs. Discrete Appl. Math. 145(2), 198\u2013209 (2005)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"1197_CR22","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/S0196-6774(03)00005-1","volume":"47","author":"R Niedermeier","year":"2003","unstructured":"Niedermeier, R., Rossmanith, P.: On efficient fixed-parameter algorithms for weighted vertex cover. J. Algorithms 47(2), 63\u201377 (2003)","journal-title":"J. Algorithms"},{"issue":"2","key":"1197_CR23","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/j.jda.2008.09.004","volume":"7","author":"I Razgon","year":"2009","unstructured":"Razgon, I.: Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3. J. Discrete Algorithms 7(2), 191\u2013212 (2009)","journal-title":"J. Discrete Algorithms"},{"issue":"3","key":"1197_CR24","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0196-6774(86)90032-5","volume":"7","author":"JM Robson","year":"1986","unstructured":"Robson, J.M.: Algorithms for maximum independent sets. J. Algorithms 7(3), 425\u2013440 (1986)","journal-title":"J. Algorithms"},{"key":"1197_CR25","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/j.jcss.2017.05.003","volume":"89","author":"H Shachnai","year":"2017","unstructured":"Shachnai, H., Zehavi, M.: A multivariate framework for weighted FPT algorithms. J. Comput. Syst. Sci. 89, 157\u2013189 (2017)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"1197_CR26","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1137\/0206038","volume":"6","author":"RE Tarjan","year":"1977","unstructured":"Tarjan, R.E., Trojanowski, A.E.: Finding a maximum independent set. SIAM J. Comput. 6(3), 537\u2013546 (1977)","journal-title":"SIAM J. Comput."},{"key":"1197_CR27","doi-asserted-by":"crossref","unstructured":"Wahlstr\u00f6m, M.: A tighter bound for counting max-weight solutions to 2SAT instances. In: Proceedings of Third International Workshop on Parameterized and Exact Computation. LNCS, vol.\u00a05018, pp. 202\u2013213 (2008)","DOI":"10.1007\/978-3-540-79723-4_19"},{"key":"1197_CR28","doi-asserted-by":"crossref","unstructured":"Xiao, M.: A simple and fast algorithm for maximum independent set in 3-degree graphs. In: WALCOM: Algorithms and Computation, pp. 281\u2013292 (2010)","DOI":"10.1007\/978-3-642-11440-3_26"},{"issue":"2","key":"1197_CR29","first-page":"153","volume":"28","author":"M Xiao","year":"2005","unstructured":"Xiao, M., Chen, J., Han, X.: Improvement on vertex cover and independent set problem for low-degree graphs. Chin. J. Comput. 28(2), 153\u2013160 (2005)","journal-title":"Chin. J. Comput."},{"key":"1197_CR30","doi-asserted-by":"crossref","unstructured":"Xiao, M., Huang, S., Zhou, Y., Ding, B.: Efficient reductions and a fast algorithm of maximum weighted independent set. In: Proceedings of the Web Conference, vol. 2021, pp. 3930\u20133940 (2021)","DOI":"10.1145\/3442381.3450130"},{"issue":"3","key":"1197_CR31","doi-asserted-by":"publisher","first-page":"830","DOI":"10.1007\/s10878-017-0115-3","volume":"34","author":"M Xiao","year":"2017","unstructured":"Xiao, M., Nagamochi, H.: A refined algorithm for maximum independent set in degree-4 graphs. J. Comb. Optim. 34(3), 830\u2013873 (2017)","journal-title":"J. Comb. Optim."},{"key":"1197_CR32","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/j.tcs.2012.09.022","volume":"469","author":"M Xiao","year":"2013","unstructured":"Xiao, M., Nagamochi, H.: Confining sets and avoiding bottleneck cases: a simple maximum independent set algorithm in degree-3 graphs. Theoret. Comput. Sci. 469, 92\u2013104 (2013)","journal-title":"Theoret. Comput. Sci."},{"key":"1197_CR33","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/j.dam.2014.07.009","volume":"199","author":"M Xiao","year":"2016","unstructured":"Xiao, M., Nagamochi, H.: An exact algorithm for maximum independent set in degree-5 graphs. Discrete Appl. Math. 199, 137\u2013155 (2016)","journal-title":"Discrete Appl. Math."},{"key":"1197_CR34","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/j.ic.2017.06.001","volume":"255","author":"M Xiao","year":"2017","unstructured":"Xiao, M., Nagamochi, H.: Exact algorithms for maximum independent set. Inf. Comput. 255, 126\u2013146 (2017)","journal-title":"Inf. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01197-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01197-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01197-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,20]],"date-time":"2024-04-20T23:03:24Z","timestamp":1713654204000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01197-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,15]]},"references-count":34,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,5]]}},"alternative-id":["1197"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01197-x","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-2635021\/v1","asserted-by":"object"}]},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,15]]},"assertion":[{"value":"27 February 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 November 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 December 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}