Linear Time Algorithms to the Minimum All-Ones Problem for Unicyclic and Bicyclic Graphs

William Y.C. Chen, Xueliang Li, Chao Wang and Xiaoyan Zhang

  Abstract:  In this paper, we give graph-theoretic algorithms of linear time to the Minimum All-Ones Problem for unicyclic and bicyclic graphs. These algorithms are based on a graph-theoretic algorithm of linear time to the Minimum All-Ones Problem with Restrictions for trees.

  AMS Classification:  05C85, 05C70, 90C27, 68Q25, 68R10.

  Keywords:  (Minimum) All-Ones Problem; graph-theoretic algorithm; linear time.

  Download:   pdf   

Return