Gomory-Hu Trees Over Wireless

被引：0

作者：

Dogan, Mine Gokce ^{[1
]}

Ezzeldin, Yahya H. ^{[2
]}

Fragouli, Christina ^{[1
]}

机构：

[1] Univ Calif Los Angeles, Elect & Comp Engn Dept, Los Angeles, CA 90095 USA

[2] Univ Southern Calif, Elect & Comp Engn Dept, Los Angeles, CA 90089 USA

来源：

IEEE COMMUNICATIONS LETTERS | 2022年 / 26卷 / 05期

关键词：

Wireless networks; Relay networks (telecommunication); Approximation algorithms; Mutual information; Optimization; Interference; Upper bound; Gomory-Hu trees; min-cut; wireless networks; FLOW;

D O I：

10.1109/LCOMM.2022.3155176

中图分类号：

TN [电子技术、通信技术];

学科分类号：

0809 ;

摘要：

The Gomory-Hu tree is a popular optimization algorithm that enables to efficiently find a min-cut (or equivalently, max-flow) for every pair of nodes in a graph. However, graphs cannot capture broadcasting and interference in wireless: over wireless networks we need to resort to the information-theoretical cut-set to bound the max-flow. Leveraging the submodularity of mutual information, we show that the Gomory-Hu algorithm can be used to efficiently find information-theoretic rate characterizations such as the capacity or an approximation to the capacity, over a number of network scenarios including wireless Gaussian networks and deterministic relay networks.

引用

页码：1004 / 1007

页数：4

共 21 条

[1] Wireless Network Information Flow: A Deterministic Approach
Avestimehr, A. Salman
Diggavi, Suhas N.
Tse, David N. C.
[J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 2011, 57 (04) : 1872 - 1905
[2] Approximate Capacity of Gaussian Relay Networks
Avestimehr, Amir Salman
Diggavi, Suhas N.
Tse, David N. C.
[J]. 2008 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY PROCEEDINGS, VOLS 1-6, 2008, : 474 - +
[3] Cover T., 1991, ELEMENTS INFORM THEO
[4] Duarte EP, 2004, 2004 INTERNATIONAL CONFERENCE ON DEPENDABLE SYSTEMS AND NETWORKS, PROCEEDINGS, P495
[5] Combinatiorial Algorithms for Wireless Information Flow
Ebrahimi, Javad B.
Fragouli, Christina
[J]. ACM TRANSACTIONS ON ALGORITHMS, 2012, 9 (01)
[6] Cut problems in graphs with a budget constraint
Engelberg, Roee
Koenemann, Jochen
Leonardi, Stefano
Naor, Joseph
[J]. JOURNAL OF DISCRETE ALGORITHMS, 2007, 5 (02) : 262 - 279
[7] Ezzeldin YH, 2019, IEEE INT SYMP INFO, P460, DOI [10.1109/ISIT.2019.8849671, 10.1109/isit.2019.8849671]
[8] Flake G.W., 2004, Internet Math., V1, P385, DOI DOI 10.1080/15427951.2004.10129093
[9] Friggstad Z, 2016, UNDIRECTED CUTS GOMO
[10] Friggstad Z., 2016, GOMORY HU TREES

← 1 2 3 →