| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4649073 | Discrete Mathematics | 2007 | 12 Pages |
Abstract
We present an algorithm that determines the prime factors of connected graphs with respect to the Cartesian product in linear time and space. This improves a result of Aurenhammer et al. [Cartesian graph factorization at logarithmic cost per edge, Comput. Complexity 2 (1992) 331–349], who compute the prime factors in O(mlogn)O(mlogn) time, where m denotes the number of vertices of G and n the number of edges. Our algorithm is conceptually simpler. It gains its efficiency by the introduction of edge-labellings.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Wilfried Imrich, Iztok Peterin,