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.
Original language | English |
---|---|
Pages (from-to) | 295-312 |
Journal | Acta Informatica |
Volume | 49 |
Issue number | 5 |
DOIs | |
Publication status | Published - 2012 |