A Linear-Time Algorithm for Computing the Prime Decomposition of a Directed Graph with Regard to the Cartesian Product - Archive ouverte HAL Access content directly
Conference Papers Year : 2013

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

(1) , (2) , (2)
1
2

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.
Not file

Dates and versions

hal-00915063 , version 1 (06-12-2013)

Identifiers

  • HAL Id : hal-00915063 , version 1

Cite

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. ⟨hal-00915063⟩
108 View
0 Download

Share

Gmail Facebook Twitter LinkedIn More