{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:45:56Z","timestamp":1742913956954,"version":"3.40.3"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319930305"},{"type":"electronic","value":"9783319930312"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-93031-2_41","type":"book-chapter","created":{"date-parts":[[2018,6,7]],"date-time":"2018-06-07T06:04:24Z","timestamp":1528351464000},"page":"567-584","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A Warning Propagation-Based Linear-Time-and-Space Algorithm for the Minimum Vertex Cover Problem on Giant Graphs"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7874-4518","authenticated-orcid":false,"given":"Hong","family":"Xu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3261-7358","authenticated-orcid":false,"given":"Kexuan","family":"Sun","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sven","family":"Koenig","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"T. K. Satish","family":"Kumar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,6,8]]},"reference":[{"key":"41_CR1","unstructured":"Abu-Khzam, F.N., Collins, R.L., Fellows, M.R., Langston, M.A., Suters, W.H., Symons, C.T.: Kernelization algorithms for the vertex cover problem: theory and experiments. In: The Workshop on Algorithm Engineering and Experiments (2004)"},{"issue":"4","key":"41_CR2","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1007\/s10732-012-9196-4","volume":"18","author":"DV Andrade","year":"2012","unstructured":"Andrade, D.V., Resende, M.G.C., Werneck, R.F.: Fast local search for the maximum independent set problem. J. Heuristics 18(4), 525\u2013547 (2012). https:\/\/doi.org\/10.1007\/s10732-012-9196-4","journal-title":"J. Heuristics"},{"key":"41_CR3","series-title":"Discrete Mathematics and Theoretical Computer Science","volume-title":"Graph Partitioning and Graph Clustering","year":"2013","unstructured":"Bader, D.A., Meyerhenke, H., Sanders, P., Wagner, D. (eds.): Graph Partitioning and Graph Clustering. Discrete Mathematics and Theoretical Computer Science. American Mathematical Society and Center, Providence (2013)"},{"issue":"5439","key":"41_CR4","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1126\/science.286.5439.509","volume":"286","author":"AL Barab\u00e1si","year":"1999","unstructured":"Barab\u00e1si, A.L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509\u2013512 (1999). https:\/\/doi.org\/10.1126\/science.286.5439.509","journal-title":"Science"},{"key":"41_CR5","unstructured":"Cai, S.: Balance between complexity and quality: local search for minimum vertex cover in massive graphs. In: The International Joint Conference on Artificial Intelligence, pp. 747\u2013753 (2015)"},{"issue":"1","key":"41_CR6","doi-asserted-by":"publisher","first-page":"687","DOI":"10.1613\/jair.3907","volume":"46","author":"S Cai","year":"2013","unstructured":"Cai, S., Su, K., Luo, C., Sattar, A.: NuMVC: an efficient local search algorithm for minimum vertex cover. J. Artif. Intell. Res. 46(1), 687\u2013716 (2013). https:\/\/doi.org\/10.1613\/jair.3907","journal-title":"J. Artif. Intell. Res."},{"issue":"1","key":"41_CR7","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/BF02124750","volume":"5","author":"RM Corless","year":"1996","unstructured":"Corless, R.M., Gonnet, G.H., Hare, D.E.G., Jeffrey, D.J., Knuth, D.E.: On the LambertW function. Adv. Comput. Math. 5(1), 329\u2013359 (1996). https:\/\/doi.org\/10.1007\/BF02124750","journal-title":"Adv. Comput. Math."},{"issue":"1","key":"41_CR8","doi-asserted-by":"publisher","first-page":"439","DOI":"10.4007\/annals.2005.162.439","volume":"162","author":"I Dinur","year":"2005","unstructured":"Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Ann. Math. 162(1), 439\u2013485 (2005). https:\/\/doi.org\/10.4007\/annals.2005.162.439","journal-title":"Ann. Math."},{"key":"41_CR9","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","volume":"6","author":"P Erd\u0151s","year":"1959","unstructured":"Erd\u0151s, P., R\u00e9nyi, A.: On random graphs I. Publicationes Mathematicae 6, 290\u2013297 (1959)","journal-title":"Publicationes Mathematicae"},{"key":"41_CR10","doi-asserted-by":"publisher","first-page":"799","DOI":"10.1613\/jair.4953","volume":"55","author":"Z Fang","year":"2016","unstructured":"Fang, Z., Li, C.M., Xu, K.: An exact algorithm based on MaxSAT reasoning for the maximum weight clique problem. J. Artif. Intell. Res. 55, 799\u2013833 (2016). https:\/\/doi.org\/10.1613\/jair.4953","journal-title":"J. Artif. Intell. Res."},{"issue":"10","key":"41_CR11","first-page":"2931","volume":"1","author":"E Filiol","year":"2007","unstructured":"Filiol, E., Franc, E., Gubbioli, A., Moquet, B., Roblot, G.: Combinatorial optimisation of worm propagation on an unknown network. Int. J. Comput. Electr. Autom. Control Inf. Eng. 1(10), 2931\u20132937 (2007)","journal-title":"Int. J. Comput. Electr. Autom. Control Inf. Eng."},{"key":"41_CR12","volume-title":"Mathematical Constants, Encyclopedia of Mathematics and Its Applications","author":"SR Finch","year":"2003","unstructured":"Finch, S.R.: Mathematical Constants, Encyclopedia of Mathematics and Its Applications, vol. 94. Cambridge University Press, Cambridge (2003)"},{"key":"41_CR13","series-title":"Texts in Theoretical Computer Science. An EATCS Series","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-29953-X","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. TTCSAES. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/3-540-29953-X"},{"key":"41_CR14","doi-asserted-by":"publisher","unstructured":"Goyal, A., Lu, W., Lakshmanan, L.V.S.: SIMPATH: an efficient algorithm for influence maximization under the linear threshold model. In: The IEEE International Conference on Data Mining, pp. 211\u2013220 (2011). https:\/\/doi.org\/10.1109\/ICDM.2011.132","DOI":"10.1109\/ICDM.2011.132"},{"key":"41_CR15","first-page":"803","volume-title":"Handbook of Mathematical Functions: With Formulas, Graphs, and Mathematical Tables","author":"EV Haynsworth","year":"1965","unstructured":"Haynsworth, E.V., Goldberg, K.: Bernoulli and Euler polynomials-Riemann zeta function. In: Abramowitz, M., Stegun, I.A. (eds.) Handbook of Mathematical Functions: With Formulas, Graphs, and Mathematical Tables, pp. 803\u2013819. Dover Publications, Inc., Mineola (1965)"},{"issue":"2","key":"41_CR16","doi-asserted-by":"publisher","first-page":"891","DOI":"10.4007\/annals.2011.174.2.4","volume":"174","author":"GA Hiary","year":"2011","unstructured":"Hiary, G.A.: Fast methods to compute the Riemann zeta function. Ann. Math. 174(2), 891\u2013946 (2011). https:\/\/doi.org\/10.4007\/annals.2011.174.2.4","journal-title":"Ann. Math."},{"volume-title":"Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge","year":"1996","key":"41_CR17","unstructured":"Johnson, D.J., Trick, M.A. (eds.): Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge. American Mathematical Society, Providence (1996)"},{"key":"41_CR18","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"Richard M. Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85\u2013103. Plenum Press, New York (1972)"},{"key":"41_CR19","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24488-9","volume-title":"Combinatorial Optimization: Theory and Algorithms","author":"B Korte","year":"2012","unstructured":"Korte, B., Vygen, J.: Combinatorial Optimization: Theory and Algorithms, 5th edn. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-24488-9","edition":"5"},{"key":"41_CR20","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198570837.001.0001","volume-title":"Information, Physics, and Computation","author":"M M\u00e9zard","year":"2009","unstructured":"M\u00e9zard, M., Montanari, A.: Information, Physics, and Computation. Oxford University Press, Oxford (2009)"},{"key":"41_CR21","unstructured":"Niskanen, S., \u00d6sterg\u00e5rd, P.R.J.: Cliquer user\u2019s guide, version 1.0. Technical report T48, Communications Laboratory, Helsinki University of Technology, Espoo, Finland (2003)"},{"issue":"2","key":"41_CR22","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1016\/j.disopt.2008.12.001","volume":"6","author":"W Pullan","year":"2009","unstructured":"Pullan, W.: Optimisation of unweighted\/weighted maximum independent sets and minimum vertex covers. Discret. Optim. 6(2), 214\u2013219 (2009). https:\/\/doi.org\/10.1016\/j.disopt.2008.12.001","journal-title":"Discret. Optim."},{"key":"41_CR23","doi-asserted-by":"crossref","unstructured":"Rossi, R.A., Ahmed, N.K.: The network data repository with interactive graph analytics and visualization. In: the AAAI Conference on Artificial Intelligence, pp. 4292\u20134293 (2015). http:\/\/networkrepository.com","DOI":"10.1609\/aaai.v29i1.9277"},{"issue":"2","key":"41_CR24","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1057\/jors.1984.16","volume":"35","author":"HD Sherali","year":"1984","unstructured":"Sherali, H.D., Rios, M.: An air force crew allocation and scheduling problem. J. Oper. Res. Soc. 35(2), 91\u2013103 (1984)","journal-title":"J. Oper. Res. Soc."},{"key":"41_CR25","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04565-7","volume-title":"Approximation Algorithms","author":"VV Vazirani","year":"2003","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/978-3-662-04565-7"},{"issue":"4","key":"41_CR26","doi-asserted-by":"publisher","first-page":"046110","DOI":"10.1103\/PhysRevE.74.046110","volume":"74","author":"M Weigt","year":"2006","unstructured":"Weigt, M., Zhou, H.: Message passing for vertex covers. Phys. Rev. E 74(4), 046110 (2006). https:\/\/doi.org\/10.1103\/PhysRevE.74.046110","journal-title":"Phys. Rev. E"},{"key":"41_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"392","DOI":"10.1007\/978-3-319-33954-2_28","volume-title":"Integration of AI and OR Techniques in Constraint Programming","author":"H Xu","year":"2016","unstructured":"Xu, H., Kumar, T.K.S., Koenig, S.: A new solver for the minimum weighted vertex cover problem. In: Quimper, C.-G. (ed.) CPAIOR 2016. LNCS, vol. 9676, pp. 392\u2013405. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-33954-2_28"},{"key":"41_CR28","doi-asserted-by":"crossref","unstructured":"Xu, H., Kumar, T.K.S., Koenig, S.: A linear-time and linear-space algorithm for the minimum vertex cover problem on giant graphs. In: The International Symposium on Combinatorial Search, pp. 173\u2013174 (2017)","DOI":"10.1609\/socs.v8i1.18414"},{"key":"41_CR29","unstructured":"Yamaguchi, K., Masuda, S.: A new exact algorithm for the maximum weight clique problem. In: The International Technical Conference on Circuits\/Systems, Computers and Communications. pp. 317\u2013320 (2008)"}],"container-title":["Lecture Notes in Computer Science","Integration of Constraint Programming, Artificial Intelligence, and Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-93031-2_41","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T17:30:11Z","timestamp":1709832611000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-93031-2_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319930305","9783319930312"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-93031-2_41","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"8 June 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CPAIOR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Delft","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"The Netherlands","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 June 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 June 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cpaior2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sites.google.com\/view\/cpaior2018\/home","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}