Approximating the minimum rank of a graph via alternating projection
2016
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.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
29
References
1
Citations
NaN
KQI