On the complexity of the positive semidefinite zero forcing number

Simple item page
dc.contributor.authorMeagher, Karen
dc.contributor.authorFallat, Shaun
dc.contributor.authorYang, Boting
dc.date.accessioned2015-05-12T16:33:17Z
dc.date.available2015-05-12T16:33:17Z
dc.date.issued2015
dc.description.abstractThe 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.en_US
dc.description.authorstatusFacultyen_US
dc.description.peerreviewyesen_US
dc.description.sponsorshipNSERCen_US
dc.identifier.urihttps://hdl.handle.net/10294/5691
dc.language.isoenen_US
dc.publisherElsevieren_US
dc.subjectcomplexityen_US
dc.subjectzero forcingen_US
dc.subjectclique cover numberen_US
dc.titleOn the complexity of the positive semidefinite zero forcing numberen_US
dc.typeArticleen_US
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
complexity-zplus-laa.pdf
Size:
979.61 KB
Format:
Adobe Portable Document Format
Description:
main article
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
2.24 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Shaun Fallat