%0 Journal Article
%T Three New Versions of the All-ones Problem<br>三种新变形的全一问题
%A Li Xueliang
%A Zhang Xiaoyan
%A <br>李学良
%A 张晓岩
%J 数学物理学报(A辑)
%D 2008
%I 
%X The authors study three new versions of the all-ones problem and the minimum all-ones problem. The original all-ones problem is simply called the vertex-vertex problem, and the three new versions are called the vertex-edge problem, the edge-vertex problem and the edge-edge problem, respectively. The vertex-vertex problem is studied extensively. For example, the existence of solutions and efficient algorithms for finding solutions are obtained, and the minimum vertex-vertex problem for general graphs is shown to be NP-complete, however for trees, unicyclic and bicyclic graphs it can be solved in linear time, etc. In this paper, for the vertex-edge problem, the authors show that a graph has a solution if and only if it is bipartite, and therefore it has only two possible solutions and optimal solutions. For the edge-vertex problem, the authors show that a graph has a solution if and only if it contains even number of vertices. By showing that the minimum edge-vertex problem can be polynomially transformed into the minimum weight perfect matching problem, the authors obtain that the minimum edge-vertex problem can be solved in polynomial time in general. The edge-edge problem is reduced to the vertex-vertex problem for the line graph of a graph.
%K All-ones problemzz
%K Minimum weight perfect matchingzz
%K Graph algorithmzz<br>全一问题
%K 最小权的完美匹配
%K 图算法
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=6E709DC38FA1D09A4B578DD0906875B5B44D4D294832BB8E&cid=37F46C35E03B4B86&jid=4DB553CDB5F521D8C921082E5C95EC80&aid=546C07860D5E9B6642C8BB761CA1DD4E&yid=67289AFF6305E306&vid=D3E34374A0D77D7F&iid=E158A972A605785F&sid=06D504E5261AB652&eid=C824C8F9F54AE9B9&journal_id=1003-3998&journal_name=数学物理学报(A辑)&referenced_num=0&reference_num=17