An algorithmic study of switch graphs

DOI10.1007/s00236-012-0160-4zbMath1251.05169OpenAlexW2141067463MaRDI QIDQ715049

Gerhard J. Woeginger, Ignaz Rutter, Bastian Katz

Publication date: 15 October 2012

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00236-012-0160-4

zbMATH Keywords

acyclic configurations in directed switch graphsconnectivity problems in undirected switch graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items

Unnamed Item, Clustered planarity testing revisited, ARRIVAL: A Zero-Player Graph Game in NP ∩ coNP, ARRIVAL: Next Stop in CLS, Reachability Switching Games, Did the train reach its destination: the complexity of finding a witness

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• General factors of graphs
• The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
• Optimal Binary Space Partitions in the Plane
• The Simple Reachability Problem in Switch Graphs
• SWITCHING GRAPHS
• On Representatives of Subsets
• An Algorithmic Study of Switch Graphs
• Combinatorial optimization. Theory and algorithms.