Reduced functional dependence graphs. Issue 2 (1st March 2015)

• Record Type: Journal Article
• Authors: Xu, Xiaoli; Thakor, Satyajit; Guan, Yong Liang
• Is Part Of: IET networks. Volume 4:Issue 2(2015)
• Page Start: 102
• Page End: 110
• Publication Date: 2015-03-01
• Subjects: directed graphs -- network coding; node reduction -- systematic graph reduction techniques -- computational complexity -- network coding capacity bounds -- directed graph -- FDG -- reduced functional dependence graphs; Computer network architectures -- Periodicals; Computer network protocols -- Periodicals; Information networks -- Periodicals; Telecommunication systems -- Periodicals; 004.605
• DOI: 10.1049/iet-net.2013.0133
• Languages: English
• ISSNs: 2047-4954

Abstract

Abstract : Functional dependence graph (FDG) is an important class of directed graph that captures the functional dependence relationships of a set of random variables and it is frequently used in characterising network coding capacity bounds. Since the computational complexity of such bounds usually grows exponentially with the order of the FDG, it is desirable to find an FDG with the smallest size possible. To this end, some systematic graph reduction techniques are introduced in this study. The first reduction technique is performed on the original networks, where 'non‐essential' edges are identified and eliminated. This is equivalent to node reduction in the corresponding FDG. Besides, the authors show that certain edges in the FDG may also be removed without affecting the functional dependence relationships of the random variables. The removal of the edges in the FDG may create new opportunities to reduce the order of the FDG. It is proved that the reduced FDGs give the same network coding capacity region/bounds as that obtained by using the original FDGs and yet much less computation is required.