$K_4$-Minor-Free Induced Subgraphs of Sparse Connected Graphs

DOI10.1137/16M107712XzbMath1386.05037arXiv1605.04730OpenAlexW3100041547MaRDI QIDQ3130446

Gwenaël Joret, David R. Wood

Publication date: 22 January 2018

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1605.04730

zbMATH Keywords

transversal\(K_4\)-minorseries-parallel edges

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Connectivity (05C40)

Cites Work

• Unnamed Item
• A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
• Improved upper bounds for planarization and series-parallelization of degree-bounded graphs
• A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP
• A faster polynomial-space algorithm for Max 2-CSP
• Planarization and fragmentability of some classes of graphs
• Linear-programming design and analysis of fast algorithms for Max 2-CSP
• New exact algorithms for the 2-constraint satisfaction problem
• Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets
• A Bound on the Pathwidth of Sparse Graphs with Applications to Exact Algorithms
• Planar Induced Subgraphs of Sparse Graphs
• Graph-Theoretic Concepts in Computer Science
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques