View Item 
      •   Home
      • 1. Schools
      • College of Science
      • School of Physical and Mathematical Sciences (SPMS)
      • SPMS Conference Papers
      • View Item
      •   Home
      • 1. Schools
      • College of Science
      • School of Physical and Mathematical Sciences (SPMS)
      • SPMS Conference Papers
      • View Item
      JavaScript is disabled for your browser. Some features of this site may not work without it.
      Subject Lookup

      Browse

      All of DR-NTUCommunities & CollectionsTitlesAuthorsBy DateSubjectsThis CollectionTitlesAuthorsBy DateSubjects

      My Account

      Login

      Statistics

      Most Popular ItemsStatistics by CountryMost Popular Authors

      About DR-NTU

      Optimal index codes with near-extreme rates

      Thumbnail
      Author
      Dau, Son Hoang
      Skachek, Vitaly
      Chee, Yeow Meng
      Date of Issue
      2012
      Conference Name
      IEEE International Symposium on Information Theory (2012 : Cambridge, US)
      School
      School of Physical and Mathematical Sciences
      Abstract
      The min-rank of a digraph was shown by Bar-Yossef et al. (2006) to represent the length of an optimal scalar linear solution of the corresponding instance of the Index Coding with Side Information (ICSI) problem. In this work, the graphs and digraphs of near-extreme min-ranks are characterized. Those graphs and digraphs correspond to the ICSI instances having near-extreme transmission rates when using optimal scalar linear index codes. It is also shown that the decision problem of whether a digraph has min-rank two is NP-complete. By contrast, the same question for graphs can be answered in polynomial time.
      Subject
      DRNTU::Science::Mathematics
      Type
      Conference Paper
      Collections
      • SPMS Conference Papers
      http://dx.doi.org/10.1109/ISIT.2012.6283852
      Get published version (via Digital Object Identifier)

      Show full item record


      NTU Library, Nanyang Avenue, Singapore 639798 © 2011 Nanyang Technological University. All rights reserved.
      DSpace software copyright © 2002-2015  DuraSpace
      Contact Us | Send Feedback
      Share |    
      Theme by 
      Atmire NV
       

       


      NTU Library, Nanyang Avenue, Singapore 639798 © 2011 Nanyang Technological University. All rights reserved.
      DSpace software copyright © 2002-2015  DuraSpace
      Contact Us | Send Feedback
      Share |    
      Theme by 
      Atmire NV
       

       

      DCSIMG