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=![empty set empty set](http://www.sciencedirect.com/scidirimg/entities/2205.gif)
, 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.