Fast Minor Testing in Planar Graphs

DOI10.1007/978-3-642-15775-2_9zbMath1287.05141OpenAlexW2097530134WikidataQ60488611 ScholiaQ60488611MaRDI QIDQ3586454

Fedor V. Fomin, Dimitrios M. Thilikos, Ignasi Sau, Isolde Adler, Frederic Dorn

Publication date: 6 September 2010

Published in: Algorithms – ESA 2010 (Search for Journal in Brave)

Full work available at URL: https://hal-lirmm.ccsd.cnrs.fr/lirmm-00736769/file/ark__67375_HCB-M3SJ9JPF-N.pdf

zbMATH Keywords

dynamic programmingplanar graphsparameterized complexitygraph minorsbranchwidth

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Graph Minors and Parameterized Algorithm Design ⋮ Faster parameterized algorithms for minor containment ⋮ Fast minor testing in planar graphs ⋮ The Parameterized Complexity of Graph Cyclability