English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  ScrewBox: a Randomized Certifying Graph Non-Isomorphism Algorithm

Kutz, M., & Schweitzer, P. (2007). ScrewBox: a Randomized Certifying Graph Non-Isomorphism Algorithm. In D. Applegate, G. S. Brodal, D. Panario, & R. Sedgewick (Eds.), Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments and the Fourth Workshop on Analytic Algorithmics and Combinatorics (pp. 150-157). Philadelphia, PA: SIAM.

Item is

 

show all

Basic

hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-209F-C Version Permalink: https://hdl.handle.net/21.11116/0000-000C-ADE3-1
Genre: Conference Paper

Files

show Files

Locators

show

Creators

hide
 Creators:
Kutz, Martin1, Author           
Schweitzer, Pascal1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

hide
Free keywords: -
 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.

Details

hide
Language(s): eng - English
 Dates: 2008-03-032007
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 356732
Other: Local-ID: C12573CC004A8E26-5346A7E2A38C418AC1257290003FCFC8-KutzSchw2006
 Degree: -

Event

hide
Title: Ninth Workshop on Algorithm Engineering and Experiments
Place of Event: New Orleans, LA, USA
Start-/End Date: 2007-01-06 - 2007-01-06

Legal Case

show

Project information

show

Source 1

hide
Title: Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments and the Fourth Workshop on Analytic Algorithmics and Combinatorics
  Abbreviation : ALENEX 2007
Source Genre: Proceedings
 Creator(s):
Applegate, David1, Editor
Brodal, Gerth Stølting2, Editor           
Panario, Daniel1, Editor
Sedgewick, Robert1, Editor
Affiliations:
1 External Organizations, ou_persistent22            
2 Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019            
Publ. Info: Philadelphia, PA : SIAM
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 150 - 157 Identifier: -

Source 2

hide
Title: Proceedings in Applied Mathematics
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: - Identifier: -