|
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 |
Attachment:
example.pdf
Description: Adobe PDF document
_______________________________________________ Compgeom-discuss mailing list Compgeom-discuss@compgeom.poly.edu http://compgeom.poly.edu/mailman/listinfo/compgeom-discuss