more again: the complexity of Hamiltonian problem on 2-regular digraph
- From: "Zhu Guohun" <ccghzhu@xxxxxxxxxxxxxxxxxxxx>
- Date: 27 Mar 2007 23:15:50 -0700
two month ago, I had send a draft to a professor that this problem is
polynomial, and post a thread about the complexity of Hamiltonian
problem on 2-regular digraph $D$, Now the problem is proved and
closed, I am not lie!
I am sure this is a polynomial time problem again, which could be
mapping into following problem.
1) max-2 SAT problem which is a NP-completed problem as search from
google, but I could not find where is the orignal proof , I think the
max-2 SAT is defined unclearly in the web?
2) a balanced bipartite undirected graph $G$ with degree 2, I proves
the complexity of finding the Hamiltonian cycle in $D$ from graph $G$
is no more than o(n^4). so it is P problem, in fact, many problem on
a undirected graph with degree 2 is always P problem.
In that cases P=NP .
Even the digraph with degree more than 3, it is also P problem
So where do I submit my draft ?
.
- Follow-Ups:
- Prev by Date: DBPL 2007 Call for Papers
- Next by Date: Re: question on variation of subset sum problem
- Previous by thread: DBPL 2007 Call for Papers
- Next by thread: Re: more again: the complexity of Hamiltonian problem on 2-regular digraph
- Index(es):
Relevant Pages
|
