Geodesic
Fast recognition of partial star products and quasi cartesian products
Ars Mathematica Contemporanea, Tome 9 (2015) no. 2, pp. 223-242.

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

This paper is concerned with the fast computation of a relation d on the edge set of connected graphs that plays a decisive role in the recognition of approximate Cartesian products, the weak reconstruction of Cartesian products, and the recognition of Cartesian graph bundles with a triangle free basis.A special case of d is the relation δ*, whose convex closure yields the product relation σ that induces the prime factor decomposition of connected graphs with respect to the Cartesian product. For the construction of d so-called Partial Star Products are of particular interest. Several special data structures are used that allow to compute Partial Star Products in constant time. These computations are tuned to the recognition of approximate graph products, but also lead to a linear time algorithm for the computation of δ* for graphs with maximum bounded degree.Furthermore, we define quasi Cartesian products as graphs with non-trivial δ*. We provide several examples, and show that quasi Cartesian products can be recognized in linear time for graphs with bounded maximum degree. Finally, we note that quasi products can be recognized in sublinear time with a parallelized algorithm.
DOI : 10.26493/1855-3974.520.933
Keywords: Cartesian product, quasi product, graph bundle, approximate product, partial star product, product relation. 
@article{10_26493_1855_3974_520_933,
     author = {Marc Hellmuth and Wilfried Imrich and Tomas Kupka},
     title = {Fast recognition of partial star products and quasi cartesian products},
     journal = {Ars Mathematica Contemporanea},
     pages = {223--242},
     publisher = {mathdoc},
     volume = {9},
     number = {2},
     year = {2015},
     doi = {10.26493/1855-3974.520.933},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.520.933/}
}
TY  - JOUR
AU  - Marc Hellmuth
AU  - Wilfried Imrich
AU  - Tomas Kupka
TI  - Fast recognition of partial star products and quasi cartesian products
JO  - Ars Mathematica Contemporanea
PY  - 2015
SP  - 223
EP  - 242
VL  - 9
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.520.933/
DO  - 10.26493/1855-3974.520.933
LA  - en
ID  - 10_26493_1855_3974_520_933
ER  - 
%0 Journal Article
%A Marc Hellmuth
%A Wilfried Imrich
%A Tomas Kupka
%T Fast recognition of partial star products and quasi cartesian products
%J Ars Mathematica Contemporanea
%D 2015
%P 223-242
%V 9
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.520.933/
%R 10.26493/1855-3974.520.933
%G en
%F 10_26493_1855_3974_520_933
Marc Hellmuth; Wilfried Imrich; Tomas Kupka. Fast recognition of partial star products and quasi cartesian products. Ars Mathematica Contemporanea, Tome 9 (2015) no. 2, pp. 223-242. doi : 10.26493/1855-3974.520.933. http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.520.933/

Cité par Sources :