Computational approaches for zero forcing and related problems

被引:22
|
作者
Brimkov, Boris [1 ]
Fast, Caleb C. [1 ,2 ]
Hicks, Illya V. [1 ]
机构
[1] Rice Univ, Dept Computat & Appl Math, 6100 Main St MS-134, Houston, TX 77005 USA
[2] FedEx Express, Business Analyt & Operat Res, 3680 Hacks Cross Rd Bldg H 2nd Floor, Memphis, TN 38125 USA
基金
美国国家科学基金会;
关键词
Combinatorial optimization; Zero forcing; Integer programming; Set-covering; CONNECTED DOMINATION; POWER DOMINATION; MINIMUM RANK; NUMBER; SETS; GRAPH;
D O I
10.1016/j.ejor.2018.09.030
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
In this paper, we propose computational approaches for the zero forcing problem, the connected zero forcing problem, and the problem of forcing a graph within a specified number of timesteps. Our approaches are based on a combination of integer programming models and combinatorial algorithms, and include formulations for zero forcing as a dynamic process, and as a set-covering problem. We explore several solution strategies for these models, test them on various types of graphs, and show that they are competitive with the state-of-the-art algorithm for zero forcing. Our proposed algorithms for connected zero forcing and for controlling the number of zero forcing timesteps are the first general-purpose computational methods for these problems, and are superior to brute force computation. (C) 2018 Elsevier B.V. All rights reserved.
引用
收藏
页码:889 / 903
页数:15
相关论文
共 50 条
  • [21] On Zero Forcing Sets and Network Controllability—Computation and Edge Augmentation
    Abbas, Waseem
    Shabbir, Mudassir
    Yazcoglu, Yasin
    Koutsoukos, Xenofon
    IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS, 2024, 11 (01): : 402 - 413
  • [22] Failed skew zero forcing on a graph
    Ansill, Thomas
    Jacob, Bonnie
    Penzellna, Jaime
    Saavedra, Daniel
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2016, 509 : 40 - 63
  • [23] Zero forcing of generalized hierarchical products
    Anderson, Sarah E.
    Kroschel, Brenda K.
    DISCRETE APPLIED MATHEMATICS, 2025, 366 : 120 - 126
  • [24] On Extremal Graphs for Zero Forcing Number
    Liang, Yi-Ping
    Li, Jianxi
    Xu, Shou-Jun
    GRAPHS AND COMBINATORICS, 2022, 38 (06)
  • [25] Fractional zero forcing via three-color forcing games
    Hogben, Leslie
    Palmowski, Kevin F.
    Roberson, David E.
    Young, Michael
    DISCRETE APPLIED MATHEMATICS, 2016, 213 : 114 - 129
  • [26] Zero forcing sets and bipartite circulants
    Meyer, Seth A.
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2012, 436 (04) : 888 - 900
  • [27] Characterization of All Graphs with a Failed Skew Zero Forcing Number of 1
    Johnson, Aidan
    Vick, Andrew E.
    Narayan, Darren A.
    MATHEMATICS, 2022, 10 (23)
  • [28] Bounds on Zero Forcing Using (Upper) Total Domination and Minimum Degree
    Bresar, Bostjan
    Cornet, Maria Gracia
    Dravec, Tanja
    Henning, Michael
    BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY, 2024, 47 (05)
  • [29] Zero Forcing in triangulations
    Hernandez, Gregorio
    Ranilla, Jose
    Ranilla-Cortina, Sandra
    JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, 2019, 354 : 123 - 130
  • [30] A New Lower Bound for Positive Zero Forcing
    Yang, Boting
    FRONTIERS IN ALGORITHMICS, FAW 2017, 2017, 10336 : 254 - 266