The complexity of coloring games on perfect graphs
From MaRDI portal
Publication:1202928
DOI10.1016/0304-3975(92)90254-DzbMath0785.90119WikidataQ59568011 ScholiaQ59568011MaRDI QIDQ1202928
Dieter Kratsch, Hans L. Bodlaender
Publication date: 22 April 1993
Published in: Theoretical Computer Science (Search for Journal in Brave)
polynomial time algorithm; bipartite graphs; perfect graphs; split graphs; NP-hardness; coloring games; interval graphs; PSPACE-completeness; winning strategy; coNP-hardness; greedy-like strategy
90C60: Abstract computational complexity for mathematical programming problems
91A05: 2-person games
91A43: Games involving graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- PSPACE-Hardness of some combinatorial games
- Complexity of problems in games, graphs and algebraic equations
- Hex ist Pspace-vollständig. (Hex is Pspace-complete)
- On the complexity of some two-person perfect-information games
- The NP-completeness column: an ongoing guide
- Planar Formulae and Their Uses
- ON THE COMPLEXITY OF SOME COLORING GAMES
- Design and implementation of an efficient priority queue