Detecting induced minors in AT-free graphs

DOI10.1016/J.TCS.2013.02.029MaRDI QIDQ390909zbMATH OpenOpenAlexFDO

Authors 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

contractionAT-free graphsinduced minor

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph minors (05C83)

Recommendations

• Detecting induced minors in AT-free graphs
• On graph contractions and induced minors
• Detecting induced star-like minors in polynomial time
• Detecting fixed patterns in chordal graphs in polynomial time

Cites work

• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• A note on contracting claw-free graphs
• Approximating the Bandwidth for Asteroidal Triple-Free Graphs
• Asteroidal Triple-Free Graphs
• Contractibility and NP-completeness
• Contraction checking in graphs on surfaces
• Detecting fixed patterns in chordal graphs in polynomial time
• Detecting induced star-like minors in polynomial time
• Finding topological subgraphs is fixed-parameter tractable
• Graph minors. XIII: The disjoint paths problem
• Graph theory
• Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs
• On graph contractions and induced minors
• On the complexity of finding iso- and other morphisms for partial \(k\)- trees
• Partitioning graphs into connected parts
• Representation of a finite graph by a set of intervals on the real line
• The Decision Problem for a Class of First‐Order Formulas in Which all Disjunctions are Binary
• The complexity of induced minors and related problems
• 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

Cited in

(9)

• Detecting induced star-like minors in polynomial time
• Compound logics for modification problems
• Contracting bipartite graphs to paths and cycles
• Induced minor models. I: Structural properties and algorithmic consequences
• Graph editing to a fixed target
• On graph contractions and induced minors
• Combing a Linkage in an Annulus
• Contracting bipartite graphs to paths and cycles
• Detecting induced minors in AT-free graphs

This page was built for publication: Detecting induced minors in AT-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q390909)