From: Luis Goddyn <goddyn@math.sfu.ca>
Newsgroups: sci.math
Subject: Re: graph theory / optimal Eulerization
Date: Tue, 20 Oct 1998 14:44:37 -0700

Peter M Asman wrote:

>
>         How does one know whether an eulerization of a graph is
>         optimal?
>
> A related question:
>
>         How does one know whether a semi-eulerization of a graph is
>         optimal?
>

The first problem is commonly known as the "Chinese Postman Problem".
Its solution
appears in many standard Discrete Optimization Text (such as Lawler or
Papadimitriou/
Steiglitz).  It can be solved in polynomial time:
(1)  Find the set W of odd-degree vertices.
 (2)  Find distances d(u,v)  in the graph between all distinct pairs u,v
in W.
 (3)  Let (H,d) be the edge weighted complete graph with vertex set W and
d(u,v) as above.
 (4)  Find a minimum total weight perfect matching in (M,d) (using, say,
Edmond's weighted
        matching algorithm).
 (5)  For each {u,v} in M, duplicate the edges along a shortest
(u,v)-path in G.
Any Euler tour of the resulting graph corresponds a shortest possible
walk in G which
traverses each edge at least once.

The second problem (I believe you are aiming to produce produce a graph
with exactly
two odd vertices) should be solved almost exactly the same way, except
that in
step (4) you want an optimal matching (H,d) having exactly |V(H)|/2-1
edges.  Off
the top of my head, this can be done either with several applications of
Edmonds'
algorithm, or by adding two new vertices to H each having a large
negative to each vertex of H.

--
---                                                      _____._____
Luis Goddyn                 email: goddyn@math.sfu.ca   /|   /|\   |\
Dept. of Math. and Stats.    http://www.sfu.ca/~goddyn /_|__/ | \__|_\
Simon Fraser University       tel: (604) 291-4699      | |__|_|_|__| |
Burnaby BC  V5A 1S6           msg:          -3331      | /  | ^ |  \ |
CANADA                        fax:          -4947      |/___|/ \|___\|