A1 Refereed original research article in a scientific journal
Complexity issues in switching of graphs
Authors: Ehrenfeucht A, Hage J, Harju T, Rozenberg G
Publication year: 2000
Journal:: Lecture Notes in Computer Science
Journal name in source: THEORY AND APPLICATION TO GRAPH TRANSFORMATIONS
Journal acronym: LECT NOTES COMPUT SC
Volume: 1764
First page : 59
Last page: 70
Number of pages: 12
ISBN: 3-540-67203-6
ISSN: 0302-9743
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' result and use it to show NP-completeness for the embedding problem. Finally we prove NP-completeness for the 3-colourability problem.
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' result and use it to show NP-completeness for the embedding problem. Finally we prove NP-completeness for the 3-colourability problem.
UTU Research Portal