Geodesic
Fast recognition of direct and strong products
Ars Mathematica Contemporanea, Tome 7 (2014) no. 2, pp. 487-497.

Voir la notice de l'article provenant de la source Ars Mathematica Contemporanea website

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 Δ.
DOI : 10.26493/1855-3974.320.43e
Keywords: Graph products, algorithms. 
@article{10_26493_1855_3974_320_43e,
     author = {Richard H. Hammack and Wilfried Imrich},
     title = {Fast recognition of direct and strong products},
     journal = {Ars Mathematica Contemporanea},
     pages = {487--497},
     publisher = {mathdoc},
     volume = {7},
     number = {2},
     year = {2014},
     doi = {10.26493/1855-3974.320.43e},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.320.43e/}
}
TY  - JOUR
AU  - Richard H. Hammack
AU  - Wilfried Imrich
TI  - Fast recognition of direct and strong products
JO  - Ars Mathematica Contemporanea
PY  - 2014
SP  - 487
EP  - 497
VL  - 7
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.320.43e/
DO  - 10.26493/1855-3974.320.43e
LA  - en
ID  - 10_26493_1855_3974_320_43e
ER  - 
%0 Journal Article
%A Richard H. Hammack
%A Wilfried Imrich
%T Fast recognition of direct and strong products
%J Ars Mathematica Contemporanea
%D 2014
%P 487-497
%V 7
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.320.43e/
%R 10.26493/1855-3974.320.43e
%G en
%F 10_26493_1855_3974_320_43e
Richard H. Hammack; Wilfried Imrich. Fast recognition of direct and strong products. Ars Mathematica Contemporanea, Tome 7 (2014) no. 2, pp. 487-497. doi : 10.26493/1855-3974.320.43e. http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.320.43e/

Cité par Sources :