{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T17:52:23Z","timestamp":1775065943832,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":39,"publisher":"ACM","license":[{"start":{"date-parts":[[2017,5,9]],"date-time":"2017-05-09T00:00:00Z","timestamp":1494288000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2017,5,9]]},"DOI":"10.1145\/3035918.3035939","type":"proceedings-article","created":{"date-parts":[[2017,5,10]],"date-time":"2017-05-10T18:09:00Z","timestamp":1494439740000},"page":"1181-1196","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":39,"title":["Computing A Near-Maximum Independent Set in Linear Time by Reducing-Peeling"],"prefix":"10.1145","author":[{"given":"Lijun","family":"Chang","sequence":"first","affiliation":[{"name":"University of New South Wales, Sydney, Australia"}]},{"given":"Wei","family":"Li","sequence":"additional","affiliation":[{"name":"University of New South Wales, Sydney, Australia"}]},{"given":"Wenjie","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of New South Wales, Sydney, Australia"}]}],"member":"320","published-online":{"date-parts":[[2017,5,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.09.023"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10732-012-9196-4"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2011.06.004"},{"key":"e_1_3_2_1_4_1","first-page":"286","author":"Barabasi A.-L.","year":"1999","unstructured":"A.-L. Barabasi and R. Albert . Emergence of scaling in random networks. Science , 286 , 1999 . A.-L. Barabasi and R. Albert. Emergence of scaling in random networks. Science, 286, 1999.","journal-title":"Emergence of scaling in random networks. Science"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1016747704458"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2012.06.002"},{"key":"e_1_3_2_1_7_1","volume-title":"On approximation properties of the independent set problem for low degree graphs. Theor. Comput. Sys., 32(2)","author":"Berman P.","year":"1999","unstructured":"P. Berman and T. Fujito . On approximation properties of the independent set problem for low degree graphs. Theor. Comput. Sys., 32(2) , 1999 . P. Berman and T. Fujito. On approximation properties of the independent set problem for low degree graphs. Theor. Comput. Sys., 32(2), 1999."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915236"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2004.03.002"},{"key":"e_1_3_2_1_11_1","volume-title":"Proc. of IJCAI'15","author":"Cai S.","year":"2015","unstructured":"S. Cai . Balance between complexity and quality: local search for minimum vertex cover in massive graphs . In Proc. of IJCAI'15 , 2015 . S. Cai. Balance between complexity and quality: local search for minimum vertex cover in massive graphs. In Proc. of IJCAI'15, 2015."},{"key":"e_1_3_2_1_12_1","volume-title":"Algorithmica","author":"Chang L.","year":"2012","unstructured":"L. Chang , J. X. Yu , and L. Qin . Fast maximal cliques enumeration in sparse graphs . Algorithmica , 2012 . L. Chang, J. X. Yu, and L. Qin. Fast maximal cliques enumeration in sparse graphs. Algorithmica, 2012."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465323"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213888"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807217"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214017"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722211"},{"key":"e_1_3_2_1_18_1","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2001","unstructured":"T. H. Cormen , C. E. Leiserson , R. L. Rivest , and C. Stein . Introduction to Algorithms . McGraw-Hill Higher Education , 2001 . T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. McGraw-Hill Higher Education, 2001."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-38851-9_9"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S089548010240415X"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1552285.1552286"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536336.2536346"},{"key":"e_1_3_2_1_23_1","volume-title":"Computers and Intractability","author":"Garey M. R.","year":"1990","unstructured":"M. R. Garey and D. S. Johnson . Computers and Intractability ; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co. , New York, NY, USA, 1990 . M. R. Garey and D. S. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA, 1990."},{"key":"e_1_3_2_1_24_1","volume-title":"Algorithmic Graph Theory","author":"Gibbons A.","year":"1985","unstructured":"A. Gibbons . Algorithmic Graph Theory . Cambridge University Press , 1985 . A. Gibbons. Algorithmic Graph Theory. Cambridge University Press, 1985."},{"key":"e_1_3_2_1_25_1","volume-title":"Greed is good: Approximating independent sets in sparse and bounded-degree graphs. Algorithmica, 18(1)","author":"Halld\u00f3rsson M. M.","year":"1997","unstructured":"M. M. Halld\u00f3rsson and J. Radhakrishnan . Greed is good: Approximating independent sets in sparse and bounded-degree graphs. Algorithmica, 18(1) , 1997 . M. M. Halld\u00f3rsson and J. Radhakrishnan. Greed is good: Approximating independent sets in sparse and bounded-degree graphs. Algorithmica, 18(1), 1997."},{"key":"e_1_3_2_1_26_1","volume-title":"Proc. of FOCS'96","author":"H\u00e5stad J.","year":"1996","unstructured":"J. H\u00e5stad . Clique is hard to approximate within n 1\u03b5 . In Proc. of FOCS'96 , 1996 . J. H\u00e5stad. Clique is hard to approximate within n 1\u03b5. In Proc. of FOCS'96, 1996."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-20086-6_6"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974317.12"},{"key":"e_1_3_2_1_29_1","volume-title":"Slashburn: Graph compression and mining beyond caveman communities","author":"Lim Y.","year":"2014","unstructured":"Y. Lim , U. Kang , and C. Faloutsos . Slashburn: Graph compression and mining beyond caveman communities . IEEE Trans. Knowl. Data Eng ., 26(12), 2014 . Y. Lim, U. Kang, and C. Faloutsos. Slashburn: Graph compression and mining beyond caveman communities. IEEE Trans. Knowl. Data Eng., 26(12), 2014."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/2831360.2831366"},{"issue":"3","key":"e_1_3_2_1_31_1","volume":"4","author":"Pardalos P. M.","year":"1994","unstructured":"P. M. Pardalos and J. Xue . The maximum clique problem. J. global Optimization , 4 ( 3 ), 1994 . P. M. Pardalos and J. Xue. The maximum clique problem. J. global Optimization, 4(3), 1994.","journal-title":"The maximum clique problem. J. global Optimization"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigDataCongress.2015.75"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2015.07.013"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/1410219"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11440-3_18"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2015.7218551"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544815"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.09.022"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2014.6816652"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-012-0292-8"}],"event":{"name":"SIGMOD\/PODS'17: International Conference on Management of Data","location":"Chicago Illinois USA","acronym":"SIGMOD\/PODS'17","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"]},"container-title":["Proceedings of the 2017 ACM International Conference on Management of Data"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3035918.3035939","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3035918.3035939","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:36:48Z","timestamp":1750217808000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3035918.3035939"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,9]]},"references-count":39,"alternative-id":["10.1145\/3035918.3035939","10.1145\/3035918"],"URL":"https:\/\/doi.org\/10.1145\/3035918.3035939","relation":{},"subject":[],"published":{"date-parts":[[2017,5,9]]},"assertion":[{"value":"2017-05-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}