New versions of the all-ones problem

Simple item page
dc.creatorLi, Xueliang
dc.creatorZhang, Xiaoyan
dc.date2005-12-01
dc.date.accessioned2026-07-07T06:54:44Z
dc.date.available2026-07-07T06:54:44Z
dc.descriptionWe 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 has been studied extensively. For example, existence of solutions and efficient algorithms for finding solutions were obtained, and the Minimum Vertex-Vertex Problem for general graphs was shown to be NP-complete and for trees it can be solved in linear time, etc. In this paper, for the Vertex-Edge Problem, we 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. A linear program version is also given. For the Edge-Vertex Problem, we 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, we 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.
dc.description12 pages
dc.identifierhttps://arxiv.org/abs/math/0512011
dc.identifierhttp://arxiv.org/abs/math/0512011
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/106044
dc.subjectCombinatorics
dc.subject05C85; 05C70; 90C27; 68Q25; 68R10
dc.titleNew versions of the all-ones problem
dc.typetext

Files

Collections

arXiv