Ecole d'ingénieur et centre de recherche en Sciences du numérique

Fractional coloring (orthogonal access) achieves all-unicast capacity (DoF) region of index coding (TIM) if and only if network topology is chordal

Yi, Xinping; Sun, Hua; Jafar, Syed A; Gesbert, David

Submitted to ArXiv on January 30, 2015

The main result of this work is that fractional coloring (orthogonal access) achieves the all-unicast capacity (degrees of freedom (DoF)) region of the index coding (topological interference management (TIM)) problem if and only if the bipartite network topology graph (with sources on one side and destinations on the other, and edges identifying presence of nontrivial channels whose communication capacity is not zero or infinity) is chordal, i.e., every cycle that can contain a chord, does contain a chord. The all-unicast capacity (DoF) region includes the capacity (DoF) region for any arbitrary choice of a unicast message set, so e.g., the results of Maleki and Jafar on the optimality of orthogonal access for the sum-capacity (DoF) of one-dimensional convex networks are recovered as a special case.

Arxiv Bibtex

Titre:Fractional coloring (orthogonal access) achieves all-unicast capacity (DoF) region of index coding (TIM) if and only if network topology is chordal
Type:Conférence
Langue:English
Ville:
Date:
Département:Systèmes de Communication
Eurecom ref:4753
Copyright: © EURECOM. Personal use of this material is permitted. The definitive version of this paper was published in Submitted to ArXiv on January 30, 2015 and is available at :
Bibtex: @inproceedings{EURECOM+4753, year = {2015}, title = {{F}ractional coloring (orthogonal access) achieves all-unicast capacity ({D}o{F}) region of index coding ({TIM}) if and only if network topology is chordal}, author = {{Y}i, {X}inping and {S}un, {H}ua and {J}afar, {S}yed {A} and {G}esbert, {D}avid }, booktitle = {{S}ubmitted to {A}r{X}iv on {J}anuary 30, 2015}, address = {}, month = {01}, url = {http://www.eurecom.fr/publication/4753} }
Voir aussi: