A new index coding scheme exploiting interlinked cycles

Title: A new index coding scheme exploiting interlinked cycles
Creator: Thapa, Chandra; Ong, Lawrence; Johnson, Sarah J.
Relation: 2015 IEEE International Symposium on Information Theory (ISIT) . Proceedings of the 2015 IEEE International Symposium on Information Theory (Hong Kong 14-19 June, 2015) p. 1024-1028
Relation: ARC.FT110100195, ARC.FT140100219 & ARC.DP150100903 http://purl.org/au-research/grants/arc/DP150100903
Publisher Link: http://dx.doi.org/10.1109/ISIT.2015.7282610
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Resource Type: conference paper
Date: 2015
Description: We study the index coding problem in the unicast message setting, i.e., where each message is requested by one unique receiver. This problem can be modeled by a directed graph. We propose a new scheme called interlinked cycle cover, which exploits interlinked cycles in the directed graph, for designing index codes. This new scheme generalizes the existing clique cover and cycle cover schemes. We prove that for a class of infinitely many digraphs with messages of any length, interlinked cycle cover provides an optimal index code. Furthermore, the index code is linear with linear time encoding complexity.
Subject: index coding; unicast; optimal broadcast rate; linear codes; interlinked cycles
Identifier: http://hdl.handle.net/1959.13/1315201
Identifier: uon:22912
Identifier: ISBN:9781467377041
Language: eng
Reviewed

		Thumbnail	File	Description	Size	Format