{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T01:23:02Z","timestamp":1773796982548,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":39,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,8,14]],"date-time":"2021-08-14T00:00:00Z","timestamp":1628899200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Key Research and Development Program of China under grant","award":["2019YFB1406401"],"award-info":[{"award-number":["2019YFB1406401"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61902074"],"award-info":[{"award-number":["61902074"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Science and Technology Committee Shanghai Municipality","award":["19ZR1404900"],"award-info":[{"award-number":["19ZR1404900"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,8,14]]},"DOI":"10.1145\/3447548.3467232","type":"proceedings-article","created":{"date-parts":[[2021,8,13]],"date-time":"2021-08-13T18:33:08Z","timestamp":1628879588000},"page":"467-477","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Towards Computing a Near-Maximum Weighted Independent Set on Massive Graphs"],"prefix":"10.1145","author":[{"given":"Jiewei","family":"Gu","sequence":"first","affiliation":[{"name":"Fudan University, Shanghai, China"}]},{"given":"Weiguo","family":"Zheng","sequence":"additional","affiliation":[{"name":"Fudan University, Shanghai, China"}]},{"given":"Yuzheng","family":"Cai","sequence":"additional","affiliation":[{"name":"Fudan University, Shanghai, China"}]},{"given":"Peng","family":"Peng","sequence":"additional","affiliation":[{"name":"Hunan University, Hunan, China"}]}],"member":"320","published-online":{"date-parts":[[2021,8,14]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.09.023"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10732-012-9196-4"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2011.06.004"},{"key":"e_1_3_2_2_4_1","unstructured":"William Brendel Mohamed R. Amer and Sinisa Todorovic. [n.d.]. Multiobject tracking as maximum weight independent set. In CVPR. 1273--1280.  William Brendel Mohamed R. Amer and Sinisa Todorovic. [n.d.]. Multiobject tracking as maximum weight independent set. In CVPR. 1273--1280."},{"key":"e_1_3_2_2_5_1","first-page":"307","article-title":"Segmentation as Maximum-Weight Independent Set","volume":"23","author":"Brendel William","year":"2010","unstructured":"William Brendel and Sinisa Todorovic . 2010 . Segmentation as Maximum-Weight Independent Set . In NIPS , Vol. 23. 307 -- 315 . William Brendel and Sinisa Todorovic. 2010. Segmentation as Maximum-Weight Independent Set. In NIPS, Vol. 23. 307--315.","journal-title":"NIPS"},{"key":"e_1_3_2_2_6_1","unstructured":"Shaowei Cai Wenying Hou Jinkun Lin and Yuanjie Li. [n.d.]. Improving Local Search for Minimum Weight Vertex Cover by Dynamic Strategies. In IJCAI J\u00e9r\u00f4me Lang (Ed.). 1412--1418.  Shaowei Cai Wenying Hou Jinkun Lin and Yuanjie Li. [n.d.]. Improving Local Search for Minimum Weight Vertex Cover by Dynamic Strategies. In IJCAI J\u00e9r\u00f4me Lang (Ed.). 1412--1418."},{"key":"e_1_3_2_2_7_1","unstructured":"Shaowei Cai and Jinkun Lin. 2016. Fast Solving Maximum Weight Clique Problem in Massive Graphs. In IJCAI. 568--574.  Shaowei Cai and Jinkun Lin. 2016. Fast Solving Maximum Weight Clique Problem in Massive Graphs. In IJCAI. 568--574."},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"crossref","unstructured":"Lijun Chang. 2019. Efficient Maximum Clique Computation over Large Sparse Graphs. In KDD. 529--538.  Lijun Chang. 2019. Efficient Maximum Clique Computation over Large Sparse Graphs. In KDD. 529--538.","DOI":"10.1109\/ICDE.2019.00241"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"crossref","unstructured":"Lijun Chang Wei Li and Wenjie Zhang. 2017. Computing A Near-Maximum Independent Set in Linear Time by Reducing-Peeling. In SIGMOD. 1181--1196.  Lijun Chang Wei Li and Wenjie Zhang. 2017. Computing A Near-Maximum Independent Set in Linear Time by Reducing-Peeling. In SIGMOD. 1181--1196.","DOI":"10.1145\/3035918.3035939"},{"key":"e_1_3_2_2_10_1","volume-title":"Werneck","author":"Dahlum Jakob","year":"2016","unstructured":"Jakob Dahlum , Sebastian Lamm , Peter Sanders , Christian Schulz , Darren Strash , and Renato F . Werneck . 2016 . Accelerating Local Search for the Maximum Independent Set Problem. In SEA. 118--133. Jakob Dahlum, Sebastian Lamm, Peter Sanders, Christian Schulz, Darren Strash, and Renato F. Werneck. 2016. Accelerating Local Search for the Maximum Independent Set Problem. In SEA. 118--133."},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S089548010240415X"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1552285.1552286"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1021\/ci990262o"},{"key":"e_1_3_2_2_14_1","volume-title":"Johnson","author":"Garey M. R.","year":"1979","unstructured":"M. R. Garey and David S . Johnson . 1979 . Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman . M. R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman."},{"key":"e_1_3_2_2_15_1","volume-title":"SEA","author":"Gemsa Andreas","year":"2014","unstructured":"Andreas Gemsa , Martin N\u00f6 llenburg, and Ignaz Rutter . 2014 . Evaluation of Labeling Strategies for Rotating Maps. In Experimental Algorithms - 13th International Symposium , SEA 2014. 235--246. Andreas Gemsa, Martin N\u00f6 llenburg, and Ignaz Rutter. 2014. Evaluation of Labeling Strategies for Rotating Maps. In Experimental Algorithms - 13th International Symposium, SEA 2014. 235--246."},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10732-007-9055-x"},{"key":"e_1_3_2_2_17_1","volume-title":"ACM Symposium on Theory of Computing. 439--448","author":"Magn\u00fas","unstructured":"Magn\u00fas M. Halld\u00f3 rsson and Jaikumar Radhakrishnan. 1994. Greed is good: approximating independent sets in sparse and bounded-degree graphs . In ACM Symposium on Theory of Computing. 439--448 . Magn\u00fas M. Halld\u00f3 rsson and Jaikumar Radhakrishnan. 1994. Greed is good: approximating independent sets in sparse and bounded-degree graphs. In ACM Symposium on Theory of Computing. 439--448."},{"key":"e_1_3_2_2_18_1","first-page":"145","article-title":"Greed is Good","volume":"18","author":"Jaikumar Radhakrishnan Magn\u00fa","year":"1997","unstructured":"Magn\u00fa s M. Halld\u00f3 rsson and Jaikumar Radhakrishnan . 1997 . Greed is Good : Approximating Independent Sets in Sparse and Bounded-Degree Graphs. Algorithmica , Vol. 18 , 1 (1997), 145 -- 163 . Magn\u00fa s M. Halld\u00f3 rsson and Jaikumar Radhakrishnan. 1997. Greed is Good: Approximating Independent Sets in Sparse and Bounded-Degree Graphs. Algorithmica, Vol. 18, 1 (1997), 145--163.","journal-title":"Approximating Independent Sets in Sparse and Bounded-Degree Graphs. Algorithmica"},{"key":"e_1_3_2_2_19_1","volume-title":"Annual Symposium on Foundations of Computer Science. 627--636","author":"H\u00e5stad Johan","year":"1996","unstructured":"Johan H\u00e5stad . 1996 . Clique is Hard to Approximate Within n(1-epsilon) . In Annual Symposium on Foundations of Computer Science. 627--636 . Johan H\u00e5stad. 1996. Clique is Hard to Approximate Within n(1-epsilon). In Annual Symposium on Foundations of Computer Science. 627--636."},{"key":"e_1_3_2_2_20_1","volume-title":"Low Delay Scheduling in Wireless Network. In IEEE International Symposium on Information Theory.","author":"Jung Kyomin","year":"2007","unstructured":"Kyomin Jung and Devavrat Shah . 2007 . Low Delay Scheduling in Wireless Network. In IEEE International Symposium on Information Theory. Kyomin Jung and Devavrat Shah. 2007. Low Delay Scheduling in Wireless Network. In IEEE International Symposium on Information Theory."},{"key":"e_1_3_2_2_21_1","volume-title":"Low Delay Scheduling in Wireless Network. In 2007 IEEE International Symposium on Information Theory. 1396--1400","author":"Jung K.","unstructured":"K. Jung and D. Shah . 2007 . Low Delay Scheduling in Wireless Network. In 2007 IEEE International Symposium on Information Theory. 1396--1400 . K. Jung and D. Shah. 2007. Low Delay Scheduling in Wireless Network. In 2007 IEEE International Symposium on Information Theory. 1396--1400."},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.08.027"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795286612"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"crossref","unstructured":"Tim Kieritz Dennis Luxen Peter Sanders and Christian Vetter. 2010. Distributed Time-Dependent Contraction Hierarchies. In Experimental Algorithms. 83--93.  Tim Kieritz Dennis Luxen Peter Sanders and Christian Vetter. 2010. Distributed Time-Dependent Contraction Hierarchies. In Experimental Algorithms. 83--93.","DOI":"10.1007\/978-3-642-13193-6_8"},{"key":"e_1_3_2_2_25_1","volume-title":"Werneck","author":"Lamm Sebastian","year":"2016","unstructured":"Sebastian Lamm , Peter Sanders , Christian Schulz , Darren Strash , and Renato F . Werneck . 2016 . Finding Near-Optimal Independent Sets at Scale. In ALENEX. 138--150. Sebastian Lamm, Peter Sanders, Christian Schulz, Darren Strash, and Renato F. Werneck. 2016. Finding Near-Optimal Independent Sets at Scale. In ALENEX. 138--150."},{"key":"e_1_3_2_2_26_1","volume-title":"ALENEX,, Stephen G","author":"Lamm Sebastian","unstructured":"Sebastian Lamm , Christian Schulz , Darren Strash , Robert Williger , and Huashuo Zhang . 2019. Exactly Solving the Maximum Weight Independent Set Problem on Large Real-World Graphs . In ALENEX,, Stephen G . Kobourov and Henning Meyerhenke (Eds.). SIAM , 144--158. Sebastian Lamm, Christian Schulz, Darren Strash, Robert Williger, and Huashuo Zhang. 2019. Exactly Solving the Maximum Weight Independent Set Problem on Large Real-World Graphs. In ALENEX,, Stephen G. Kobourov and Henning Meyerhenke (Eds.). SIAM, 144--158."},{"key":"e_1_3_2_2_27_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data.  Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/2831360.2831366"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580444"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-017-1128-7"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2014.2338277"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90032-5"},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2009.2030448"},{"key":"e_1_3_2_2_34_1","unstructured":"Peng-Jun Wan Boliu Xu Lei Wang Sai Ji and Ophir Frieder. 2015. A new paradigm for multiflow in wireless networks: Theory and applications. In INFOCOM. 1706--1714.  Peng-Jun Wan Boliu Xu Lei Wang Sai Ji and Ophir Frieder. 2015. A new paradigm for multiflow in wireless networks: Theory and applications. In INFOCOM. 1706--1714."},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"crossref","unstructured":"Jingen Xiang Cong Guo and Ashraf Aboulnaga. 2013. Scalable maximum clique computation using MapReduce. In ICDE. 74--85.  Jingen Xiang Cong Guo and Ashraf Aboulnaga. 2013. Scalable maximum clique computation using MapReduce. In ICDE. 74--85.","DOI":"10.1109\/ICDE.2013.6544815"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"crossref","unstructured":"Mingyu Xiao and Hiroshi Nagamochi. 2013. Exact Algorithms for Maximum Independent Set. In ISAAC. 328--338.  Mingyu Xiao and Hiroshi Nagamochi. 2013. Exact Algorithms for Maximum Independent Set. In ISAAC. 328--338.","DOI":"10.1007\/978-3-642-45030-3_31"},{"key":"e_1_3_2_2_37_1","unstructured":"M. J. Zaki S. Parthasarathy M. Ogihara and W. Li. 1997. New algorithms for fast discovery of association rules. In KDD. 283--286.  M. J. Zaki S. Parthasarathy M. Ogihara and W. Li. 1997. New algorithms for fast discovery of association rules. In KDD. 283--286."},{"key":"e_1_3_2_2_38_1","volume-title":"Efficient Weighted Independent Set Computation over Large Graphs","author":"Zheng Weiguo","year":"1970","unstructured":"Weiguo Zheng , Jiewei Gu , Peng Peng , and Jeffrey Xu Yu. 2020. Efficient Weighted Independent Set Computation over Large Graphs . In ICDE. IEEE , 1970 --1973. Weiguo Zheng, Jiewei Gu, Peng Peng, and Jeffrey Xu Yu. 2020. Efficient Weighted Independent Set Computation over Large Graphs. In ICDE. IEEE, 1970--1973."},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"crossref","unstructured":"Weiguo Zheng Chengzhi Piao Hong Cheng and Jeffrey Xu Yu. 2019. Computing a Near-Maximum Independent Set in Dynamic Graphs. In ICDE. 76--87.  Weiguo Zheng Chengzhi Piao Hong Cheng and Jeffrey Xu Yu. 2019. Computing a Near-Maximum Independent Set in Dynamic Graphs. In ICDE. 76--87.","DOI":"10.1109\/ICDE.2019.00016"}],"event":{"name":"KDD '21: The 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining","location":"Virtual Event Singapore","acronym":"KDD '21","sponsor":["SIGMOD ACM Special Interest Group on Management of Data","SIGKDD ACM Special Interest Group on Knowledge Discovery in Data"]},"container-title":["Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3447548.3467232","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3447548.3467232","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:28Z","timestamp":1750191508000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3447548.3467232"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,14]]},"references-count":39,"alternative-id":["10.1145\/3447548.3467232","10.1145\/3447548"],"URL":"https:\/\/doi.org\/10.1145\/3447548.3467232","relation":{},"subject":[],"published":{"date-parts":[[2021,8,14]]},"assertion":[{"value":"2021-08-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}