{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:38:20Z","timestamp":1742913500373,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662531730"},{"type":"electronic","value":"9783662531747"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[[2016]]},"DOI":"10.1007\/978-3-662-53174-7_35","type":"book-chapter","created":{"date-parts":[[2016,8,4]],"date-time":"2016-08-04T10:50:06Z","timestamp":1470307806000},"page":"499-512","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Beyond Classes of Graphs with \u201cFew\u201d Minimal Separators: FPT Results Through Potential Maximal Cliques"],"prefix":"10.1007","author":[{"given":"Mathieu","family":"Liedloff","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pedro","family":"Montealegre","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ioan","family":"Todinca","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,8,5]]},"reference":[{"issue":"3","key":"35_CR1","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1142\/S0129054100000211","volume":"11","author":"A Berry","year":"2000","unstructured":"Berry, A., Bordat, J.P., Cogis, O.: Generating all the minimal separators of a graph. Int. J. Found. Comput. Sci. 11(3), 397\u2013403 (2000)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"1\u20132","key":"35_CR2","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. Theor. Comput. Sci. 209(1\u20132), 1\u201345 (1998)","journal-title":"Theor. Comput. Sci."},{"key":"35_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1007\/978-3-642-30891-8_12","volume-title":"The Multivariate Algorithmic Revolution and Beyond","author":"HL Bodlaender","year":"2012","unstructured":"Bodlaender, H.L.: Fixed-parameter tractability of treewidth and pathwidth. In: Bodlaender, H.L., Downey, R., Fomin, F.V., Marx, D. (eds.) The Multivariate Algorithmic Revolution and Beyond. LNCS, vol. 7370, pp. 196\u2013227. Springer, Heidelberg (2012)"},{"issue":"2","key":"35_CR4","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1006\/jagm.1996.0049","volume":"21","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L., Kloks, T.: Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms 21(2), 358\u2013402 (1996)","journal-title":"J. Algorithms"},{"issue":"5\u20136","key":"35_CR5","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1007\/BF01758777","volume":"7","author":"RB Borie","year":"1992","unstructured":"Borie, R.B., Gary Parker, R., Tovey, C.A.: Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families. Algorithmica 7(5\u20136), 555\u2013581 (1992)","journal-title":"Algorithmica"},{"issue":"1","key":"35_CR6","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1137\/S0097539799359683","volume":"31","author":"V Bouchitt\u00e9","year":"2001","unstructured":"Bouchitt\u00e9, V., Todinca, I.: Treewidth and minimum fill-in: grouping the minimal separators. SIAM J. Comput. 31(1), 212\u2013232 (2001)","journal-title":"SIAM J. Comput."},{"issue":"1\u20132","key":"35_CR7","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/S0304-3975(01)00007-X","volume":"276","author":"V Bouchitt\u00e9","year":"2002","unstructured":"Bouchitt\u00e9, V., Todinca, I.: Listing all potential maximal cliques of a graph. Theor. Comput. Sci. 276(1\u20132), 17\u201332 (2002)","journal-title":"Theor. Comput. Sci."},{"issue":"2\u20133","key":"35_CR8","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s10107-005-0649-5","volume":"105","author":"K Cameron","year":"2006","unstructured":"Cameron, K., Hell, P.: Independent packings in structured graphs. Math. Program. 105(2\u20133), 201\u2013213 (2006)","journal-title":"Math. Program."},{"issue":"1","key":"35_CR9","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85(1), 12\u201375 (1990)","journal-title":"Inf. Comput."},{"key":"35_CR10","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511977619","volume-title":"Graph Structure and Monadic Second-Order Logic","author":"B Courcelle","year":"2012","unstructured":"Courcelle, B., Engelfriet, J.: Graph Structure and Monadic Second-Order Logic. Cambridge University Press, Cambridge (2012)"},{"key":"35_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1007\/978-3-319-08404-6_16","volume-title":"Algorithm Theory \u2013 SWAT 2014","author":"FV Fomin","year":"2014","unstructured":"Fomin, F.V., Liedloff, M., Montealegre, P., Todinca, I.: Algorithms parameterized by vertex cover and modular width, through potential maximal cliques. In: Ravi, R., G\u00f8rtz, I.L. (eds.) SWAT 2014. LNCS, vol. 8503, pp. 182\u2013193. Springer, Heidelberg (2014)"},{"issue":"1","key":"35_CR12","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1137\/140964801","volume":"44","author":"FV Fomin","year":"2015","unstructured":"Fomin, F.V., Todinca, I., Villanger, Y.: Large induced subgraphs via triangulations and CMSO. SIAM J. Comput. 44(1), 54\u201387 (2015)","journal-title":"SIAM J. Comput."},{"key":"35_CR13","unstructured":"Fomin, F.V., Villanger, Y.: Finding induced subgraphs via minimal triangulations. In: STACS 2010, LIPIcs, pp. 383\u2013394. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2010)"},{"issue":"1\u20133","key":"35_CR14","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.apal.2004.01.007","volume":"130","author":"M Frick","year":"2004","unstructured":"Frick, M., Grohe, M.: The complexity of first-order and monadic second-order logic revisited. Ann. Pure Appl. Logic 130(1\u20133), 3\u201331 (2004)","journal-title":"Ann. Pure Appl. Logic"},{"key":"35_CR15","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"MC Golumbic","year":"1980","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)"},{"key":"35_CR16","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1016\/j.tcs.2012.03.013","volume":"511","author":"P Heggernes","year":"2013","unstructured":"Heggernes, P., van\u2019t Hof, P., Jansen, B.M.P., Kratsch, S., Villanger, Y.: Parameterized complexity of vertex deletion into perfect graph classes. Theor. Comput. Sci. 511, 172\u2013180 (2013)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"35_CR17","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1006\/jctb.1997.1788","volume":"73","author":"J Lagergren","year":"1998","unstructured":"Lagergren, J.: Upper bounds on the size of obstructions and intertwines. J. Comb. Theor. Ser. B 73(1), 7\u201340 (1998)","journal-title":"J. Comb. Theor. Ser. B"},{"issue":"7","key":"35_CR18","doi-asserted-by":"publisher","first-page":"747","DOI":"10.1016\/j.dam.2008.11.006","volume":"158","author":"F Mancini","year":"2010","unstructured":"Mancini, F.: Minimum fill-in and treewidth of split+ke and split+kv graphs. Discrete Appl. Math. 158(7), 747\u2013754 (2010)","journal-title":"Discrete Appl. Math."},{"key":"35_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/978-3-540-28639-4_8","volume-title":"Parameterized and Exact Computation","author":"D Marx","year":"2004","unstructured":"Marx, D.: Parameterized coloring problems on chordal graphs. In: Downey, R.G., Fellows, M.R., Dehne, F. (eds.) IWPEC 2004. LNCS, vol. 3162, pp. 83\u201395. Springer, Heidelberg (2004)"},{"issue":"4","key":"35_CR20","doi-asserted-by":"publisher","first-page":"747","DOI":"10.1007\/s00453-008-9233-8","volume":"57","author":"D Marx","year":"2010","unstructured":"Marx, D.: Chordal deletion is fixed-parameter tractable. Algorithmica 57(4), 747\u2013768 (2010)","journal-title":"Algorithmica"},{"issue":"2","key":"35_CR21","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/j.jctb.2004.08.001","volume":"92","author":"N Robertson","year":"2004","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XX. Wagner\u2019s conjecture. J. Comb. Theor. Ser. B 92(2), 325\u2013357 (2004). Special Issue Dedicated to Professor W.T. Tutte","journal-title":"J. Comb. Theor. Ser. B"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-53174-7_35","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T01:11:39Z","timestamp":1558314699000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-53174-7_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662531730","9783662531747"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-53174-7_35","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"5 August 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Graph-Theoretic Concepts in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Garching","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2015","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 June 2015","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 June 2015","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"41","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2015","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}