Use your computer fearlessly.

Mission Services Articles Research

A polynomial-time algorithm for graph isomorphism

Authors: Brent Kirkpatrick

Journal: The Intrepid Publication Series (TIPS)

Year: 2016

Abstract: The graph isomorphism problem is fundamental to many applications of computer science. This problem is so often presented in its technical formulation, rather than its applications, that newcomers to the field of computer science may underestimate the breadth of application for this single problem.

This paper presents a polynomial-time algorithm for counting the automorphisms of a directed acyclic graph (DAG). The same algorithm can be used to find a single automorphism in polynomial time. Due to the graph-isomorphic completeness of the DAG isomorphism problem, this result applies by reduction to solving the general problem of graph isomorphism.

Download: pdf

Bibliography: BibTeX,

What Is New? | Contact | Tips

© 2015-2021 Intrepid Net Computing. All rights reserved.