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 等数据库收录！ |
|
