Search Space Contraction in Canonical Labeling of Graphs

Details Search Space Contraction in Canonical Labeling of Graphs Search Space Contraction in Canonical Labeling of Graphs

2008-04-30

arxiv.org/abs/0804.4881v2

Computer Science

Data Structures and Algorithms

Scientific paper

The individualization-refinement paradigm for computing a canonical labeling and the automorphism group of a graph is investigated. A new algorithmic design aimed at reducing the size of the associated search space is introduced, and a new tool, named "Traces", is presented, together with experimental results and comparisons with existing software, such as McKay's "nauty". It is shown that the approach presented here leads to a huge reduction in the search space, thereby making computation feasible for several classes of graphs which are hard for all the main canonical labeling tools in the literature.

Affiliated with

Also associated with

No associations

Rating

Search Space Contraction in Canonical Labeling of Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Search Space Contraction in Canonical Labeling of Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Search Space Contraction in Canonical Labeling of Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-578493