{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,12]],"date-time":"2025-12-12T13:46:33Z","timestamp":1765547193476,"version":"3.37.3"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2023,12,22]],"date-time":"2023-12-22T00:00:00Z","timestamp":1703203200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,12,22]],"date-time":"2023-12-22T00:00:00Z","timestamp":1703203200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100007219","name":"Natural Science Foundation of Shanghai","doi-asserted-by":"publisher","award":["20ZR1402700"],"award-info":[{"award-number":["20ZR1402700"]}],"id":[{"id":"10.13039\/100007219","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61873337"],"award-info":[{"award-number":["61873337"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Supercomput"],"published-print":{"date-parts":[[2024,5]]},"DOI":"10.1007\/s11227-023-05841-9","type":"journal-article","created":{"date-parts":[[2023,12,22]],"date-time":"2023-12-22T18:01:24Z","timestamp":1703268084000},"page":"10418-10443","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Efficient computation of maximum weighted independent sets on weighted dynamic graph"],"prefix":"10.1007","volume":"80","author":[{"given":"Yuting","family":"Tan","sequence":"first","affiliation":[]},{"given":"Junfeng","family":"Zhou","sequence":"additional","affiliation":[]},{"given":"Xinqi","family":"Rong","sequence":"additional","affiliation":[]},{"given":"Ming","family":"Du","sequence":"additional","affiliation":[]},{"given":"Caiyun","family":"Qi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,12,22]]},"reference":[{"key":"#cr-split#-5841_CR1.1","unstructured":"William B, Sinisa T (2010) Segmentation as Maximum-Weight Independent Set. In: Lafferty J"},{"key":"#cr-split#-5841_CR1.2","unstructured":"(ed) Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010. Proceedings of a Meeting Held 6-9 Dec 2010, Vancouver, British Columbia, Canada, vol 23, pp 307-315"},{"key":"5841_CR2","doi-asserted-by":"publisher","unstructured":"Gemsa A, N\u00f6llenburg M, Rutter I (2014) Evaluation of labeling strategies for rotating maps. In: Gudmundsson J, Katajainen J (eds) Experimental Algorithms, pp 235\u2013246. Springer, Cham. https:\/\/doi.org\/10.1007\/978-3-319-07959-2_20","DOI":"10.1007\/978-3-319-07959-2_20"},{"key":"#cr-split#-5841_CR3.1","doi-asserted-by":"crossref","unstructured":"Chou JC, Kim J, Rotem D (2011) Energy-Aware Scheduling in Disk Storage Systems. In: Lafferty J","DOI":"10.1109\/ICDCS.2011.40"},{"key":"#cr-split#-5841_CR3.2","unstructured":"(ed) 2011 31st International Conference on Distributed Computing Systems, pp 423-433"},{"issue":"4","key":"5841_CR4","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1016\/j.dam.2008.08.027","volume":"157","author":"A Kako","year":"2009","unstructured":"Kako A, Ono T, Hirata T, Halld\u00f3rsson MM (2009) Approximation algorithms for the weighted independent set problem in sparse graphs. Discr Appl Math 157(4):617\u2013626. https:\/\/doi.org\/10.1016\/j.dam.2008.08.027","journal-title":"Discr Appl Math"},{"key":"5841_CR5","doi-asserted-by":"publisher","unstructured":"Chang L, Li W, Zhang W (2017) Computing a Near-Maximum Independent Set in Linear Time by Reducing-Peeling. In: Proceedings of the 2017 ACM International Conference on Management of Data. SIGMOD \u201917, pp 1181\u20131196. Association for Computing Machinery, New York, USA. https:\/\/doi.org\/10.1145\/3035918.3035939","DOI":"10.1145\/3035918.3035939"},{"key":"5841_CR6","doi-asserted-by":"publisher","unstructured":"Gu J, Zheng W, Cai Y, Peng P (2021) Towards Computing a Near-Maximum Weighted Independent Set on Massive Graphs. In: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp 467\u2013477. Association for Computing Machinery, New York, USA. https:\/\/doi.org\/10.1145\/3447548.3467232","DOI":"10.1145\/3447548.3467232"},{"key":"5841_CR7","doi-asserted-by":"publisher","unstructured":"Gao X, Li J, Miao D (2022) Dynamic Approximate Maximum Independent Set on Massive Graphs. In: 38th IEEE International Conference on Data Engineering, ICDE 2022, Kuala Lumpur, Malaysia, May 9-12, 2022, pp 1835\u20131847. https:\/\/doi.org\/10.1109\/ICDE53745.2022.00183","DOI":"10.1109\/ICDE53745.2022.00183"},{"key":"5841_CR8","doi-asserted-by":"publisher","unstructured":"Wang X, Wen D, Zhang W, Zhang Y, Qin L (2023) Distributed Near-Maximum Independent Set Maintenance Over Large-Scale Dynamic Graphs. In: 39th IEEE International Conference on Data Engineering, ICDE 2023, Anaheim, CA, USA, Apr 3-7, 2023, pp 2538\u20132550. https:\/\/doi.org\/10.1109\/ICDE55515.2023.00195","DOI":"10.1109\/ICDE55515.2023.00195"},{"key":"5841_CR9","unstructured":"Warren S, Hicks IV (2007) Combinatorial branch-and-bound for the maximum weight independent set problem. Relat\u00f3rio T\u00e9cnico, Texas A&M University, pp 1\u201323"},{"key":"5841_CR10","doi-asserted-by":"publisher","unstructured":"Lamm S, Schulz C, Strash D, Williger R, Zhang H (2019) Exactly solving the maximum weight independent set problem on large real-world graphs. In: 2019 Proceedings of the Meeting on Algorithm Engineering and Experiments (ALENEX), pp 144\u2013158. https:\/\/doi.org\/10.1137\/1.9781611975499.12","DOI":"10.1137\/1.9781611975499.12"},{"issue":"4","key":"5841_CR11","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1016\/j.orl.2006.07.004","volume":"35","author":"S Butenko","year":"2007","unstructured":"Butenko S, Trukhanov S (2007) Using critical sets to solve the maximum independent set problem. Op Res Lett 35(4):519\u2013524. https:\/\/doi.org\/10.1016\/j.orl.2006.07.004","journal-title":"Op Res Lett"},{"issue":"1","key":"5841_CR12","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/BF02243394","volume":"52","author":"L Babel","year":"1994","unstructured":"Babel L (1994) A fast algorithm for the maximum weight clique problem. Computing 52(1):31\u201338. https:\/\/doi.org\/10.1007\/BF02243394","journal-title":"Computing"},{"issue":"3","key":"5841_CR13","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1007\/s11590-017-1128-7","volume":"12","author":"B Nogueira","year":"2018","unstructured":"Nogueira B, Pinheiro RGS, Subramanian A (2018) A hybrid iterated local search heuristic for the maximum weight independent set problem. Optim Lett 12(3):567\u2013583. https:\/\/doi.org\/10.1007\/s11590-017-1128-7","journal-title":"Optim Lett"},{"issue":"1","key":"5841_CR14","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/BF02832348","volume":"25","author":"SMA Nayeem","year":"2007","unstructured":"Nayeem SMA, Pal M (2007) Genetic algorithmic approach to find the maximum weight independent set of a graph. J Appl Math Comput 25(1):217\u2013229","journal-title":"J Appl Math Comput"},{"issue":"3\u20134","key":"5841_CR15","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1080\/00207169108803967","volume":"38","author":"PM Pardalos","year":"1991","unstructured":"Pardalos PM, Desai N (1991) An algorithm for finding a maximum weighted independent set in an arbitrary graph. Int J Comput Math 38(3\u20134):163\u2013175. https:\/\/doi.org\/10.1080\/00207169108803967","journal-title":"Int J Comput Math"},{"key":"5841_CR16","doi-asserted-by":"publisher","unstructured":"Dahlum J, Lamm S, Sanders P, Schulz C, Strash D, Werneck RF (2016) Accelerating local search for the maximum independent set problem. In: Goldberg AV, Kulikov AS (eds) Experimental Algorithms-15th International Symposium, SEA 2016, St. Petersburg, Russia, Jun 5-8, 2016, Proceedings, vol 9685, pp 118\u2013133. https:\/\/doi.org\/10.1007\/978-3-319-38851-9_9","DOI":"10.1007\/978-3-319-38851-9_9"},{"key":"5841_CR17","doi-asserted-by":"publisher","unstructured":"Zheng W, Gu J, Peng P, Yu JX (2020) Efficient Weighted Independent Set Computation Over Large Graphs. In: 2020 IEEE 36th International Conference on Data Engineering (ICDE), pp 1970\u20131973. https:\/\/doi.org\/10.1109\/ICDE48307.2020.00216","DOI":"10.1109\/ICDE48307.2020.00216"},{"key":"5841_CR18","doi-asserted-by":"publisher","unstructured":"Hespe D, Schulz C, Strash D (2018) Scalable kernelization for maximum independent sets. In: Pagh R, Venkatasubramanian S (eds) Proceedings of the Twentieth Workshop on Algorithm Engineering and Experiments, ALENEX 2018, New Orleans, LA, USA, Jan 7-8, 2018, pp 223\u2013237. https:\/\/doi.org\/10.1137\/1.9781611975055.19","DOI":"10.1137\/1.9781611975055.19"},{"issue":"4","key":"5841_CR19","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/s10732-017-9337-x","volume":"23","author":"S Lamm","year":"2017","unstructured":"Lamm S, Sanders P, Schulz C, Strash D, Werneck RF (2017) Finding near-optimal independent sets at scale. J Heurist 23(4):207\u2013229. https:\/\/doi.org\/10.1007\/s10732-017-9337-x","journal-title":"J Heurist"},{"key":"5841_CR20","doi-asserted-by":"publisher","unstructured":"Zheng W, Wang Q, Yu JX, Cheng H, Zou L (2018) Efficient Computation of a Near-Maximum Independent Set Over Evolving Graphs. In: 34th IEEE International Conference on Data Engineering, ICDE 2018, Paris, France, Apr 16-19, pp 869\u2013880. https:\/\/doi.org\/10.1109\/ICDE.2018.00083","DOI":"10.1109\/ICDE.2018.00083"},{"key":"5841_CR21","doi-asserted-by":"publisher","unstructured":"Zheng W, Piao C, Cheng H, Yu JX (2019) Computing a Near-Maximum Independent Set in Dynamic Graphs. In: 35th IEEE International Conference on Data Engineering, ICDE 2019, Macao, China, Apr 8-11, pp 76\u201387. https:\/\/doi.org\/10.1109\/ICDE.2019.00016","DOI":"10.1109\/ICDE.2019.00016"},{"issue":"1","key":"5841_CR22","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1137\/1024022","volume":"24","author":"H Juris","year":"1982","unstructured":"Juris H (1982) Computers and intractability: a guide to the theory of np-completeness. SIAM Rev 24(1):90","journal-title":"SIAM Rev"},{"key":"5841_CR23","doi-asserted-by":"publisher","unstructured":"Abrishami T, Chudnovsky M, Pilipczuk M, Rzazewski P (2023) Max weight independent set in sparse graphs with no long claws. CoRR abs\/2309.16995https:\/\/doi.org\/10.48550\/arXiv.2309.16995arxiv:2309.16995","DOI":"10.48550\/arXiv.2309.16995"},{"key":"5841_CR24","doi-asserted-by":"publisher","unstructured":"Gartland P, Lokshtanov D, Masar\u00edk T, Pilipczuk M, Pilipczuk M, Rzazewski P (2023) Maximum weight independent set in graphs with no long claws in quasi-polynomial time. CoRR abs\/2305.15738. https:\/\/doi.org\/10.48550\/arXiv.2305.15738","DOI":"10.48550\/arXiv.2305.15738"},{"issue":"1","key":"5841_CR25","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1145\/3414473","volume":"18","author":"A Grzesik","year":"2022","unstructured":"Grzesik A, Klimosov\u00e1 T, Pilipczuk M, Pilipczuk M (2022) Polynomial-time algorithm for maximum weight independent set on P$${}_{\\text{6 }}$$-free graphs. ACM Trans Algorithms 18(1):4\u20131457. https:\/\/doi.org\/10.1145\/3414473","journal-title":"ACM Trans Algorithms"},{"key":"5841_CR26","doi-asserted-by":"publisher","unstructured":"Assadi S, Onak K, Schieber B, Solomon S (2018) Fully dynamic maximal independent set with sublinear update time. In: Diakonikolas I, Kempe D, Henzinger M (eds) Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, Jun 25-29, pp 815\u2013826. https:\/\/doi.org\/10.1145\/3188745.3188922","DOI":"10.1145\/3188745.3188922"},{"key":"5841_CR27","doi-asserted-by":"publisher","unstructured":"Behnezhad S, Derakhshan M, Hajiaghayi M, Stein C, Sudan M (2019) Fully dynamic maximal independent set with polylogarithmic update time. In: Zuckerman D (ed) 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, Nov 9-12, pp 382\u2013405. https:\/\/doi.org\/10.1109\/FOCS.2019.00032","DOI":"10.1109\/FOCS.2019.00032"}],"container-title":["The Journal of Supercomputing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-023-05841-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11227-023-05841-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-023-05841-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,6]],"date-time":"2024-05-06T10:49:30Z","timestamp":1714992570000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11227-023-05841-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,22]]},"references-count":29,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2024,5]]}},"alternative-id":["5841"],"URL":"https:\/\/doi.org\/10.1007\/s11227-023-05841-9","relation":{},"ISSN":["0920-8542","1573-0484"],"issn-type":[{"type":"print","value":"0920-8542"},{"type":"electronic","value":"1573-0484"}],"subject":[],"published":{"date-parts":[[2023,12,22]]},"assertion":[{"value":"24 November 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 December 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"We declare that we do not have any commercial or associative interest that represents a conflict of interest in connection with the work submitted.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"This work is not applicable for human or animal studies.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}}]}}