{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:22:06Z","timestamp":1759638126894,"version":"3.40.3"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030250263"},{"type":"electronic","value":"9783030250270"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","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":[[2019]]},"DOI":"10.1007\/978-3-030-25027-0_17","type":"book-chapter","created":{"date-parts":[[2019,8,1]],"date-time":"2019-08-01T00:04:09Z","timestamp":1564617849000},"page":"243-257","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["On the Tractability of Covering a Graph with 2-Clubs"],"prefix":"10.1007","author":[{"given":"Riccardo","family":"Dondi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manuel","family":"Lafond","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,7,10]]},"reference":[{"key":"17_CR1","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1080\/0022250X.1973.9989826","volume":"3","author":"RD Alba","year":"1973","unstructured":"Alba, R.D.: A graph-theoretic definition of a sociometric clique. J. Math. Sociol. 3, 113\u2013126 (1973)","journal-title":"J. Math. Sociol."},{"issue":"6","key":"17_CR2","doi-asserted-by":"publisher","first-page":"1834","DOI":"10.1007\/s00453-017-0344-y","volume":"80","author":"Y Asahiro","year":"2018","unstructured":"Asahiro, Y., Doi, Y., Miyano, E., Samizo, K., Shimizu, H.: Optimal approximation algorithms for maximum distance-bounded subgraph problems. Algorithmica 80(6), 1834\u20131856 (2018)","journal-title":"Algorithmica"},{"issue":"1","key":"17_CR3","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/s10878-005-1857-x","volume":"10","author":"B Balasundaram","year":"2005","unstructured":"Balasundaram, B., Butenko, S., Trukhanov, S.: Novel approaches for analyzing biological networks. J. Comb. Optim. 10(1), 23\u201339 (2005)","journal-title":"J. Comb. Optim."},{"issue":"1","key":"17_CR4","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/S0377-2217(01)00133-3","volume":"138","author":"J Bourjolly","year":"2002","unstructured":"Bourjolly, J., Laporte, G., Pesant, G.: An exact algorithm for the maximum k-club problem in an undirected graph. Eur. J. Oper. Res. 138(1), 21\u201328 (2002)","journal-title":"Eur. J. Oper. Res."},{"issue":"12","key":"17_CR5","doi-asserted-by":"publisher","first-page":"2270","DOI":"10.1016\/j.dam.2007.10.015","volume":"156","author":"MR Cerioli","year":"2008","unstructured":"Cerioli, M.R., Faria, L., Ferreira, T.O., Martinhon, C.A.J., Protti, F., Reed, B.A.: Partition into cliques for cubic graphs: planar case, complexity and approximation. Discret. Appl. Math. 156(12), 2270\u20132278 (2008)","journal-title":"Discret. Appl. Math."},{"issue":"3","key":"17_CR6","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1051\/ita\/2011106","volume":"45","author":"MR Cerioli","year":"2011","unstructured":"Cerioli, M.R., Faria, L., Ferreira, T.O., Protti, F.: A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation. RAIRO-Theor. Inform. Appl. 45(3), 331\u2013346 (2011)","journal-title":"RAIRO-Theor. Inform. Appl."},{"issue":"9","key":"17_CR7","doi-asserted-by":"publisher","first-page":"739","DOI":"10.1007\/s00607-012-0263-3","volume":"95","author":"M Chang","year":"2013","unstructured":"Chang, M., Hung, L., Lin, C., Su, P.: Finding large k-clubs in undirected graphs. Computing 95(9), 739\u2013758 (2013)","journal-title":"Computing"},{"issue":"2","key":"17_CR8","doi-asserted-by":"publisher","first-page":"271","DOI":"10.7155\/jgaa.00491","volume":"23","author":"R Dondi","year":"2019","unstructured":"Dondi, R., Mauri, G., Sikora, F., Zoppis, I.: Covering a graph with clubs. J. Graph Algorithms Appl. 23(2), 271\u2013292 (2019)","journal-title":"J. Graph Algorithms Appl."},{"key":"17_CR9","doi-asserted-by":"crossref","unstructured":"Dondi, R., Mauri, G., Zoppis, I.: On the tractability of finding disjoint clubs in a network. Theor. Comput. Sci. (2019, to appear)","DOI":"10.1016\/j.tcs.2019.03.045"},{"issue":"3","key":"17_CR10","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/s00373-011-1026-1","volume":"27","author":"A Dumitrescu","year":"2011","unstructured":"Dumitrescu, A., Pach, J.: Minimum clique partition in unit disk graphs. Graphs Comb. 27(3), 399\u2013411 (2011)","journal-title":"Graphs Comb."},{"issue":"1","key":"17_CR11","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.tcs.2008.09.065","volume":"410","author":"MR Fellows","year":"2009","unstructured":"Fellows, M.R., Hermelin, D., Rosamond, F.A., Vialette, S.: On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci. 410(1), 53\u201361 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"17_CR12","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"MR Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.J.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1(3), 237\u2013267 (1976)","journal-title":"Theor. Comput. Sci."},{"key":"17_CR13","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)"},{"key":"17_CR14","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.dam.2014.04.016","volume":"174","author":"PA Golovach","year":"2014","unstructured":"Golovach, P.A., Heggernes, P., Kratsch, D., Rafiey, A.: Finding clubs in graph classes. Discrete Appl. Math. 174, 57\u201365 (2014)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"17_CR15","doi-asserted-by":"publisher","first-page":"155","DOI":"10.7155\/jgaa.00352","volume":"19","author":"S Hartung","year":"2015","unstructured":"Hartung, S., Komusiewicz, C., Nichterlein, A.: Parameterized algorithmics and computational experiments for finding 2-clubs. J. Graph Algorithms Appl. 19(1), 155\u2013190 (2015)","journal-title":"J. Graph Algorithms Appl."},{"key":"17_CR16","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Proceedings of a symposium on the Complexity of Computer Computations, held 20\u201322 March 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York. The IBM Research Symposia Series, pp. 85\u2013103. Plenum Press, New York (1972)"},{"key":"17_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth, Computations and Approximations","author":"T Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth, Computations and Approximations. LNCS, vol. 842. Springer, Heidelberg (1994). https:\/\/doi.org\/10.1007\/BFb0045375"},{"issue":"1","key":"17_CR18","doi-asserted-by":"publisher","first-page":"21","DOI":"10.3390\/a9010021","volume":"9","author":"C Komusiewicz","year":"2016","unstructured":"Komusiewicz, C.: Multivariate algorithmics for finding cohesive subnetworks. Algorithms 9(1), 21 (2016)","journal-title":"Algorithms"},{"key":"17_CR19","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/j.dam.2015.04.029","volume":"193","author":"C Komusiewicz","year":"2015","unstructured":"Komusiewicz, C., Sorge, M.: An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems. Discrete Appl. Math. 193, 145\u2013161 (2015)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"17_CR20","doi-asserted-by":"publisher","first-page":"20:1","DOI":"10.1007\/s13278-016-0326-0","volume":"6","author":"S Laan","year":"2016","unstructured":"Laan, S., Marx, M., Mokken, R.J.: Close communities in social networks: boroughs and 2-clubs. Soc. Netw. Anal. Min. 6(1), 20:1\u201320:16 (2016)","journal-title":"Soc. Netw. Anal. Min."},{"issue":"2","key":"17_CR21","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/BF00139635","volume":"13","author":"R Mokken","year":"1979","unstructured":"Mokken, R.: Cliques, clubs and clans. Qual. Quant.: Int. J. Methodol. 13(2), 161\u2013173 (1979)","journal-title":"Qual. Quant.: Int. J. Methodol."},{"issue":"1","key":"17_CR22","doi-asserted-by":"publisher","first-page":"40:1","DOI":"10.1007\/s13278-016-0345-x","volume":"6","author":"RJ Mokken","year":"2016","unstructured":"Mokken, R.J., Heemskerk, E.M., Laan, S.: Close communication and 2-clubs in corporate networks: Europe 2010. Soc. Netw. Anal. Min. 6(1), 40:1\u201340:19 (2016)","journal-title":"Soc. Netw. Anal. Min."},{"key":"17_CR23","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/0304-3975(81)90081-5","volume":"15","author":"A Paz","year":"1981","unstructured":"Paz, A., Moran, S.: Non deterministic polynomial optimization problems and their approximations. Theor. Comput. Sci. 15, 251\u2013277 (1981)","journal-title":"Theor. Comput. Sci."},{"issue":"3\u20134","key":"17_CR24","doi-asserted-by":"publisher","first-page":"1050","DOI":"10.1007\/s00453-011-9503-8","volume":"62","author":"IA Pirwani","year":"2012","unstructured":"Pirwani, I.A., Salavatipour, M.R.: A weakly robust PTAS for minimum clique partition in unit disk graphs. Algorithmica 62(3\u20134), 1050\u20131072 (2012)","journal-title":"Algorithmica"},{"issue":"5","key":"17_CR25","doi-asserted-by":"publisher","first-page":"883","DOI":"10.1007\/s11590-011-0311-5","volume":"6","author":"A Sch\u00e4fer","year":"2012","unstructured":"Sch\u00e4fer, A., Komusiewicz, C., Moser, H., Niedermeier, R.: Parameterized computational complexity of finding small-diameter subgraphs. Optim. Lett. 6(5), 883\u2013891 (2012)","journal-title":"Optim. Lett."}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-25027-0_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T13:25:36Z","timestamp":1710336336000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-25027-0_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030250263","9783030250270"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-25027-0_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"10 July 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FCT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Fundamentals of Computation Theory","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Copenhagen","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Denmark","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 August 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14 August 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fct0","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/di.ku.dk\/fct2019","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}