@inproceedings{03707c9abf864456994a685b3e2441d1,
title = "Complexity Issues in Switching of Graphs",
abstract = "In the context of graph transformations we look at the operation of switching, which can be viewed as an elegant method for realizing global transformations of graphs through local transformations of the vertices. We compare the complexity of a number of problems on graphs with the complexity of these problems extended to the set of switches of a graph. Within this framework, we prove a modification of Yannakakis{\textquoteright} result and use it to show NP-completeness for the embedding problem. Finally we prove NP-completeness for the 3-colourability problem.",
keywords = "Wiskunde en Informatica (WIIN), Mathematics, Informatica, Landbouwwetenschappen, Natuurwetenschappen",
author = "Andrzej Ehrenfeucht and Jurriaan Hage and Tero Harju and Grzegorz Rozenberg",
year = "2000",
doi = "10.1007/978-3-540-46464-8_5",
language = "English",
isbn = "9783540672036",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "59--70",
editor = "H. Ehrig and G. Engels and H.-J. Kreowski and G. Rozenberg",
booktitle = "Theory and Application of Graph Transformations. TAGT 1998",
address = "United States",
}