Euler Graphs, Triangle-Free Graphs and Bipartite Graphs in Switching Classes

Jurriaan Hage; Tero Harju; Emo Welzl

doi:10.1007/3-540-45832-8_13

Euler Graphs, Triangle-Free Graphs and Bipartite Graphs in Switching Classes

Jurriaan Hage, Tero Harju, Emo Welzl

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

8 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. A switching class is then a set of graphs obtainable from a given start graph by applying the switching operation.

Continuing the line of research in Ehrenfeucht et al. we consider the problem of detecting three kinds of graphs in switching classes. For all three we find algorithms running in time polynomial in the number of vertices in the graphs, although switching classes contain exponentially many graphs.

Original language	English
Title of host publication	Graph Transformation. ICGT 2002
Editors	A. Corradini, H. Ehrig, H.-J. Kreowski, G. Rozenberg
Publisher	Springer
Pages	48-60
Number of pages	13
ISBN (Electronic)	9783540458326
ISBN (Print)	9783540443100
DOIs	https://doi.org/10.1007/3-540-45832-8_13
Publication status	Published - 2002

Publication series

Name	Lecture Notes in Computer Science
Volume	2505
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Access to Document

10.1007/3-540-45832-8_13

Cite this

@inproceedings{6b908dbb7aea45a08177e03b1ccd076a,

title = "Euler Graphs, Triangle-Free Graphs and Bipartite Graphs in Switching Classes",

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. A switching class is then a set of graphs obtainable from a given start graph by applying the switching operation.Continuing the line of research in Ehrenfeucht et al. we consider the problem of detecting three kinds of graphs in switching classes. For all three we find algorithms running in time polynomial in the number of vertices in the graphs, although switching classes contain exponentially many graphs.",

author = "Jurriaan Hage and Tero Harju and Emo Welzl",

year = "2002",

doi = "10.1007/3-540-45832-8_13",

language = "English",

isbn = "9783540443100",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "48--60",

editor = "A. Corradini and H. Ehrig and H.-J. Kreowski and G. Rozenberg",

booktitle = "Graph Transformation. ICGT 2002",

}

Euler Graphs, Triangle-Free Graphs and Bipartite Graphs in Switching Classes. / Hage, Jurriaan; Harju, Tero; Welzl, Emo.
Graph Transformation. ICGT 2002. ed. / A. Corradini; H. Ehrig; H.-J. Kreowski; G. Rozenberg. Springer, 2002. p. 48-60 (Lecture Notes in Computer Science; Vol. 2505).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Euler Graphs, Triangle-Free Graphs and Bipartite Graphs in Switching Classes

AU - Hage, Jurriaan

AU - Harju, Tero

AU - Welzl, Emo

PY - 2002

Y1 - 2002

N2 - 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. A switching class is then a set of graphs obtainable from a given start graph by applying the switching operation.Continuing the line of research in Ehrenfeucht et al. we consider the problem of detecting three kinds of graphs in switching classes. For all three we find algorithms running in time polynomial in the number of vertices in the graphs, although switching classes contain exponentially many graphs.

AB - 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. A switching class is then a set of graphs obtainable from a given start graph by applying the switching operation.Continuing the line of research in Ehrenfeucht et al. we consider the problem of detecting three kinds of graphs in switching classes. For all three we find algorithms running in time polynomial in the number of vertices in the graphs, although switching classes contain exponentially many graphs.

U2 - 10.1007/3-540-45832-8_13

DO - 10.1007/3-540-45832-8_13

M3 - Conference contribution

SN - 9783540443100

T3 - Lecture Notes in Computer Science

SP - 48

EP - 60

BT - Graph Transformation. ICGT 2002

A2 - Corradini, A.

A2 - Ehrig, H.

A2 - Kreowski, H.-J.

A2 - Rozenberg, G.

PB - Springer

ER -

Euler Graphs, Triangle-Free Graphs and Bipartite Graphs in Switching Classes

Abstract

Publication series

Access to Document

Fingerprint

Cite this