An approximation algorithm for zero forcing

DOI10.1016/J.DAM.2025.12.013MaRDI QIDQ6854633zbMATH OpenFDO

Authors Ben Cameron, Jeannette Janssen, Rogers Mathew, Zhiyuan Zhang

Publication date 24 February 2026

Published in Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

approximation algorithmpathwidthpath decompositionzero forcingvertex cuts

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15)

Cites work

• scientific article; zbMATH DE number 566078 (Why is no real title available?)
• scientific article; zbMATH DE number 6423647 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• A computational comparison of compact MILP formulations for the zero forcing number
• A technique for computing the zero forcing number of a graph with a cut-vertex
• Approximating Pathwidth for Graphs of Small Treewidth
• Approximation algorithms for treewidth, pathwidth, and treedepth -- a short survey
• Blocking zero forcing processes in Cartesian products of graphs
• Bounds on the connected forcing number of a graph
• Complexity of Finding Embeddings in a k-Tree
• Computational approaches for zero forcing and related problems
• Effects of vertex degrees on the zero-forcing number and propagation time of a graph
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Extremal values and bounds for the zero forcing number
• Families of graphs with maximum nullity equal to zero forcing number
• Fixed-parameter tractability of treewidth and pathwidth
• Graph minors. II. Algorithmic aspects of tree-width
• Improved Computational Approaches and Heuristics for Zero Forcing
• Matching, path covers, and total forcing sets
• Maximum nullity and zero forcing of circulant graphs
• New structures and their applications to variants of zero forcing and propagation time
• On extremal graphs for zero forcing number
• On minimum rank and zero forcing sets of a graph
• On the Structural and Strong Structural Controllability of Undirected Networks
• On the compatibility between a graph and a simple order
• On the diameter and zero forcing number of some graph classes in the Johnson, Grassmann and Hamming association scheme
• On the relationship between the zero forcing number and path cover number for some graphs
• On the zero blocking number of rectangular, cylindrical, and Möbius grids
• On the zero forcing number and spectral radius of graphs
• Propagation time for zero forcing on a graph
• The Zero Forcing Number of Graphs
• The minimum rank of symmetric matrices described by a graph: a survey
• The zero forcing number of graphs with the matching number and the cyclomatic number
• The zero forcing polynomial of a graph
• Throttling zero forcing propagation speed on graphs
• Tree-width, path-width, and cutwidth
• Treedepth vs circumference
• Treewidth. Computations and approximations
• Zero Forcing Sets and Controllability of Dynamical Systems Defined on Graphs
• Zero forcing in claw-free cubic graphs
• Zero forcing number of a graph in terms of the number of pendant vertices
• Zero forcing parameters and minimum rank problems
• Zero forcing sets and the minimum rank of graphs
• Zero-forcing in random regular graphs

This page was built for publication: An approximation algorithm for zero forcing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6854633)