Articles liés à Isomorphism Testing for Restricted Graph Classes: On...

Isomorphism Testing for Restricted Graph Classes: On the complexity of isomorphism testing and reachability problems for restricted graph classes - Couverture souple

Wagner, Fabian

 
9783838119540: Isomorphism Testing for Restricted Graph Classes: On the complexity of isomorphism testing and reachability problems for restricted graph classes
Couverture souple
ISBN 10 : 3838119541 ISBN 13 : 9783838119540
Editeur : Suedwestdeutscher Verlag fuer Hochschulschriften, 2010

Synopsis

The graph isomorphism problem (GI) consists of deciding whether there is a bijection between the vertices of two graphs, which preserves the adjacency relations. GI is not known to be NP-complete nor to be in P. The enormous gap between the known upper and lower bound has motivated a study of isomorphism restricted to special classes of graphs where this gap can be reduced. We prove for the classes of planar graphs, K_{3,3}-minor free and K_5-minor free graphs, that isomorphism testing is in logspace. For graphs of bounded treewidth we prove a new upper bound LogCFL. We also consider the complexity of the isomorphism problem when groups or quasigroups are given in table representation. Because of all these results in the context of logarithmic space complexity classes we also consider reachability problems. Reachability is a widely studied problem especially in the space setting, it asks in a directed graph with two designated vertices s and t whether there is a path from s to t. We improve some upper bounds of the reachability problems for the mentioned graph classes.

Les informations fournies dans la section « Synopsis » peuvent faire référence à une autre édition de ce titre.

Présentation de l'éditeur

The graph isomorphism problem (GI) consists of deciding whether there is a bijection between the vertices of two graphs, which preserves the adjacency relations. GI is not known to be NP-complete nor to be in P. The enormous gap between the known upper and lower bound has motivated a study of isomorphism restricted to special classes of graphs where this gap can be reduced. We prove for the classes of planar graphs, K_{3,3}-minor free and K_5-minor free graphs, that isomorphism testing is in logspace. For graphs of bounded treewidth we prove a new upper bound LogCFL. We also consider the complexity of the isomorphism problem when groups or quasigroups are given in table representation. Because of all these results in the context of logarithmic space complexity classes we also consider reachability problems. Reachability is a widely studied problem especially in the space setting, it asks in a directed graph with two designated vertices s and t whether there is a path from s to t. We improve some upper bounds of the reachability problems for the mentioned graph classes.

Biographie de l'auteur

Fabian Wagner studied computer science at University of Ulm, he received his doctorate in 2010 from Institute of Theoretical Computer Science in Ulm.

Les informations fournies dans la section « A propos du livre » peuvent faire référence à une autre édition de ce titre.

Éditeur
Suedwestdeutscher Verlag fuer Hochschulschriften
Date d'édition
2010
Langue
anglais
ISBN 10 
3838119541
ISBN 13 
9783838119540
Reliure
Broché
Nombre de pages
244
Coordonnées du fabricant
non disponible
Personne responsable
non disponible