Kayles on special classes of graphs — An application of Sprague-Grundy theory

Hans Bodlaender

doi:10.1007/3-540-56402-0_39

Kayles on special classes of graphs — An application of Sprague-Grundy theory

Hans Bodlaender

extern

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic › peer-review

Abstract

Kayles is the game, where two players alternately choose a vertex that has not been chosen before nor is adjacent to an already chosen vertex from a given graph. The last player that choses a vertex wins the game. We show, with help of Sprague-Grundy theory, that the problem to determine which player has a winning strategy for a given graph, can be solved in O(n^3) time on interval graphs, on circular arc graphs, on permutation graphs, and on co-comparability graphs and in O(n^1.631) time on cographs. For general graphs, the problem is known to be PSPACE-complete, but can be solved in time, polynomial in the number of isolatable sets of vertices of the graph.

Original language	English
Title of host publication	Graph-Theoretic Concepts in Computer Science
Subtitle of host publication	18th International Workshop, WG '92 Wiesbaden-Naurod, Germany, June 18–20, 1992 Proceedings
Editors	Ernst W. Mayr
Publisher	Springer
Pages	90-102
Number of pages	13
Volume	657
ISBN (Electronic)	978-3-540-47554-5
ISBN (Print)	978-3-540-56402-7
DOIs	https://doi.org/10.1007/3-540-56402-0_39
Publication status	Published - 1993
Externally published	Yes

Publication series

Name	Lecture Notes in Computer Science

Access to Document

10.1007/3-540-56402-0_39

http://dx.doi.org/10.1007/3-540-56402-0_39

Cite this

Bodlaender, H. (1993). Kayles on special classes of graphs — An application of Sprague-Grundy theory. In E. W. Mayr (Ed.), Graph-Theoretic Concepts in Computer Science: 18th International Workshop, WG '92 Wiesbaden-Naurod, Germany, June 18–20, 1992 Proceedings (Vol. 657, pp. 90-102). (Lecture Notes in Computer Science). Springer. https://doi.org/10.1007/3-540-56402-0_39

@inbook{1e6fd933ca3b4aa099e36fb4c9f0d692,

title = "Kayles on special classes of graphs — An application of Sprague-Grundy theory",

abstract = "Kayles is the game, where two players alternately choose a vertex that has not been chosen before nor is adjacent to an already chosen vertex from a given graph. The last player that choses a vertex wins the game. We show, with help of Sprague-Grundy theory, that the problem to determine which player has a winning strategy for a given graph, can be solved in O(n^3) time on interval graphs, on circular arc graphs, on permutation graphs, and on co-comparability graphs and in O(n^1.631) time on cographs. For general graphs, the problem is known to be PSPACE-complete, but can be solved in time, polynomial in the number of isolatable sets of vertices of the graph.",

author = "Hans Bodlaender",

year = "1993",

doi = "10.1007/3-540-56402-0_39",

language = "English",

isbn = "978-3-540-56402-7",

volume = "657",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "90--102",

editor = "Mayr, {Ernst W.}",

booktitle = "Graph-Theoretic Concepts in Computer Science",

}

Kayles on special classes of graphs — An application of Sprague-Grundy theory. / Bodlaender, Hans.
Graph-Theoretic Concepts in Computer Science: 18th International Workshop, WG '92 Wiesbaden-Naurod, Germany, June 18–20, 1992 Proceedings. ed. / Ernst W. Mayr. Vol. 657 Springer, 1993. p. 90-102 (Lecture Notes in Computer Science).

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic › peer-review

TY - CHAP

T1 - Kayles on special classes of graphs — An application of Sprague-Grundy theory

AU - Bodlaender, Hans

PY - 1993

Y1 - 1993

N2 - Kayles is the game, where two players alternately choose a vertex that has not been chosen before nor is adjacent to an already chosen vertex from a given graph. The last player that choses a vertex wins the game. We show, with help of Sprague-Grundy theory, that the problem to determine which player has a winning strategy for a given graph, can be solved in O(n^3) time on interval graphs, on circular arc graphs, on permutation graphs, and on co-comparability graphs and in O(n^1.631) time on cographs. For general graphs, the problem is known to be PSPACE-complete, but can be solved in time, polynomial in the number of isolatable sets of vertices of the graph.

AB - Kayles is the game, where two players alternately choose a vertex that has not been chosen before nor is adjacent to an already chosen vertex from a given graph. The last player that choses a vertex wins the game. We show, with help of Sprague-Grundy theory, that the problem to determine which player has a winning strategy for a given graph, can be solved in O(n^3) time on interval graphs, on circular arc graphs, on permutation graphs, and on co-comparability graphs and in O(n^1.631) time on cographs. For general graphs, the problem is known to be PSPACE-complete, but can be solved in time, polynomial in the number of isolatable sets of vertices of the graph.

U2 - 10.1007/3-540-56402-0_39

DO - 10.1007/3-540-56402-0_39

M3 - Chapter

SN - 978-3-540-56402-7

VL - 657

T3 - Lecture Notes in Computer Science

SP - 90

EP - 102

BT - Graph-Theoretic Concepts in Computer Science

A2 - Mayr, Ernst W.

PB - Springer

ER -

Kayles on special classes of graphs — An application of Sprague-Grundy theory

Abstract

Publication series

Access to Document

Fingerprint

Cite this