An algorithmic study of switch graphs

Research output: Contribution to journalArticleAcademicpeer-review

6 Citations (Scopus)

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

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

Cite this