A Linear-Time Algorithm for Computing the Prime Decomposition of a Directed Graph with Regard to the Cartesian Product

Christophe Crespelle 1, * Eric Thierry 2 Thomas Lambert 2
* Auteur correspondant
1 DANTE - Dynamic Networks : Temporal and Structural Capture Approach
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme, IXXI - Institut Rhône-Alpin des systèmes complexes
Abstract : In this paper, we design the first linear-time algorithm for computing the prime decomposition of a digraph G with regard to the cartesian product. A remarkable feature of our solution is that it computes the decomposition of G from the decomposition of its underlying undirected graph, for which there exists a linear-time algorithm. First, this allows our algorithm to remain conceptually very simple and in addition, it provides new insight into the connexions between the directed and undirected versions of cartesian product of graphs.
Type de document :
Communication dans un congrès
19th Annual International Computing and Combinatorics Conference - COCOON 2013, Jun 2013, Hangzhou, China. 2013, 〈http://link.springer.com/chapter/10.1007/978-3-642-38768-5_42〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00915063
Contributeur : Christophe Crespelle <>
Soumis le : vendredi 6 décembre 2013 - 14:56:13
Dernière modification le : jeudi 12 juillet 2018 - 01:09:26

Identifiants

  • HAL Id : hal-00915063, version 1

Collections

Citation

Christophe Crespelle, Eric Thierry, Thomas Lambert. A Linear-Time Algorithm for Computing the Prime Decomposition of a Directed Graph with Regard to the Cartesian Product. 19th Annual International Computing and Combinatorics Conference - COCOON 2013, Jun 2013, Hangzhou, China. 2013, 〈http://link.springer.com/chapter/10.1007/978-3-642-38768-5_42〉. 〈hal-00915063〉

Partager

Métriques

Consultations de la notice

201