Eliminating graphs by means of parallel knock-out schemes

DOI10.1016/j.dam.2006.04.034zbMath1109.05091OpenAlexW2071675546WikidataQ60488755 ScholiaQ60488755MaRDI QIDQ867852

Rastislav Královič, Fedor V. Fomin, Gerhard J. Woeginger, Hajo J. Broersma

Publication date: 19 February 2007

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

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

zbMATH Keywords

treecomputational complexitydynamic programmingclaw-free graphHamiltonian cycleperfect matchingknock-out number

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

The computational complexity of the parallel knock-out problem ⋮ Path factors and parallel knock-out schemes of almost claw-free graphs ⋮ Upper bounds and algorithms for parallel knock-out numbers ⋮ Knocking out \(P_k\)-free graphs

Cites Work

• Matching theory
• Claw-free graphs---a survey
• The Computational Complexity of the Parallel Knock-Out Problem
• Graphs with 1-Factors
• Parallel Knockouts in the Complete Graph
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Eliminating graphs by means of parallel knock-out schemes