{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:54:34Z","timestamp":1742914474956,"version":"3.40.3"},"publisher-location":"Cham","reference-count":15,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319575858"},{"type":"electronic","value":"9783319575865"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"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":[[2017]]},"DOI":"10.1007\/978-3-319-57586-5_8","type":"book-chapter","created":{"date-parts":[[2017,4,13]],"date-time":"2017-04-13T15:23:34Z","timestamp":1492097014000},"page":"80-91","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the Complexity of Finding a Potential Community"],"prefix":"10.1007","author":[{"given":"Cristina","family":"Bazgan","sequence":"first","affiliation":[]},{"given":"Thomas","family":"Pontoizeau","sequence":"additional","affiliation":[]},{"given":"Zsolt","family":"Tuza","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,4,14]]},"reference":[{"key":"8_CR1","unstructured":"Alekseev, V.E.: On the local restrictions effect on the complexity of finding the graph independence number. In: Combinatorial-Algebraic Methods in Applied Mathematics, pp. 3\u201313 (1983)"},{"key":"8_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1007\/3-540-62592-5_80","volume-title":"Algorithms and Complexity","author":"P Alimonti","year":"1997","unstructured":"Alimonti, P., Kann, V.: Hardness of approximating problems on cubic graphs. In: Bongiovanni, G., Bovet, D.P., Battista, G. (eds.) CIAC 1997. LNCS, vol. 1203, pp. 288\u2013298. Springer, Heidelberg (1997). doi:10.1007\/3-540-62592-5_80"},{"key":"8_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"HL Bodlaender","year":"1998","unstructured":"Bodlaender, H.L.: A partial $$k$$-arboretum of graphs with bounded treewidth. Theoret. Comput. Sci. 209, 1\u201345 (1998)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"8_CR4","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"KS Booth","year":"1976","unstructured":"Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci. 13(3), 335\u2013379 (1976)","journal-title":"J. Comput. Syst. Sci."},{"key":"8_CR5","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0166-218X(81)90013-5","volume":"3","author":"LS Burlingham","year":"1981","unstructured":"Burlingham, L.S., Corneil, D.G., Lerchs, H.: Complement reducible graphs. Discret. Appl. Math. 3, 163\u2013174 (1981)","journal-title":"Discret. Appl. Math."},{"key":"8_CR6","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1051\/ita\/1992260302571","volume":"26","author":"B Courcelle","year":"1992","unstructured":"Courcelle, B.: The monadic second-order logic of graphs iii: tree-decompositions, minors and complexity issues. RAIRO - Informatique Th\u00e9orique et Appl. 26, 257\u2013286 (1992)","journal-title":"RAIRO - Informatique Th\u00e9orique et Appl."},{"key":"8_CR7","unstructured":"Frank, A.: Some polynomial algorithms for certain graphs and hypergraphs. Congressus Numerantium No. XV, pp. 3\u201313 (1976)"},{"key":"8_CR8","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.: Some simplified NP-complete problems. Theoret. Comput. Sci. 1, 237\u2013267 (1976)","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"8_CR9","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1002\/net.3230120410","volume":"12","author":"UI Gupta","year":"1982","unstructured":"Gupta, U.I., Lee, D.T., Leung, J.Y.-T.: Efficient algorithms for interval graphs and circular-arc graphs. Networks 12(4), 459\u2013467 (1982)","journal-title":"Networks"},{"key":"8_CR10","first-page":"87","volume":"14","author":"P Heggernes","year":"2007","unstructured":"Heggernes, P., Kratsch, D.: Linear-time certifying recognition algorithms and forbidden induced subgraphs. Nord. J. Comput. 14, 87\u2013108 (2007)","journal-title":"Nord. J. Comput."},{"issue":"1","key":"8_CR11","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1137\/S0097539795286612","volume":"28","author":"S Khanna","year":"1998","unstructured":"Khanna, S., Motwani, R., Sudan, M., Vazirani, U.V.: On syntactic versus computational views of approximability. SIAM J. Comput. 28(1), 164\u2013191 (1998)","journal-title":"SIAM J. Comput."},{"key":"8_CR12","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF02289199","volume":"15","author":"RD Luce","year":"1950","unstructured":"Luce, R.D.: Connectivity and generalized cliques in sociometric group structure. Psychometrika 15, 169\u2013190 (1950)","journal-title":"Psychometrika"},{"issue":"2","key":"8_CR13","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/BF00139635","volume":"13","author":"RJ Mokken","year":"1979","unstructured":"Mokken, R.J.: Cliques, clubs and clans. Qual. Quant. 13(2), 161\u2013173 (1979)","journal-title":"Qual. Quant."},{"issue":"3","key":"8_CR14","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"CH Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43(3), 425\u2013440 (1991)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"8_CR15","doi-asserted-by":"publisher","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D Zuckerman","year":"2007","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theor. Comput. 3(1), 103\u2013128 (2007)","journal-title":"Theor. Comput."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-57586-5_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T14:47:32Z","timestamp":1710341252000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-57586-5_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319575858","9783319575865"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-57586-5_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"14 April 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithms and Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Athens","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Greece","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 May 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 May 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ciac2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.corelab.ntua.gr\/ciac2017\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}