Re: A letter want to disprove my paper which submitted recently

Thank you for you comments.


t...@xxxxxxxxxxxxx

In article <f5bsg5$c7p$1@xxxxxxxxxxxxxxx>, Rod Howell <rhowell@xxxxxxx> wrote:
He is claiming that Plesnik's proof is for planar graphs in which each
vertex has at most 2 outgoing edges, but arbitrarily many incoming
edges. I haven't been able to track down Plesnik's paper, so I don't
know whether this is the case. Plesnik's title is ambiguous in this regard.

For the benefit of others reading this, Plesnik's paper is:

J. Plesnik, The NP-completeness of the Hamiltonian cycle problem in
planar digraphs with degree bound two, Inform. Process. Lett. 8 (1979),
no. 4, 199-201.

I just looked at this paper in our library, and Plesnik's result, as
correctly reported by Zhu, is that the directed Hamiltonian path problem
remains NP-complete even if we restrict to the class of planar digraphs
in which every vertex has either (a) indegree 1 and outdegree 2, or
(b) indegree 2 and outdegree 1.
--

Yes, Plesnik's constraints on the planar digraphs $D$ with either
(a) indegree 1 and outdegree 2, or (b) indegree 2 and outdegree 1.

The worst cases of enumeration all of cycle of length $n$, including
all isomorphism and disjoint cycle length of $n$, which is
exponent. If considering the HC from this method, Plesnik's
results is correctly.

But if considering the isomorphism, there are at most $n$ number of
isomorphism simple cycles length of $n$ , where isomorphism is defined
by the same rank of a transform of $D$(please ref my draft if you are
free and interested). thus it is only need polynomial time, and my
results is correctly.

The same principle, if you want to finding a perfect matching in a
bipartite graph by enumerate all maximal matching method, the worst
is exponent; But in fact , you only need find one maximal
matching, the worst is in polynomial.
---------------------------
Best regards,
Zhu










Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences

.

Relevant Pages

  • Re: A letter want to disprove my paper which submitted recently
    ... Determining Existence a Hamiltonian Cycle is O". ... one's mileage may differ for 0-node and 1-node graphs.) ... as it deals with digraphs with up to 2 incoming edges and up to 2 ... outgoing edges - not a total of at most 2 incoming + outgoing, ...
    (comp.theory)
  • Re: Armstrong and Virdings One Pass GC
    ... a data structure with a change in a cycle, ... I could imagine implementations that use sparse-matrix organisations, and implementations that construct a function that returns the list of outgoing edges for a given node. ...
    (comp.lang.functional)