Affiliations: Institute of Information and Computing Science,
Universiteit Utrecht, P.O.Box 80.089, 3508 TB Utrecht, Netherlands | Department of Mathematics, University of Turku,
FIN-20014 Turku, Finland | Institut füur Theoretische Informatik, ETH
Zürich, CH - 8092 Zürich, Switzerland
Abstract: In the context of graph transformations we look at the operation of
switching, which can be viewed as a 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, Hage,
Harju and Rozenberg 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.
