Complexity Issues in Switching of Graphs

Andrzej Ehrenfeucht, Jurriaan Hage, Tero Harju, Grzegorz Rozenberg

Research output: Chapter in Book/Report/Conference proceedingConference contribution

17 Citations (Scopus)

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.
Original languageEnglish
Title of host publicationTheory and Application of Graph Transformations. TAGT 1998
EditorsH. Ehrig, G. Engels, H.-J. Kreowski, G. Rozenberg
PublisherSpringer
Pages59-70
Number of pages12
ISBN (Electronic)9783540464648
ISBN (Print)9783540672036
DOIs
Publication statusPublished - 2000

Publication series

NameLecture Notes in Computer Science
Volume1764
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Keywords

  • Wiskunde en Informatica (WIIN)
  • Mathematics
  • Informatica
  • Landbouwwetenschappen
  • Natuurwetenschappen

Fingerprint

Dive into the research topics of 'Complexity Issues in Switching of Graphs'. Together they form a unique fingerprint.

Cite this