A Heuristic for Direct Product Graph Decomposition
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2021
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908630183313408 |
|---|---|
| author | Calderoni, Luca Margara, Luciano Marzolla, Moreno |
| author_facet | Calderoni, Luca Margara, Luciano Marzolla, Moreno |
| contents | 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 Adj($G$), our heuristic searches for a pair of graphs~$G_1$ and~$G_2$ such that $G = G_1 \otimes G_2$, where $G_1 \otimes 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2107_03133 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | A Heuristic for Direct Product Graph Decomposition Calderoni, Luca Margara, Luciano Marzolla, Moreno Data Structures and Algorithms 05C70 F.2.2; F.2.1 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 Adj($G$), our heuristic searches for a pair of graphs~$G_1$ and~$G_2$ such that $G = G_1 \otimes G_2$, where $G_1 \otimes 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. |
| title | A Heuristic for Direct Product Graph Decomposition |
| topic | Data Structures and Algorithms 05C70 F.2.2; F.2.1 |
| url | https://arxiv.org/abs/2107.03133 |