Abstract | ||
---|---|---|
We propose an algorithm for computing polyhedral bounds on the rate regions of multi-source multi-sink network coding instances given the knowledge of symmetries of the instance as captured by the network symmetry group. We show how the network symmetry group can be interpreted as a group of symmetries of a polyhedron, which in turn enables the use techniques for exploiting symmetry in polyhedral computation to reduce the complexity of calculating the rate region. We apply these techniques to the polyhedral projection algorithm chm to list only those facets and extreme points of a polyhedral bound on rate region that are inequivalent under the action of the network symmetry group. Additionally, a generalization of this algorithm that can exploit richer super-groups of polyhedral symmetries, the restricted affine symmetry groups, is discussed. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1109/NETCOD.2015.7176793 | 2015 International Symposium on Network Coding (NetCod) |
Keywords | Field | DocType |
network coding,symmetry,polyhedral projection | Linear network coding,Affine transformation,Extreme point,Discrete mathematics,Combinatorics,Symmetry group,Dykstra's projection algorithm,Polyhedron,Frameworks supporting the polyhedral model,Homogeneous space,Mathematics | Conference |
ISSN | Citations | PageRank |
2374-9660 | 5 | 0.43 |
References | Authors | |
7 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jayant Apte | 1 | 22 | 2.65 |
John MacLaren Walsh | 2 | 107 | 17.90 |