Switching graphs

J.F. Groote, B. Ploeger

Research output: Contribution to journalArticleAcademicpeer-review

5 Citations (Scopus)
1 Downloads (Pure)

Abstract

Switching graphs are graphs that contain switches. A switch is a pair of edges that start in the same vertex and of which precisely one edge is enabled at any time. By using a Boolean function called a switch setting, the switches in a switching graph can be put in a fixed direction to obtain an ordinary graph. For many problems, switching graphs are a remarkable straightforward and natural model, but they have hardly been studied. We study the complexity of several natural questions in switching graphs of which some are polynomial, and others are NP-complete. We started investigating switching graphs because they turned out to be a natural framework for studying the problem of solving Boolean equation systems, which is equivalent to model checking of the modal µ-calculus and deciding the winner in parity games. We give direct, polynomial encodings of Boolean equation systems in switching graphs and vice versa, and prove correctness of the encodings.
Original languageEnglish
Pages (from-to)869-886
JournalInternational Journal of Foundations of Computer Science
Volume20
Issue number5
DOIs
Publication statusPublished - 2009

Fingerprint

Dive into the research topics of 'Switching graphs'. Together they form a unique fingerprint.

Cite this