Faster parameterized algorithms for minor containment

DOI10.1007/978-3-642-13731-0_31zbMATH Open1285.68206DBLPconf/swat/AdlerDFST10OpenAlexW2123988662WikidataQ60488615 ScholiaQ60488615MaRDI QIDQ3569902FDOQ3569902

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

Publication date: 22 June 2010

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-13731-0_31

Recommendations

• Faster parameterized algorithms for minor containment
• Fast minor testing in planar graphs
• Branch decompositions and minor containment
• Catalan structures and dynamic programming in \(H\)-minor-free graphs
• Fast minor testing in planar graphs

zbMATH Keywords

dynamic programminggraph minorsparameterized complexitygraphs on surfacesbranchwidth

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Graph minors (05C83)

Cited In (10)

• Square roots of minor closed graph classes
• Fast minor testing in planar graphs
• Branch decompositions and minor containment
• Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications
• Faster parameterized algorithms for minor containment
• Irrelevant vertices for the planar disjoint paths problem
• Solving SAT (and MaxSAT) with a quantum annealer: foundations, encodings, and preliminary results
• Square roots of minor closed graph classes
• Quickly deciding minor-closed parameters in general graphs
• Dynamic programming for graphs on surfaces

This page was built for publication: Faster parameterized algorithms for minor containment

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3569902)