An algorithmic study of switch graphs

B. Katz, I. Rutter, G.J. Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

7 Citations (Scopus)


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 languageEnglish
Pages (from-to)295-312
JournalActa Informatica
Issue number5
Publication statusPublished - 2012


Dive into the research topics of 'An algorithmic study of switch graphs'. Together they form a unique fingerprint.

Cite this