We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
An algorithmic study of switch graphs.
- Authors
Katz, Bastian; Rutter, Ignaz; Woeginger, Gerhard
- Abstract
We derive a variety of results on the algorithmics of switch graphs. On the negative side we prove hardness of the following problems: Given a switch graph, does it possess a bipartite/planar/triangle-free/Eulerian configuration? On the positive side we design fast algorithms for several connectivity problems in undirected switch graphs, and for recognizing acyclic configurations in directed switch graphs.
- Subjects
ALGORITHMS; GRAPH theory; PROOF theory; GRAPH connectivity; BIPARTITE graphs; EULERIAN graphs; ACYCLIC model
- Publication
Acta Informatica, 2012, Vol 49, Issue 5, p295
- ISSN
0001-5903
- Publication type
Article
- DOI
10.1007/s00236-012-0160-4