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

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

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE