Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








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

URL of the conference:

http://www.siam.org/meetings/alenex07/

URL for downloading the paper:

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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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 PM
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section