Exact algorithms for Kayles

DOI10.1016/j.tcs.2014.09.042zbMath1305.05143OpenAlexW1970560697WikidataQ59567437 ScholiaQ59567437MaRDI QIDQ476858

Hans L. Bodlaender, Dieter Kratsch, Sjoerd T. Timmer

Publication date: 2 December 2014

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.09.042

zbMATH Keywords

analysis of algorithmsgraph algorithmsindependent setscombinatorial gamesexact algorithmsmoderately exponential time algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) 2-person games (91A05) Games involving graphs (91A43) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial games (91A46) Games on graphs (graph-theoretic aspects) (05C57)

Related Items (4)

Winner determination algorithms for graph games with matching structures ⋮ Games on interval and permutation graph representations ⋮ On structural parameterizations of Node Kayles ⋮ Winner determination algorithms for graph games with matching structures

Cites Work

• Unnamed Item
• Unnamed Item
• Exact exponential algorithms.
• Compound Node-Kayles on paths
• On the complexity of some two-person perfect-information games
• A Faster Algorithm for Dominating Set Analyzed by the Potential Method
• Exact Algorithms for Kayles
• Kayles and Nimbers
• A measure & conquer approach for the analysis of exact algorithms
• The complexity of satisfiability problems

This page was built for publication: Exact algorithms for Kayles