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(n^2, \Delta^3))$? for the direct product, and ?$O(m \; a(G) \Delta)$? for the strong, where ?$n$? is the order of the graph ?$G$? to be factored, ?$m$? its size, ?$a(G)$? its arboricity, and ?$\Delta$? its maximum degree. That is, the complexities are linear in ?$m$? for fixed ?$\Delta$?.

Rights

URN

URN:NBN:SI:DOC-KDKQY53L

COBISSID

17164889

Added

29.05.2020

Metadata

Citation

APA:

Hammack, Richard H., Imrich, Wilfried (2014). Fast recognition of direct and strong products. Ars mathematica contemporanea, volume 7, issue 2, str. 487-497. URN:NBN:SI:DOC-KDKQY53L from http://www.dlib.si

MLA:

Hammack, Richard H., Imrich, Wilfried. "Fast recognition of direct and strong products." Ars mathematica contemporanea volume 7. issue 2 (2014) str. 487-497.
<http://www.dlib.si/?URN=URN:NBN:SI:DOC-KDKQY53L>

Ars mathematica contemporanea
2008-
(Assembly record)