Title | ||
---|---|---|
Algorithms for computing network coding rate regions via single element extensions of matroids |
Abstract | ||
---|---|---|
We propose algorithms for finding extreme rays of rate regions achievable with vector linear codes over finite fields Fq, q ∈ {2, 3, 4} for which there are known forbidden minors for matroid representability. We use the idea of single element extensions (SEEs) of matroids and enumeration of non-isomorphic matroids using SEEs, to first propose an algorithm to obtain lists of all non-isomorphic matroids representable over a given finite field.We modify this algorithm to produce only the list of all non-isomorphic connected matroids representable over the given finite field. We then integrate the process of testing which matroids in a list of matroids form valid linear network codes for a given network within matroid enumeration. We name this algorithm, which essentially builds all matroids that form valid network codes for a given network from scratch, as network-constrained matroid enumeration. |
Year | DOI | Venue |
---|---|---|
2014 | 10.1109/ISIT.2014.6875245 | Information Theory |
Keywords | DocType | Citations |
combinatorial mathematics,linear codes,matrix algebra,network coding,vectors,SEE,extreme rays,finite fields,linear network codes,matroid representability,network coding rate regions,network-constrained matroid enumeration,nonisomorphic matroids,single element extensions,vector linear codes,Single emement extensions,rate regions of multi-source network coding problems,region of entropic vectors | Conference | 3 |
PageRank | References | Authors |
0.45 | 0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jayant Apte | 1 | 22 | 2.65 |
Congduan Li | 2 | 40 | 7.75 |
John MacLaren Walsh | 3 | 107 | 17.90 |