A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Complexity issues in switching of graphs
Tekijät: Ehrenfeucht A, Hage J, Harju T, Rozenberg G
Julkaisuvuosi: 2000
Lehti:: Lecture Notes in Computer Science
Tietokannassa oleva lehden nimi: THEORY AND APPLICATION TO GRAPH TRANSFORMATIONS
Lehden akronyymi: LECT NOTES COMPUT SC
Vuosikerta: 1764
Aloitussivu: 59
Lopetussivu: 70
Sivujen määrä: 12
ISBN: 3-540-67203-6
ISSN: 0302-9743
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali