Accession Number:
ADA093321
Title:
A Subexponential Algorithm for Trivalent Graph Isomorphism.
Descriptive Note:
Technical rept.,
Corporate Author:
CORNELL UNIV ITHACA N Y DEPT OF COMPUTER SCIENCE
Personal Author(s):
Report Date:
1980-06-01
Pagination or Media Count:
30.0
Abstract:
This report contains two results First, a polynomial-time algorithm to test color preserving isomorphism of two vertex-colored graphs in which each color class is of size k or less Second, we improve Hoffmans algorithm for determining the automorphism group of a trivalent cone graph to deterministic time 0nclogn and extend it to arbitrary trivalent graphs. Author
Descriptors:
Subject Categories:
- Theoretical Mathematics