Computing the directed Cartesian-product decomposition of a directed graph from its undirected decomposition in linear time

In this paper, we design an algorithm that, given a directed graph G and the Cartesian-product decomposition of its underlying undirected graph G̃, produces the directed Cartesian-product decomposition of G in linear time. This is the first time that the linear complexity is achieved for this proble...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2015-12, Vol.338 (12), p.2393-2407
Main Authors: Crespelle, Christophe, Thierry, Eric
Format: Article
Language:English
Subjects:
Algorithms
Cartesian product
Computation
Computer Science
Computing time
Decomposition
Directed graphs
Equivalence
Graph decompositions
Graph theory
Graphs
Linear-time algorithm
Mathematical models
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we design an algorithm that, given a directed graph G and the Cartesian-product decomposition of its underlying undirected graph G̃, produces the directed Cartesian-product decomposition of G in linear time. This is the first time that the linear complexity is achieved for this problem, which has two major consequences. Firstly, it shows that the directed and undirected versions of the Cartesian-product decomposition of graphs are linear-time equivalent problems. And secondly, as there already exists a linear-time algorithm for solving the undirected version of the problem, combined together, it provides the first linear-time algorithm for computing the directed Cartesian-product decomposition of a directed graph.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2015.06.001