Reduced Functional Dependence Graph and Its Applications

Details Reduced Functional Dependence Graph and Its Applications Reduced Functional Dependence Graph and Its Applications

2012-01-11

arxiv.org/abs/1201.2231v2

Computer Science

Information Theory

Scientific paper

Functional dependence graph (FDG) is an important class of directed graph that captures the dominance relationship among a set of variables. FDG is frequently used in calculating network coding capacity bounds. However, the order of FDG is usually much larger than the original network and the computational complexity of many bounds grows exponentially with the order of FDG. In this paper, we introduce the concept of reduced FDG, which is obtained from the original FDG by keeping only those "essential" edges. It is proved that the reduced FDG gives the same capacity region/bounds with the original FDG, but requiring much less computation. The applications of reduced FDG in the algebraic formulation of scalar linear network coding is also discussed.

Affiliated with

Also associated with

No associations

Rating

Reduced Functional Dependence Graph and Its Applications does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Reduced Functional Dependence Graph and Its Applications, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reduced Functional Dependence Graph and Its Applications will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-603408