Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

The Eulerian Tour problem is of course a well-studied classical problem in graph theory (Wikipedia article). This question concerns non-Eulerian graphs; i.e., graphs that contain one or more odd-degree vertices. In a nutshell, I wonder what is the best "Eulerian-like" way of traversing non-Eulerian graphs.

Given an undirected connected graph, let an Eulerian "semi-tour" be defined as a "cycle" that passes each edge at least once and can visit any vertex or edge multiple times. Consider the following costs for a given semi-tour:

  1. Total cost: The total number of edges visited by the semi-tour, counting multiplicities.

  2. Width cost: The number of times the most-visited edge is visited.

I'm interested in optimization problems that aim to find a semi-tour that minimizes the total cost or the width cost on a given graph. Of course, if a graph is Eulerian, an Eulerian tour would be optimal, for which the total cost is the number of edges and the width cost is zero. For graphs containing odd degree vertices, the optimal cost in both senses must be larger.

I suspect these optimization problems (if not trivial) must have been well studied in the literature. What are the relevant references, if any, and what is known about these problems (both algorithmically and combinatorially)?

share|improve this question
    
I wonder what happens if you do the Christofides trick: find a "min congestion matching" on the odd degree vertices and then run the Euler tour –  Suresh Venkat Jan 7 '13 at 21:16
add comment

1 Answer 1

up vote 7 down vote accepted

For total cost, see http://en.wikipedia.org/wiki/Route_inspection_problem (also called the Chinese postman problem). The optimal solutions to this problem visit each edge at most twice, so they also optimize your width cost.

share|improve this answer
    
Great, that seems to be what I had in mind. –  MCH Jan 7 '13 at 22:47
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.