Mathematics & Statistics Faculty

Permanent URI for this communityhttps://hdl.handle.net/10294/4260

Browse

Browsing Mathematics & Statistics Faculty by Subject "complexity"

Filter results by typing the first few letters
Now showing 1 - 1 of 1
  • Thumbnail Image
    ItemOpen Access
    On the complexity of the positive semidefinite zero forcing number
    (Elsevier, 2015) Meagher, Karen; Fallat, Shaun; Yang, Boting
    The positive semidefinite zero forcing number of a graph is a graph parameter that arises from a non-traditional type of graph colouring and is related to a more conventional version of zero forcing. We establish a relation between the zero forcing and the fast–mixed searching, which implies some NP-completeness results for the zero forcing problem. Relationships between positive semidefinite zero forcing sets and clique coverings are well-understood for chordal graphs. Building upon constructions associated with optimal tree covers and forest covers, we present a linear time algorithm for computing the positive semidefinite zero forcing number of chordal graphs. We also prove that it is NP-complete to determine whether a graph has a positive semidefinite zero forcing set with an additional property.