DIRECTED ACYCLIC GRAPHS AND DISJOINT CHAINS

Yangjun Chen

2009

Abstract

The problem of decomposing a DAG (directed acyclic graph) into a set of disjoint chains has many applications in data engineering. One of them is the compression of transi¬tive closures to support reachability queries on whether a given node v in a directed graph G is reachable from another node u through a path in G. Recently, an interesting algorithm is proposed by Chen et al. (Y. Chen and Y. Chen, 2008) which claims to be able to decompose G into a minimal set of dis¬joint chains in O(n2 + bn ) time, where n is the number of the nodes of G, and b is G’s width, defined to be the size of a largest node subset U of G such that for every pair of nodes u, v  U, there does not exist a path from u to v or from v to u. However, in some cases, it fails to do so. In this paper, we analyze this algorithm and show the problem. More importantly, a new algorithm is discussed, which can always find a minimal set of disjoint chains in the same time complexity as Chen’s.

Paper Citation

in Harvard Style

Chen Y. (2009). DIRECTED ACYCLIC GRAPHS AND DISJOINT CHAINS . In Proceedings of the 11th International Conference on Enterprise Information Systems - Volume 1: ICEIS, ISBN 978-989-8111-84-5, pages 17-24. DOI: 10.5220/0001858300170024

in Bibtex Style

@conference{iceis09,
author={Yangjun Chen},
title={DIRECTED ACYCLIC GRAPHS AND DISJOINT CHAINS},
booktitle={Proceedings of the 11th International Conference on Enterprise Information Systems - Volume 1: ICEIS,},
year={2009},
pages={17-24},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0001858300170024},
isbn={978-989-8111-84-5},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 11th International Conference on Enterprise Information Systems - Volume 1: ICEIS,
TI - DIRECTED ACYCLIC GRAPHS AND DISJOINT CHAINS
SN - 978-989-8111-84-5
AU - Chen Y.
PY - 2009
SP - 17
EP - 24
DO - 10.5220/0001858300170024