• English
    • Deutsch
  • English 
    • English
    • Deutsch
  • Login
View Item 
  •   Home
  • Universität Ulm
  • Publikationen
  • View Item
  •   Home
  • Universität Ulm
  • Publikationen
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

On the complexity of isomorphism testing for restricted classes of graphs

Thumbnail
vts_7264_10267.pdf (1.557Mb)
217 Seiten
Veröffentlichung
2010-05-03
Authors
Wagner, Fabian
Dissertation


Faculties
Fakultät für Ingenieurwissenschaften und Informatik
Abstract
The graph isomorphism problem GI consists of deciding whether there is a bijection between the vertices of two graphs, which preserves the adjacency relations. The problem is in NP but it is not known to be complete for this class [BHZ87,Sch88] nor in the class P. The best known lower bound is DET [Tor04]. This enormous gap 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 on quasigroups, which are given in table representation. Besides isomorphism we also consider the reachability problem which asks in a directed graph with two designated vertices s and t, whether there is a path from s to t. We consider the complexity of the shortest path problem on planar graphs and reduce reachability on K_{3,3}-minor free and K_5-minor free directed graphs to reachability for planar directed graphs. This improves the existing upper bounds for the reachability problems on the mentioned graph classes.
Date created
2010
Subject headings
[GND]: Graphenisomorphie
[LCSH]: Computational complexity | Graph theory
[Free subject headings]: Graph isomorphism | Reachability
[DDC subject group]: DDC 004 / Data processing & computer science
License
Standard (Fassung vom 01.10.2008)
https://oparu.uni-ulm.de/xmlui/license_v2

Metadata
Show full item record

DOI & citation

Please use this identifier to cite or link to this item: http://dx.doi.org/10.18725/OPARU-3896

Wagner, Fabian (2010): On the complexity of isomorphism testing for restricted classes of graphs. Open Access Repositorium der Universität Ulm und Technischen Hochschule Ulm. Dissertation. http://dx.doi.org/10.18725/OPARU-3896
Citation formatter >



Policy | kiz service OPARU | Contact Us
Impressum | Privacy statement
 

 

Advanced Search

Browse

All of OPARUCommunities & CollectionsPersonsInstitutionsPublication typesUlm SerialsDewey Decimal ClassesEU projects UlmDFG projects UlmOther projects Ulm

My Account

LoginRegister

Statistics

View Usage Statistics

Policy | kiz service OPARU | Contact Us
Impressum | Privacy statement