Project Details
Projekt Print View

Untersuchung der Komplexität des Graphenisomorphieproblems

Subject Area Theoretical Computer Science
Term from 2005 to 2011
Project identifier Deutsche Forschungsgemeinschaft (DFG) - Project number 5436983
 
Final Report Year 2010

Final Report Abstract

Wir sind in der Forschung der Komplexität des Isomorphieproblems für Graphen und andere algebraische Strukturen ein Stück weiter gekommen. Insbesondere für konkrete eingeschränkte Graphklassen wie planare, K3,3 und K5 freie Graphen haben wir wichtige Resultate erzielt die das Klassifikationsproblem endgültig lösen können, indem wir die Vollständigkeit der Probleme für die Klasse L bewiesen haben. Auch für das Isomorphieproblem für Quasigruppen haben wir wichtige Resultate erzielt. Intuitiv schien das Problem einfacher als das Graphenisomorphieproblem zu sein. Wir konnten diese Intuition formalisieren und ohne jegliche unbewiesene Voraussetzungen zeigen, dass das erste Problem auf das zweite AC^0 reduzierbar ist, aber Graphenisomorphie nicht auf Quasigruppenisomorphie reduzierbar ist.

Publications

  • Arthur-Merlin Games and the Problem of Isomorphism Testing. Proc. Conference on Computability in Europe, Vol. 1, LNCS 3526, 495-506, 2005
    Jacobo Torán
  • Isomorphism Testing: Perspective and Open Problems. In: Bulletin of the European Association for Theoretical Computer Science, Vol 86, 2005
    V. Arvind and Jacobo Torán
  • The Complexity of Quasigroup Isomorphism and the Minimum Generating Set Problem. Proc. 17th International Symposium on Algorithms and Computation, LNCS 4288, 233-242, 2006
    V. Arvind and Jacobo Toran
  • Hardness results for tournament isomorphism and automorphism. In: 32nd International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 572-583, 2007
    Fabian Wagner
  • The Quantum Query Complexity of Algebraic Properties. Proc. 16th International Symposium on Fundamentals of Computation Theory, 2007
    Sebastian Dörn, Thomas Thierauf
  • Hardness results for isomorphism and automorphism of bounded valence graphs. In: Theory and Practice of Computer Science (SOFSEM), volume 2 - Student Research Forum, pages 131-140, 2008
    Fabian Wagner
  • Isomorphism and factorization, classical and quantum algorithms. Mathematical Analysis of Evolution, Information, and Complexity, 16:433-454, 2009
    Sebastian Dörn, Daniel Haase, Jacobo Torán, and Fabian Wagner
  • Isomorphism for K3,3-free and K5-free graphs is in log-space. In: Proceedings of the 29th annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2009
    Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf and Fabian Wagner
  • Planar graph isomorphism is in log-space. Annual IEEE Conference on Computational Complexity (CCC), pages 203-214, 2009
    Samir Datta, Nutan Limaye, Prajalcta Nimbhorkar, Thomas Thierauf and Fabian Wagner
  • Reachabihty in K3,3-free graphs and K5-free graphs is in unambiguous log-space. In: 17th International Symposium, Fundamentals of Computation Theory (FCT), LNCS 5699, 2009
    Thomas Thierauf and Fabian Wagner
  • The complexity of planar graph isomorphism. Bulletin of the European Association for Theoretical Computer Science (EATCS), 97:60-82, 2009
    Jacobo Torán and Fabian Wagner
  • On the complexity of isomorphism testing for restricted classes of graphs. Dissertation. Technical Report VTS-ID/7264, Institutional Repository of University of Ulm, 2010
    Fabian Wagner
  • Reductions to Graph Isomorphism. Theory of Computing Systems 47 (1) 288-299 (2010)
    Jacobo Torán
  • Restricted space algorithms for isomorphism on bounded treewidth graphs. In: 27th International Symposium on Theoretical Aspects of Computer Science (STACS), pages 227-238, 2010
    Bireswar Das, Jacobo Torán, and Fabian Wagner
  • The isomorphism problem for planar 3-connected graphs is in unambiguous logspace. Theory of Computing Systems (ToC), 47(3):655-673, 2010
    Thomas Thierauf and Fabian Wagner
 
 

Additional Information

Textvergrößerung und Kontrastanpassung