MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Kutz, Martin
Schweitzer, Pascal		dblp
dblp
Editor(s):
Applegate, David
Brodal, Gerth		dblp
dblp
BibTeX cite key*:
KutzSchw2006
Title, Booktitle
Title*:
ScrewBox: a Randomized Certifying Graph Non-Isomorphism Algorithm
Booktitle*:
9th Workshop on Algorithm Engineering and Experiments (ALENEX'07)
Event, URLs
Conference URL::
http://www.siam.org/meetings/alenex07/
Downloading URL:
http://www.siam.org/meetings/proceedings/2007/alenex/papers/015kutzm.pdf
Event Address*:
New Orleans, USA
Language:
English
Event Date*
(no longer used):
Organization:
Society for Industrial and Applied Mathematics (SIAM)
Event Start Date:
6 January 2007
Event End Date:
6 January 2007
Publisher
Name*:
SIAM
URL:
http://www.siam.org
Address*:
Philadelphia, USA
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
Pages:
150-157
Year*:
2007
VG Wort Pages:
ISBN/ISSN:
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
We present a novel randomized approach to the graph isomorphism problem. Our algorithm aims at solving difficult instances by producing randomized certificates for \emph{non}-isomorphism. We compare our implementation to the de facto standard nauty. On many of the hardest known instances, the incidence graphs of finite projective planes, our program is considerably faster than nauty.
However, it is inherent to our approach that it performs better on pairs of non-isomorphic graphs than on isomorphic instances.

Our algorithm randomly samples substructures in the given graphs in order to detect dissimilarities between them. The choice of the sought-after structures as well as the tuning of the search process is dynamically adapted during the sampling. Eventually, a randomized certificate is produced by which the user can verify the non-isomorphism of the input graphs. As a byproduct of our approach, we introduce a new concept of regularity for graphs which is meant to capture the computational hardness of isomorphism problems on graphs.
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{KutzSchw2006,
AUTHOR = {Kutz, Martin and Schweitzer, Pascal},
 EDITOR = {Applegate, David and Brodal, Gerth},
 TITLE = {{ScrewBox}: a Randomized Certifying Graph Non-Isomorphism Algorithm},
 BOOKTITLE = {9th Workshop on Algorithm Engineering and Experiments (ALENEX'07)},
 PUBLISHER = {SIAM},
 YEAR = {2007},
 ORGANIZATION = {Society for Industrial and Applied Mathematics (SIAM)},
 PAGES = {150--157},
 ADDRESS = {New Orleans, USA},
}

Entry last modified by Christine Kiesel, 02/28/2008
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Pascal Schweitzer		Created
02/28/2007 12:36:59
Revisions
3.
2.
1.
0.
Editor(s)
Christine Kiesel
Christine Kiesel
Pascal Schweitzer
Pascal Schweitzer
Edit Dates
20.06.2007 13:38:44
20.06.2007 12:55:31
05/08/2007 01:21:02 PM
02/28/2007 12:36:59 PM