Finding induced trees

DOI10.1016/j.dam.2009.02.009zbMath1227.05124OpenAlexW2013421520MaRDI QIDQ967418

Christophe Picouleau, Nicolas Derhy

Publication date: 28 April 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2009.02.009

zbMATH Keywords

polynomial time algorithminduced subgraphinduced tree\(\mathcal {NP}\)-completeness

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

MIP formulations for induced graph optimization problems: a tutorial, Maximum weighted induced forests and trees: new formulations and a computational comparative review, Large Induced Subgraphs via Triangulations and CMSO, Exact Solution Algorithms for the Chordless Cycle Problem, Finding induced paths of given parity in claw-free graphs, The \(k\)-in-a-path problem for claw-free graphs, FPT and kernelization algorithms for the induced tree problem, Induced Disjoint Paths in Claw-Free Graphs, Unnamed Item, The balanced connected subgraph problem, Induced disjoint paths in AT-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The three-in-a-tree problem
• On the complexity of testing for odd holes and induced odd paths
• Recognizing Berge graphs
• Algorithms for Perfectly Contractile Graphs
• The steiner problem in graphs
• Detecting induced subgraphs