Geodesic
A Heuristic for Direct Product Graph Decomposition
Journal of Graph Algorithms and Applications, Tome 27 (2023) no. 7, pp. 581-601.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

In this paper we describe a heuristic for decomposing a directed graph into factors according to the direct product (also known as Kronecker, cardinal or tensor product). Given a directed, unweighted graph $G$ with adjacency matrix $\mathbf{Adj}(G)$, our heuristic aims at identifying two graphs $G_1$ and $G_2$ such that $G = G_1 \times G_2$, where $G_1 \times G_2$ is the direct product of $G_1$ and $G_2$. For undirected, connected graphs it has been shown that graph decomposition is "at least as difficult" as graph isomorphism; therefore, polynomial-time algorithms for decomposing a general directed graph into factors are unlikely to exist. Although graph factorization is a problem that has been extensively investigated, the heuristic proposed in this paper represents - to the best of our knowledge - the first computational approach for general directed, unweighted graphs. We have implemented our algorithm using the MATLAB environment; we report on a set of experiments that show that the proposed heuristic solves reasonably-sized instances in a few seconds on general-purpose hardware. Although the proposed heuristic is not guaranteed to find a factorization, even if one exists; however, it always succeeds on all the randomly-generated instances used in the experimental evaluation.
DOI : 10.7155/jgaa.00635
Keywords: Kronecker product, direct product, graph factorization, graph decomposition, heuristic 
@article{JGAA_2023_27_7_a3,
     author = {Luca Calderoni and Luciano Margara and Moreno Marzolla},
     title = {A {Heuristic} for {Direct} {Product} {Graph} {Decomposition}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {581--601},
     publisher = {mathdoc},
     volume = {27},
     number = {7},
     year = {2023},
     doi = {10.7155/jgaa.00635},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00635/}
}
TY  - JOUR
AU  - Luca Calderoni
AU  - Luciano Margara
AU  - Moreno Marzolla
TI  - A Heuristic for Direct Product Graph Decomposition
JO  - Journal of Graph Algorithms and Applications
PY  - 2023
SP  - 581
EP  - 601
VL  - 27
IS  - 7
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00635/
DO  - 10.7155/jgaa.00635
LA  - en
ID  - JGAA_2023_27_7_a3
ER  - 
%0 Journal Article
%A Luca Calderoni
%A Luciano Margara
%A Moreno Marzolla
%T A Heuristic for Direct Product Graph Decomposition
%J Journal of Graph Algorithms and Applications
%D 2023
%P 581-601
%V 27
%N 7
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00635/
%R 10.7155/jgaa.00635
%G en
%F JGAA_2023_27_7_a3
Luca Calderoni; Luciano Margara; Moreno Marzolla. A Heuristic for Direct Product Graph Decomposition. Journal of Graph Algorithms and Applications, Tome 27 (2023) no. 7, pp. 581-601. doi : 10.7155/jgaa.00635. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00635/

Cité par Sources :