Detecting induced minors in AT-free graphs
From MaRDI portal
Publication:390909
DOI10.1016/j.tcs.2013.02.029zbMath1296.05183OpenAlexW1990607348MaRDI 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
Analysis of algorithms and problem complexity (68Q25) Graph minors (05C83) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (4)
Graph editing to a fixed target ⋮ Combing a Linkage in an Annulus ⋮ Contracting bipartite graphs to paths and cycles ⋮ Contracting bipartite graphs to paths and cycles
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
This page was built for publication: Detecting induced minors in AT-free graphs
