Cantitate/Preț
Produs

Isomorphism Testing for Restricted Graph Classes

Autor Fabian Wagner
en Limba Engleză Paperback – 16 noi 2015
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.
Citește tot Restrânge

Preț: 50865 lei

Preț vechi: 63582 lei
-20% Nou

Puncte Express: 763

Preț estimativ în valută:
9734 10101$ 8136£

Carte tipărită la comandă

Livrare economică 17-31 martie

Preluare comenzi: 021 569.72.76

Specificații

ISBN-13: 9783838119540
ISBN-10: 3838119541
Pagini: 244
Dimensiuni: 152 x 229 x 14 mm
Greutate: 0.36 kg
Editura: Sudwestdeutscher Verlag Fur Hochschulschrifte

Notă biografică

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