Fast recognition of direct and strong products

Richard H. Hammack, Wilfried Imrich

Abstract


This note describes fast algorithms for computing the prime factors of connected, nonbipartite graphs with respect to the direct product, and of connected graphs with respect to the strong product. The complexities are O(m min(n2; Δ3)) for the direct product, and O(m a(G) Δ) for the strong, where n is the order of the graph G to be factored, m its size, a(G) its arboricity, and Δ its maximum degree. That is, the complexities are linear in m for fixed Δ.

Keywords


Graph products, algorithms.

Full Text:

PDF Abstracts (EN/SI)


DOI: https://doi.org/10.26493/1855-3974.320.43e

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications