$K_4$-Minor-Free Induced Subgraphs of Sparse Connected Graphs
From MaRDI portal
Publication:3130446
DOI10.1137/16M107712XzbMath1386.05037arXiv1605.04730OpenAlexW3100041547MaRDI QIDQ3130446
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
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