{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T09:52:28Z","timestamp":1764841948614,"version":"3.37.3"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2017,2,27]],"date-time":"2017-02-27T00:00:00Z","timestamp":1488153600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-15-CE40-0009"],"award-info":[{"award-number":["ANR-15-CE40-0009"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,4]]},"DOI":"10.1007\/s00453-017-0297-1","type":"journal-article","created":{"date-parts":[[2017,2,27]],"date-time":"2017-02-27T09:47:44Z","timestamp":1488188864000},"page":"1146-1169","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["Algorithms Parameterized by Vertex Cover and Modular Width, Through Potential Maximal Cliques"],"prefix":"10.1007","volume":"80","author":[{"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[]},{"given":"Mathieu","family":"Liedloff","sequence":"additional","affiliation":[]},{"given":"Pedro","family":"Montealegre","sequence":"additional","affiliation":[]},{"given":"Ioan","family":"Todinca","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,2,27]]},"reference":[{"key":"297_CR1","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S Arnborg","year":"1991","unstructured":"Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. J. Algorithms 12, 308\u2013340 (1991)","journal-title":"J. Algorithms"},{"key":"297_CR2","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25, 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"key":"297_CR3","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/j.dam.2004.01.008","volume":"145","author":"HL Bodlaender","year":"2005","unstructured":"Bodlaender, H.L., Fomin, F.V.: Tree decompositions with small cost. Discrete Appl. Math. 145, 143\u2013154 (2005)","journal-title":"Discrete Appl. Math."},{"key":"297_CR4","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1007\/s00453-003-1026-5","volume":"36","author":"HL Bodlaender","year":"2003","unstructured":"Bodlaender, H.L., Rotics, U.: Computing the treewidth and the minimum fill-in with the modular decomposition. Algorithmica 36, 375\u2013408 (2003)","journal-title":"Algorithmica"},{"key":"297_CR5","doi-asserted-by":"crossref","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, 212\u2013232 (2001)","journal-title":"SIAM J. Comput."},{"key":"297_CR6","doi-asserted-by":"crossref","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, 17\u201332 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"297_CR7","doi-asserted-by":"crossref","unstructured":"Chapelle, M., Liedloff, M., Todinca, I., and Villanger, Y.: Treewidth and pathwidth parameterized by the vertex cover number. In: WADS, Dehne, F., Solis-Oba, R., Sack, J.-R. (eds.) vol.\u00a08037 of Lecture Notes in Computer Science, pp. 232\u2013243. Springer, Berlin (2013)","DOI":"10.1007\/978-3-642-40104-6_21"},{"key":"297_CR8","doi-asserted-by":"crossref","first-page":"3736","DOI":"10.1016\/j.tcs.2010.06.026","volume":"411","author":"J Chen","year":"2010","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theor. Comput. Sci. 411, 3736\u20133756 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"297_CR9","doi-asserted-by":"crossref","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, 12\u201375 (1990)","journal-title":"Inf. Comput."},{"key":"297_CR10","doi-asserted-by":"crossref","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":"297_CR11","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. 33, 125\u2013150 (2000)","journal-title":"Theory Comput. Syst."},{"key":"297_CR12","doi-asserted-by":"crossref","first-page":"940","DOI":"10.1007\/s00453-012-9707-6","volume":"68","author":"M Cygan","year":"2014","unstructured":"Cygan, M., Lokshtanov, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: On cutwidth parameterized by vertex cover. Algorithmica 68, 940\u2013953 (2014)","journal-title":"Algorithmica"},{"key":"297_CR13","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/S0166-218X(99)00179-1","volume":"98","author":"JS Deogun","year":"1999","unstructured":"Deogun, J.S., Kloks, T., Kratsch, D., M\u00fcller, H.: On the vertex ranking problem for trapezoid, circular-arc and other graphs. Discrete Appl. Math. 98, 39\u201363 (1999)","journal-title":"Discrete Appl. Math."},{"key":"297_CR14","doi-asserted-by":"crossref","unstructured":"Fellows, M.R., Lokshtanov, D., Misra, N., Rosamond, F.A., Saurabh, S.: Graph layout problems parameterized by vertex cover. In: ISAAC, Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) vol.\u00a05369 of Lecture Notes in Computer Science, pp. 294\u2013305. Springer, Berlin (2008)","DOI":"10.1007\/978-3-540-92182-0_28"},{"key":"297_CR15","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1007\/s00453-014-9914-4","volume":"73","author":"FV Fomin","year":"2015","unstructured":"Fomin, F.V., Giannopoulou, A.C., Pilipczuk, M.: Computing tree-depth faster than $$2^n$$ 2 n . Algorithmica 73, 202\u2013216 (2015)","journal-title":"Algorithmica"},{"key":"297_CR16","doi-asserted-by":"crossref","first-page":"1058","DOI":"10.1137\/050643350","volume":"38","author":"FV Fomin","year":"2008","unstructured":"Fomin, F.V., Kratsch, D., Todinca, I., Villanger, Y.: Exact algorithms for treewidth and minimum fill-in. SIAM J. Comput. 38, 1058\u20131079 (2008)","journal-title":"SIAM J. Comput."},{"key":"297_CR17","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Liedloff, M., Montealegre-Barba, P., and Todinca, I.: Algorithms parameterized by vertex cover and modular width, through potential maximal cliques. In: Ravi, R., L. G\u00f8rtz, I. (eds.) Algorithm Theory\u2014SWAT 2014\u201414th Scandinavian Symposium and Workshops, Copenhagen, Denmark, July 2-4, 2014. Proceedings, vol.\u00a08503 of Lecture Notes in Computer Science, pp.\u00a0182\u2013193. Springer, Berlin (2014)","DOI":"10.1007\/978-3-319-08404-6_16"},{"key":"297_CR18","doi-asserted-by":"crossref","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, 54\u201387 (2015)","journal-title":"SIAM J. Comput."},{"key":"297_CR19","unstructured":"Fomin, F.V., Villanger, Y.: Finding induced subgraphs via minimal triangulations. In: STACS, Marion, J.-Y., Schwentick, T. (eds.) vol.\u00a05 of LIPIcs, Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik, pp.\u00a0383\u2013394 (2010)"},{"key":"297_CR20","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1007\/s00493-012-2536-z","volume":"32","author":"FV Fomin","year":"2012","unstructured":"Fomin, F.V., Villanger, Y.: Treewidth computation and extremal combinatorics. Combinatorica 32, 289\u2013308 (2012)","journal-title":"Combinatorica"},{"key":"297_CR21","doi-asserted-by":"crossref","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, 3\u201331 (2004)","journal-title":"Ann. Pure Appl. Logic"},{"key":"297_CR22","doi-asserted-by":"crossref","unstructured":"Gajarsk\u00fd, J., Lampis, M., Ordyniak, S.: Parameterized algorithms for modular-width. In: Parameterized and Exact Computation\u20148th International Symposium, IPEC 2013, Lecture Notes in Computer Science, pp.\u00a0163\u2013176 (2013)","DOI":"10.1007\/978-3-319-03898-8_15"},{"key":"297_CR23","doi-asserted-by":"crossref","unstructured":"Gysel, R.: Minimal triangulation algorithms for perfect phylogeny problems. In: Dediu, A.\u00a0H., Mart\u00edn-Vide, C., Sierra-Rodr\u00edguez, J.\u00a0L., Truthe, B. (eds.) Language and Automata Theory and Applications\u20148th International Conference, LATA 2014, Madrid, Spain, March 10\u201314, 2014. Proceedings, vol.\u00a08370 of Lecture Notes in Computer Science, pp.\u00a0421\u2013432. Springer, Berlin (2014)","DOI":"10.1007\/978-3-319-04921-2_34"},{"key":"297_CR24","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/s00453-011-9554-x","volume":"64","author":"M Lampis","year":"2012","unstructured":"Lampis, M.: Algorithmic meta-theorems for restrictions of treewidth. Algorithmica 64, 19\u201337 (2012)","journal-title":"Algorithmica"},{"key":"297_CR25","unstructured":"Liedloff, M., Montealegre-Barba, P., Todinca, I.: Beyond classes of graphs with \u201cfew\u201d minimal separators: FPT results through potential maximal cliques. In: Graph-Theoretic Concepts in Computer Science, 41st International Workshop, Proceedings of WG 2015, Munich, (2015) (To appear)"},{"key":"297_CR26","doi-asserted-by":"crossref","first-page":"820","DOI":"10.1016\/j.dam.2009.10.007","volume":"158","author":"D Lokshtanov","year":"2010","unstructured":"Lokshtanov, D.: On the complexity of computing treelength. Discrete Appl. Math. 158, 820\u2013827 (2010)","journal-title":"Discrete Appl. Math."},{"key":"297_CR27","doi-asserted-by":"crossref","unstructured":"Ne\u0161et\u0159il, J., de\u00a0Mendez, P.O.: Sparsity\u2014Graphs, Structures, and Algorithms, vol. 28 of Algorithms and combinatorics, Springer, 2012.","DOI":"10.1007\/978-3-642-27875-4"},{"key":"297_CR28","doi-asserted-by":"crossref","unstructured":"Reidl, F., Rossmanith, P., Villaamil, F.S., Sikdar, S.: A faster parameterized algorithm for treedepth. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) Automata, Languages, and Programming\u201441st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, vol.\u00a08572 of Lecture Notes in Computer Science, pp.\u00a0931\u2013942. Springer, Berlin (2014)","DOI":"10.1007\/978-3-662-43948-7_77"},{"key":"297_CR29","unstructured":"Skodinis, K.: Efficient analysis of graphs with small minimal separators. In: Widmayer, P., Neyer, G., Eidenbenz, S. (eds.) Graph-Theoretic Concepts in Computer Science, 25th International Workshop, WG \u201999, Ascona, Switzerland, June 17\u201319, 1999, Proceedings, vol.\u00a01665 of Lecture Notes in Computer Science, pp. 155\u2013166. Springer, Berlin (1999)"},{"key":"297_CR30","doi-asserted-by":"crossref","unstructured":"Tedder, M., Corneil, D.G., Habib, M., Paul, C.: Simpler linear-time modular decomposition via recursive factorizing permutations. In: ICALP (1) Automata, Languages and Programming, 35th International Colloquium, Lecture Notes in Computer Science, pp.\u00a0634\u2013645 (2008)","DOI":"10.1007\/978-3-540-70575-8_52"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0297-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0297-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0297-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,19]],"date-time":"2019-09-19T00:19:36Z","timestamp":1568852376000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0297-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,2,27]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,4]]}},"alternative-id":["297"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0297-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2017,2,27]]}}}