Paper Info
Title
Finding the prime factors of strong direct product graphs in polynomial time
Abstract
The strong direct product is one of several standard product operators on graphs. Dörfler and Imrich (1969) and, independently, McKenzie (1971) showed that any connected graph has a unique prime factorization under the strong direct product. We give a polynomial-time algorithm for finding this unique factorization, thus settling a question of Nešetřil.
Year
DOI
Venue
1992
10.1016/0012-365X(92)90280-S
Discrete Mathematics
Keywords
Field
DocType
strong direct product graph,prime factor,polynomial time,direct product
Discrete mathematics,Combinatorics,Direct product,Unique prime,Graph product,Factorization,Prime factor,Unique factorization domain,Connectivity,Time complexity,Mathematics
Journal
Volume
Issue
ISSN
109
1-3
Discrete Mathematics
Citations 
PageRank 
References 
22
2.53
12
Authors
2
Name
Order
Citations
PageRank
Joan Feigenbaum14714711.33
Alejandro A. Schäffer2827136.66