Detecting induced star-like minors in polynomial time

DOI10.1016/J.JDA.2012.11.002MaRDI QIDQ2376792zbMATH OpenOpenAlexFDO

Authors Daniël Paulusma, Jiří Fiala, Marcin Kamiński

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

treecomputational complexityinduced minor

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph minors (05C83)

Recommendations

• Detecting induced minors in AT-free graphs
• Detecting induced minors in AT-free graphs
• The complexity of induced minors and related problems
• scientific article; zbMATH DE number 4094810
• On graph contractions and induced minors

Cites work

• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• Contractibility and NP-completeness
• Contracting a chordal graph to a split graph or a tree
• Contractions of Planar Graphs in Polynomial Time
• Corrigendum to: On the complexity of testing for odd holes and induced odd paths
• Edge contractions in subclasses of chordal graphs
• Finding contractions and induced minors in chordal graphs via disjoint paths
• Graph minors. XIII: The disjoint paths problem
• On graph contractions and induced minors
• On the complexity of finding iso- and other morphisms for partial \(k\)- trees
• 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

(6)

• scientific article; zbMATH DE number 4094810 (Why is no real title available?)
• Quasipolynomiality of the Smallest Missing Induced Subgraph
• Induced disjoint paths in claw-free graphs
• Graph editing to a fixed target
• Detecting induced minors in AT-free graphs
• Detecting induced minors in AT-free graphs

This page was built for publication: Detecting induced star-like minors in polynomial time

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