Matroidal Network Link Model

Project: Research

View graph of relations


Problems concerning a network often involves a link model that describes how nodes areinterconnected. The classic network coding problem, for instance, models thecommunication channels as edges in a graph and so graph-theoretic results such as themax-flow min-cut theorem can be applied to characterize the maximum throughput. Weare interested in more complicated interconnections that may not be adequately capturedby graphs, such as the correlation in a distributed random source and the broadcast andinterference of signals over a wireless network. There were preliminary results thatextend the max-flow min-cut theorem to those cases. In particular, we have formulateda general link model using matroids and linking systems, and discovered meaningfulnotions of paths and flows that generalizes Menger's theorem and the Ford-Fulkersonalgorithm. Under the matroidal framework, we also extended the notion of partitionconnectivity from tree packing to mutual information for multiple random variables,which is applicable to undirected network coding, secret key agreement and dataexchange problems. We propose to investigate other related graph-theoretic results andsee whether they can be extended using the new framework. One concrete idea is toconsider fractional flows using polylinking systems and extend the more efficient push-relabelalgorithms for computing the maximum flow.


Project number9042608
Grant typeGRF
Effective start/end date1/01/1531/05/19