From: Luis Goddyn 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 |/___|/ \|___\|