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

Description

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 influenced 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 . . . . . . . . . . . .

Sujets

• Informatik

Informations

• Publié par: universitat_ulm
• Publié le: 01 janvier 2010
• Nombre de lectures: 25
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait