Detecting induced minors in AT-free graphs

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

zbMATH Keywords

contraction; AT-free graphs; induced minor

Mathematics Subject Classification ID

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