A Subexponential Algorithm for Trivalent Graph Isomorphism.

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 Hoffman's algorithm for determining the automorphism group of a trivalent cone graph to deterministic time 0(n(clogn)) and extend it to arbitrary trivalent graphs. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1980
Accession Number
ADA093321

Entities

People

  • Eugene Luks
  • John Hopcroft
  • Merrick Furst

Organizations

  • Department of Computer Science, Cornell University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Computer Science
  • Computers
  • Generators
  • Identities
  • Mathematics
  • Military Research
  • Permutations
  • Polynomials
  • Sequences
  • Trees (Data Structures)
  • Universities

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.