The computational complexity of the parallel knock-out problem

DOI10.1016/J.TCS.2007.11.021MaRDI QIDQ2481963zbMATHOpenAlexFDO

Authors Matthew Johnson, Daniël Paulusma, Iain Stewart, Hajo Broersma

Publication date 15 April 2008

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL http://dro.dur.ac.uk/5000/1/5000.pdf

zbMATH Keywords

computational complexitygraphsparallel knock-out

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• The Computational Complexity of the Parallel Knock-Out Problem
• Mathematical Foundations of Computer Science 2004
• Eliminating graphs by means of parallel knock-out schemes
• Upper Bounds and Algorithms for Parallel Knock-Out Numbers
• Upper bounds and algorithms for parallel knock-out numbers

Cites work

• scientific article; zbMATH DE number 68918 (Why is no real title available?)
• scientific article; zbMATH DE number 3503283 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1194938 (Why is no real title available?)
• scientific article; zbMATH DE number 4189769 (Why is no real title available?)
• Eliminating graphs by means of parallel knock-out schemes
• Graph theory
• Parallel Knockouts in the Complete Graph
• The Factorization of Linear Graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

Cited in

(8)

• Knocking out \(P_k\)-free graphs
• Анализ сложности алгоритма параллельного поиска “золотой” коллизии
• Mathematical Foundations of Computer Science 2004
• Eliminating graphs by means of parallel knock-out schemes
• The Computational Complexity of the Parallel Knock-Out Problem
• Path factors and parallel knock-out schemes of almost claw-free graphs
• Black-box Complexity of Parallel Search with Distributed Populations
• Upper bounds and algorithms for parallel knock-out numbers

This page was built for publication: The computational complexity of the parallel knock-out problem

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