Computational and Theoretical Challenges for Computing the Minimum Rank of a Graph

Research output: Contribution to journal › Journal article › Research › peer-review

Standard

Computational and Theoretical Challenges for Computing the Minimum Rank of a Graph. / Hicks, Illya V.; Brimkov, Boris; Deaett, Louis; Haas, Ruth; Mikesell, Derek; Roberson, David; Smith, Logan.

In: INFORMS Journal on Computing, Vol. 34, No. 6, 2022, p. 2868-2872.

Research output: Contribution to journal › Journal article › Research › peer-review

Harvard

Hicks, IV, Brimkov, B, Deaett, L, Haas, R, Mikesell, D, Roberson, D & Smith, L 2022, 'Computational and Theoretical Challenges for Computing the Minimum Rank of a Graph', INFORMS Journal on Computing, vol. 34, no. 6, pp. 2868-2872. https://doi.org/10.1287/ijoc.2022.1219

APA

Hicks, I. V., Brimkov, B., Deaett, L., Haas, R., Mikesell, D., Roberson, D., & Smith, L. (2022). Computational and Theoretical Challenges for Computing the Minimum Rank of a Graph. INFORMS Journal on Computing, 34(6), 2868-2872. https://doi.org/10.1287/ijoc.2022.1219

Vancouver

Hicks IV, Brimkov B, Deaett L, Haas R, Mikesell D, Roberson D et al. Computational and Theoretical Challenges for Computing the Minimum Rank of a Graph. INFORMS Journal on Computing. 2022;34(6):2868-2872. https://doi.org/10.1287/ijoc.2022.1219

Author

Hicks, Illya V. ; Brimkov, Boris ; Deaett, Louis ; Haas, Ruth ; Mikesell, Derek ; Roberson, David ; Smith, Logan. / Computational and Theoretical Challenges for Computing the Minimum Rank of a Graph. In: INFORMS Journal on Computing. 2022 ; Vol. 34, No. 6. pp. 2868-2872.

Bibtex

@article{315d9ef0579b465aaab37f4ce5d0120d,
title = "Computational and Theoretical Challenges for Computing the Minimum Rank of a Graph",
abstract = "The minimum rank of a graph G is the minimum of the ranks of all symmetric adjacency matrices of G. We present a new combinatorial bound for the minimum rank of an arbitrary graph G based on enumerating certain subsets of vertices of G satisfying matroid theoretic properties. We also present some computational and theoretical challenges associated with computing the minimum rank. This includes a conjecture that this bound on the minimum rank actually holds with equality for all graphs.",
keywords = "forts, matroid, maximum nullity, minimum rank, zero forcing",
author = "Hicks, {Illya V.} and Boris Brimkov and Louis Deaett and Ruth Haas and Derek Mikesell and David Roberson and Logan Smith",
note = "Publisher Copyright: {\textcopyright} 2022 INFORMS.",
year = "2022",
doi = "10.1287/ijoc.2022.1219",
language = "English",
volume = "34",
pages = "2868--2872",
journal = "INFORMS Journal on Computing",
issn = "1091-9856",
publisher = "Institute for Operations Research and the Management Sciences (I N F O R M S)",
number = "6",

}

RIS

TY - JOUR

T1 - Computational and Theoretical Challenges for Computing the Minimum Rank of a Graph

AU - Hicks, Illya V.

AU - Brimkov, Boris

AU - Deaett, Louis

AU - Haas, Ruth

AU - Mikesell, Derek

AU - Roberson, David

AU - Smith, Logan

N1 - Publisher Copyright: © 2022 INFORMS.

PY - 2022

Y1 - 2022

N2 - The minimum rank of a graph G is the minimum of the ranks of all symmetric adjacency matrices of G. We present a new combinatorial bound for the minimum rank of an arbitrary graph G based on enumerating certain subsets of vertices of G satisfying matroid theoretic properties. We also present some computational and theoretical challenges associated with computing the minimum rank. This includes a conjecture that this bound on the minimum rank actually holds with equality for all graphs.

AB - The minimum rank of a graph G is the minimum of the ranks of all symmetric adjacency matrices of G. We present a new combinatorial bound for the minimum rank of an arbitrary graph G based on enumerating certain subsets of vertices of G satisfying matroid theoretic properties. We also present some computational and theoretical challenges associated with computing the minimum rank. This includes a conjecture that this bound on the minimum rank actually holds with equality for all graphs.

KW - forts

KW - matroid

KW - maximum nullity

KW - minimum rank

KW - zero forcing

UR - http://www.scopus.com/inward/record.url?scp=85146334801&partnerID=8YFLogxK

U2 - 10.1287/ijoc.2022.1219

DO - 10.1287/ijoc.2022.1219

M3 - Journal article

AN - SCOPUS:85146334801

VL - 34

SP - 2868

EP - 2872

JO - INFORMS Journal on Computing

JF - INFORMS Journal on Computing

SN - 1091-9856

IS - 6

ER -

ID: 334253415