A Subexponential Algorithm for Trivalent Graph Isomorphism.
CORNELL UNIV ITHACA N Y DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
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
- Theoretical Mathematics