An algorithmic study of switch graphs |
| |
Authors: | Bastian Katz Ignaz Rutter Gerhard Woeginger |
| |
Affiliation: | 1. Faculty of Informatics, Karlsruhe Institute of Technology (KIT), Karlsruhe, Germany 2. Department of Mathematics and Computer Science, TU Eindhoven, Eindhoven, The Netherlands
|
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|