An algorithmic study of switch graphs

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

doi:10.1007/s00236-012-0160-4

An algorithmic study of switch graphs

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

Discrete Mathematics

Research output: Contribution to journal › Article › Academic › peer-review

7 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 language	English
Pages (from-to)	295-312
Journal	Acta Informatica
Volume	49
Issue number	5
DOIs	https://doi.org/10.1007/s00236-012-0160-4
Publication status	Published - 2012

Access to Document

10.1007/s00236-012-0160-4

Cite this

@article{0dd7e2b7fe884517ad7754f12938b26f,

title = "An algorithmic study of switch graphs",

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.",

author = "B. Katz and I. Rutter and G.J. Woeginger",

year = "2012",

doi = "10.1007/s00236-012-0160-4",

language = "English",

volume = "49",

pages = "295--312",

journal = "Acta Informatica",

issn = "0001-5903",

publisher = "Springer",

number = "5",

}

TY - JOUR

T1 - An algorithmic study of switch graphs

AU - Katz, B.

AU - Rutter, I.

AU - Woeginger, G.J.

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

U2 - 10.1007/s00236-012-0160-4

DO - 10.1007/s00236-012-0160-4

M3 - Article

VL - 49

SP - 295

EP - 312

JO - Acta Informatica

JF - Acta Informatica

SN - 0001-5903

IS - 5

ER -

An algorithmic study of switch graphs

Abstract

Access to Document

Fingerprint

Cite this