The general σ all-ones problem for trees
- 作者：Xueliang Li ; Chao Wang ; Xiaoyan Zhang
- 关键词：(minimum) (general) none ; color ; black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6TYW-4PT1P0J-2&_mathId=mml27&_user=1067359&_cdi=5629&_rdoc=20&_acct=C000050221&_version=1&_userid=10&md5=a519d0531708d43
- 刊名：Discrete Applied Mathematics
- 出版年：2008
- 期刊代码：46_0166218x
- 类别：cp
- 出版时间：28 May 2008
- 卷：156
- 期：10
- 页码：1790-1801
- 文件大小：258 K
摘要
The general 0J-2&_mathId=mml7&_user=1067359&_cdi=5629&_rdoc=20&_acct=C000050221&_version=1&_userid=10&md5=1c43797ca5a1c3a5d0589701bed5b545" title="Click to view the MathML source" alt="Click to view the MathML source">σ all-ones problem is defined as follows: Given a graph G=(V,E), where V and E denote the vertex-set and the edge-set of G, respectively. Denote C as an initial subset of V. The problem is to find a subset X of V such that for every vertex v of 25912a9ee710fa88a" title="Click to view the MathML source" alt="Click to view the MathML source">G
C the number of vertices in X adjacent to v is odd while for every vertex v of C the number is even. X is called a solution to the problem. When C=
, this problem is the so-called σ all-ones problem. If a vertex is viewed to be adjacent to itself, the σ all-ones problem is addressed as the 2547c05c7c1f6fe8b" title="Click to view the MathML source" alt="Click to view the MathML source">σ+ all-ones problem. The 707c9" title="Click to view the MathML source" alt="Click to view the MathML source">σ+ all-ones problem has been studied extensively. However, the σ all-ones problem has received much less attention. Unlike the σ+ all-ones problem, which has solutions for any graphs, the σ all-ones problem may not have solutions for many graphs, even for some very simple graphs like C3 and P5. So, it becomes an interesting question to find polynomial time algorithms to determine if for a given tree the problem has solutions. And if it does, to find a solution to the minimum σ all-ones problem. In this paper we present two algorithms of linear time to solve the general 2577acf96f68bb9fa175deef29ac6d" title="Click to view the MathML source" alt="Click to view the MathML source">σ all-ones problem for trees. The first one is good for counting the number of solutions if solutions do exist, and the second one is good for solving the minimum 25">25&_user=1067359&_cdi=5629&_rdoc=20&_acct=C000050221&_version=1&_userid=10&md5=4c33f6b8b64935cac74ef5242d55ae8d" title="Click to view the MathML source" alt="Click to view the MathML source">σ all-ones problem. Furthermore, we can modify the algorithm slightly to solve the general minimum σ all-ones problem.
C the number of vertices in X adjacent to v is odd while for every vertex v of C the number is even. X is called a solution to the problem. When C=, this problem is the so-called σ all-ones problem. If a vertex is viewed to be adjacent to itself, the σ all-ones problem is addressed as the 2547c05c7c1f6fe8b" title="Click to view the MathML source" alt="Click to view the MathML source">σ+ all-ones problem. The 707c9" title="Click to view the MathML source" alt="Click to view the MathML source">σ+ all-ones problem has been studied extensively. However, the σ all-ones problem has received much less attention. Unlike the σ+ all-ones problem, which has solutions for any graphs, the σ all-ones problem may not have solutions for many graphs, even for some very simple graphs like C3 and P5. So, it becomes an interesting question to find polynomial time algorithms to determine if for a given tree the problem has solutions. And if it does, to find a solution to the minimum σ all-ones problem. In this paper we present two algorithms of linear time to solve the general 2577acf96f68bb9fa175deef29ac6d" title="Click to view the MathML source" alt="Click to view the MathML source">σ all-ones problem for trees. The first one is good for counting the number of solutions if solutions do exist, and the second one is good for solving the minimum 25">25&_user=1067359&_cdi=5629&_rdoc=20&_acct=C000050221&_version=1&_userid=10&md5=4c33f6b8b64935cac74ef5242d55ae8d" title="Click to view the MathML source" alt="Click to view the MathML source">σ all-ones problem. Furthermore, we can modify the algorithm slightly to solve the general minimum σ all-ones problem.