Polynomial time algorithm for min-ranks of graphs with simple tree structures

DOI10.1007/S00453-013-9789-9MaRDI QIDQ2258079zbMATH OpenOpenAlexFDO

Authors Son Hoang Dau, Yeow Meng Chee

Publication date 2 March 2015

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.6832

zbMATH Keywords

dynamic~programmingindex codingmin-ranknetwork codingpolynomial timetree structure

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Abstract: The min-rank of a graph was introduced by Haemers (1978) to bound the Shannon capacity of a graph. This parameter of a graph has recently gained much more attention from the research community after the work of Bar-Yossef et al. (2006). In their paper, it was shown that the min-rank of a graph G characterizes the optimal scalar linear solution of an instance of the Index Coding with Side Information (ICSI) problem described by the graph G. It was shown by Peeters (1996) that computing the min-rank of a general graph is an NP-hard problem. There are very few known families of graphs whose min-ranks can be found in polynomial time. In this work, we introduce a new family of graphs with efficiently computed min-ranks. Specifically, we establish a polynomial time dynamic programming algorithm to compute the min-ranks of graphs having simple tree structures. Intuitively, such graphs are obtained by gluing together, in a tree-like structure, any set of graphs for which the min-ranks can be determined in polynomial time. A polynomial time algorithm to recognize such graphs is also proposed.

Recommendations

• Linear index coding via semidefinite programming
• Linear index coding via semidefinite programming
• The minrank of random graphs
• On minrank and forbidden subgraphs
• On minrank and forbidden subgraphs

Cites work

• A note on finding the bridges of a graph
• scientific article; zbMATH DE number 5454110 (Why is no real title available?)
• scientific article; zbMATH DE number 4049084 (Why is no real title available?)
• scientific article; zbMATH DE number 3745081 (Why is no real title available?)
• scientific article; zbMATH DE number 3259770 (Why is no real title available?)
• Index Coding With Side Information
• Linear index coding via semidefinite programming
• Network information flow
• On the Index Coding Problem and Its Relation to Network Coding and Matroid Theory
• On the Shannon capacity of a graph
• Orthogonal representations over finite fields and the chromatic number of graphs
• The strong perfect graph theorem
• Theory and Applications of Satisfiability Testing

Cited in

(4)

• Polynomial Time Algorithms for the MIN CUT Problem on Degree Restricted Trees
• The minrank of random graphs
• Linear index coding via semidefinite programming
• Linear index coding via semidefinite programming

Describes a project that uses

Uses Software

• MiniSat

This page was built for publication: Polynomial time algorithm for min-ranks of graphs with simple tree structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2258079)