On the DAG Decomposition
Journal of Advances in Mathematics and Computer Science · pp. 1–27 · Published 5 Aug 2015
10.9734/BJMCS/2015/19380Abstract
In this paper, we propose an efficient algorithm to decompose a directed acyclic graph G into a minimized set of node-disjoint chains, which cover all the nodes of G. For any two nodes u and v on a chain, if u is above v then there is a path from u to v in G. The best algorithm for this problem up to now needs O(n3) time, where n is the number of the nodes of G. Our algorithm, however, needs only O(k.n2) time, where k isG’s width, defined to be the size of a largest node subset U of G such that for every pair of nodes x, y∈U, there does not exist a path from x to y or from y to x. More importantly, by the existing algorithm, O(n2) extra space (besides the space for G itself) is required to maintain the transitive closure of G to do the task while ours needs only O(k.n) extra space.
Cited by 3
Giacomo Ortali, Ioannis G. Tollis · Foundations · 2021
Panagiotis Lionakis, Giacomo Ortali, Ioannis G. Tollis · SN Computer Science · 2021
Giacomo Ortali, Ioannis G. Tollis · Lecture Notes in Computer Science · 2018
Related research
- On Cartesian Products of Any Finite Number of Orthogonal Double Covers — shares topic coverage
- On Orthogonal Double Covers of Complete Bipartite Graphs by an Infinite Certain Graph-Path and Graph-Cycle — shares topic coverage
- On Orthogonal Double Covers of Circulant Graphs — shares topic coverage
- Orthogonal Double Covers of Complete Bipartite Graphs by A Special Class of Disjoint Union of Path and A Complete Bipartite Graph — shares topic coverage
- On Cyclic Orthogonal Double Covers of Circulant Graphs using Infinite Graph Classes — shares topic coverage
Article metrics
Real usage data collected on this platform.
0
Page views
0
PDF downloads
0
Outbound clicks
3
Citations
Views by country
Approximate, from request IP at view time — not citizenship or institution. Countries with fewer than 5 views are grouped as "Other".
No views recorded yet.
Traffic sources
Referring site, by host.
No traffic recorded yet.
Views and downloads exclude known bots/crawlers. Citations combines this platform's own DOI-resolved index with each external source's own reported total — see Cited by above for individually listed citing works. Last refreshed 0 seconds ago.