Detecting induced minors in AT-free graphs
From MaRDI portal
Publication:390909
DOI10.1016/j.tcs.2013.02.029zbMath1296.05183MaRDI QIDQ390909
Petr A. Golovach, Dieter Kratsch, Daniël Paulusma
Publication date: 9 January 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2013.02.029
68Q25: Analysis of algorithms and problem complexity
05C83: Graph minors
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Contracting bipartite graphs to paths and cycles, Contracting bipartite graphs to paths and cycles, Combing a Linkage in an Annulus, Graph editing to a fixed target
Cites Work
- On graph contractions and induced minors
- Partitioning graphs into connected parts
- On the complexity of finding iso- and other morphisms for partial \(k\)- trees
- The complexity of induced minors and related problems
- Graph minors. XIII: The disjoint paths problem
- Induced disjoint paths in AT-free graphs
- Detecting fixed patterns in chordal graphs in polynomial time
- Detecting induced star-like minors in polynomial time
- Representation of a finite graph by a set of intervals on the real line
- The computational complexity of graph contractions I: Polynomially solvable and NP-complete cases
- The computational complexity of graph contractions II: Two tough polynomially solvable cases
- Contractibility and NP-completeness
- Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs
- Asteroidal Triple-Free Graphs
- Approximating the Bandwidth for Asteroidal Triple-Free Graphs
- Finding topological subgraphs is fixed-parameter tractable
- The Decision Problem for a Class of First‐Order Formulas in Which all Disjunctions are Binary
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item