Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1142227 | Operations Research Letters | 2016 | 5 Pages |
Abstract
The minimum rank problem asks to find the minimum rank over all matrices with a given pattern associated with a graph. This problem is NP-hard, and there is no known approximation method. Further, this problem has no straightforward convex relaxation. In this article, a numerical algorithm is given to heuristically approximate the minimum rank using alternating projections. The effectiveness of this algorithm is demonstrated by comparing its results to a related parameter: the zero-forcing number. Using these methods, numerical evidence for the minimum rank graph complement conjecture is provided.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Franklin H.J. Kenter,