 |
|
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, EndNote, RefWorks, Mendeley |
