On the complexity of failed zero forcing

DOI10.1016/j.tcs.2016.11.032zbMath1357.05126arXiv1609.00211OpenAlexW2963729907MaRDI QIDQ729899

Yaroslav N. Shitov

Publication date: 22 December 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1609.00211

zbMATH Keywords

zero forcing

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Improved Computational Approaches and Heuristics for Zero Forcing, On the zero blocking number of rectangular, cylindrical, and Möbius grids, Immune sets in monotone infection rules. Characterization and complexity, An integer program for positive semidefinite zero forcing in graphs, Failed zero forcing and critical sets on directed graphs, Blocking zero forcing processes in Cartesian products of graphs, Sparks of symmetric matrices and their graphs, Failed power domination on graphs

Cites Work

• Failed skew zero forcing on a graph
• Fast-mixed searching and related problems on graphs
• Zero forcing parameters and minimum rank problems
• Zero forcing sets and the minimum rank of graphs
• Positive Semidefinite Zero Forcing: Complexity and Lower Bounds
• Reducibility among Combinatorial Problems
• On the complexity of the positive semidefinite zero forcing number