Well, I'm facing a problem with a small work I have in hands right now...
The main goal is, having a given graph (without weights, and directed), I have to discover the group of paths(if possible, only one path, but they can be more) with minimum total length, that cover all edges. Other "constraint" is that the graph, is a DFA, so the paths should start in an initial state, and end in an acceptance state (they're marked).
Initially I found that this was similar to the Chinese Postman Problem, and in fact, it is. But in my case, the graph is directed (I believe this changes thing a bit), and there isn't any problem in processing an edge more than once, since the resultant path remains the shortest.
I've read some things about Euler paths, and T-Joins, and this is probably the solution to my problem. If I understood it right, what I should do is to find an Euler path in my graph and, if there isn't one, make it exist, duplicating the T-Joins, or something like that... I had lots of trouble understanding this, I don't even know if this is the answer to my problem... (shortest and most understandable text I found here: http://en.wikipedia.org/wiki/Route_inspection_problem)
Just to leave a short example, given this graph (1 is initial and 5 is acceptance):
1 -> 2;
2 -> 3;
2 -> 4;
4 -> 5;
The answer to my problem should be: 1 -> 2 -> 4 -> 5 and 1 -> 2 -> 3. (In this case I would also have to handle the fact that 3 isn't an acceptance state, but that edge had to be covered. But I can easily get through that by flagging all the states with no edges to other nodes as acceptance states).
Hope I explained everything well enough.
Thanks in advance!