Exact algorithms for Kayles

DOI10.1016/J.TCS.2014.09.042MaRDI QIDQ476858zbMATH OpenOpenAlexWikidataFDO

Authors 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 algorithmsexact algorithmsgraph algorithmscombinatorial gamesindependent setsmoderately exponential time algorithms

Mathematics Subject Classification ID

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

Recommendations

• Exact algorithms for Kayles
• scientific article; zbMATH DE number 512922
• scientific article; zbMATH DE number 7199604
• Kayles and Nimbers
• Polynomial time graph families for Arc Kayles

Cites work

• scientific article; zbMATH DE number 3761989 (Why is no real title available?)
• scientific article; zbMATH DE number 3521877 (Why is no real title available?)
• A faster algorithm for dominating set analyzed by the potential method
• A measure \& conquer approach for the analysis of exact algorithms
• Compound Node-Kayles on paths
• Exact algorithms for Kayles
• Exact exponential algorithms.
• Kayles and Nimbers
• On the complexity of some two-person perfect-information games
• The complexity of satisfiability problems

Cited in

(7)

• Winner determination algorithms for graph games with matching structures
• Winner determination algorithms for graph games with matching structures
• On a class of strongly asymmetric PKA algorithms
• Games on interval and permutation graph representations
• Kayles and Nimbers
• On structural parameterizations of Node Kayles
• Exact algorithms for Kayles

This page was built for publication: Exact algorithms for Kayles

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