HackerPapers

arXiv:0804.4881cs.DS

Search Space Contraction in Canonical Labeling of Graphs

Adolfo Piperno

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

Abstract

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.

arXiv comments
Journal reference
DOI
Subjects
cs.DSData Structures and Algorithms cs.DMDiscrete Mathematics

On Hacker News

Linked by 1 identifiable commenter in 1 comment across 1 thread, from Jul 2020 to Jul 2020.

Comments linking this paper, per year.

Discussed in comments1 thread

  1. Computation Graphs and Graph Computation 1 comment

    • I haven't read everything, but it does contain a section about something I'm quite familiar with: The article says "We compute the hashcode of the entire graph by hashing the multiset of WL labels. With one round, we’re just comparing the degree histogram. The more rounds we…

      jixView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.