Detecting induced star-like minors in polynomial time

DOI10.1016/j.jda.2012.11.002zbMath1267.68122MaRDI QIDQ2376792

Daniël Paulusma, Jiří Fiala, Marcin Kaminski

Publication date: 24 June 2013

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2012.11.002

zbMATH Keywords

tree; computational complexity; induced minor

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C83: Graph minors

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Induced Disjoint Paths in Claw-Free Graphs, Graph editing to a fixed target, Detecting induced minors in AT-free graphs

Cites Work

• Unnamed Item
• On graph contractions and induced minors
• Corrigendum to: On the complexity of testing for odd holes and induced odd paths
• 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
• Edge Contractions in Subclasses of Chordal Graphs
• Contracting a Chordal Graph to a Split Graph or a Tree
• Finding Contractions and Induced Minors in Chordal Graphs via Disjoint Paths
• The computational complexity of graph contractions I: Polynomially solvable and NP-complete cases
• Contractions of Planar Graphs in Polynomial Time
• The computational complexity of graph contractions II: Two tough polynomially solvable cases
• Contractibility and NP-completeness