Polynomial Time Algorithm for Min-Ranks of Graphs with Simple Tree Structures

Son Hoang Dau, Yeow Meng Chee

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 resear…