On the Graph Decomposition

descriptionPublicationkeyboard_double_arrow_right Article , Conference object 01 Dec 2014Publisher:IEEEJournal:2014 IEEE Fourth International Conference on Big Data and Cloud Computing

Authors: Yangjun Chen; Yibin Chen;

doi: 10.1109/bdcloud.2014.118

On the Graph Decomposition

- Summary
- Metrics

Abstract

In this paper, we propose an efficient algorithm to decompose a directed acyclic graph (DAG) 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.

Related Organizations

University of Winnipeg
Canada

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	4
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average