Subject: [Compgeom-discuss] the complexity of a walk

From: "Ali Mohades" <[email-masked]>
Date: Tue, 7 Feb 2006 13:55:41 -0800

Dear all:

 I am touching the following problem

Having a graph   G(V1UV2 , E)  in which the degree of all vertices in V2 is even.

 A tourist wants to take a close walk such that:

1:  All vertices in V2 are visited at least once.

2:  All vertices in V2 are visited at most once.

3: The tourist chooses the middle edge to exit when he visit a vertex from  V2  satisfy in 2 and 3 as most as possible.

What is the complexity of the finding this walk?

Is it NP-complete?

 An example is attached.

Regards
Ali Mohades
-----------------------------------------------------
Department of  Computer Science
Faculty of Math & Computer Science
Amirkabir University of Technology
424 Hafez Avenue
Tehran 15914
Iran