On the complexity of isomorphism testing for restricted classes of graphs [Elektronische Ressource] / vorgelegt von Fabian Emanuel Herbert Wagner

217

pages

English

Documents

2010

Lire

Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres

217

pages

English

Documents

2010

Lire

Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres

Publié par

universitat_ulm

Publié le

01 janvier 2010

Nombre de lectures

Langue

English

Poids de l'ouvrage

1 Mo

Universita¨t UlmInstitut fur Theoretische Informatik¨Leiter: Prof. Dr. Uwe Schoning¨On the Complexity ofIsomorphism Testingfor Restricted Classes of GraphsDISSERTATIONzur Erlangung des Doktorgrades Dr.rer.nat.der Fakulta¨t fu¨r Ingenieurwissenschaften und Informatik derUniversitat Ulm¨vorgelegt vonFabian Emanuel Herbert Wagneraus Munchen¨2010Amtierender Dekan: Prof. Dr.-Ing. Michael WeberGutachter: Prof. Dr. Jacobo Tor´anProf. Dr. Uwe Schoning¨Prof. Dr. Johannes Ko¨blerTag der Promotion: 18.02.2010AcknowledgmentsI would like to thank my supervisor, Prof. Dr. Jacobo Tor´an. His continuoussupport and guidance have greatly inﬂuenced my research and this work. Thisthesis arose in the context of the DFG research project: Die Komplexita¨t desGraphenisomorphieproblems and the Graduate School: Mathematical Analysisof Evolution, Information and Complexity. I am grateful to Prof. Dr. ThomasThierauf for the close collaboration. I wish to thank Meena Mahajan, SamirDatta,NutanLimayeandPrajaktaNimbhorkarforintensivelyworkingtogetheron isomorphismand reachabilityproblems. Finally, I thankmyparentsand myfamily Gudrun and Sebastian for love and patience.Contents1 Introduction 11.1 Overview of the thesis . . . . . . . . . . . . . . . . . . . . . . . . 42 Preliminaries 72.1 Complexity Theory . . . . . . . . . . . . . . . . . . . . . . . . . . 72.2 Graph Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.3 Group Theory . . . . . . . . . . . .

Voir

Publié par

universitat_ulm

Publié le

01 janvier 2010

Langue

English

Poids de l'ouvrage

1 Mo

Informatik

Voir