Postmen deliver letters down roads. The Chinese Postman Problem is to find
the shortest route in a network that uses every arc (directed edge) and gets
back to where they started (closed problem) or doesn't go back (open problem).
There are many further variations on the problem, but we are concerned with
weighted directed graphs with (possible) parallel arcs, so-called weighted multidigraphs
-- what the world wide web is made out of from its HTML links, which are directed
and may be repeated. We allow weights because we might, for example, be interested
in how long a user takes to explore a web site, so the weights could be measured
in seconds.

Here is a simple graph, and below are postman tours of the graph that were output
by the Java program you can get from this site.

The following is a closed tour of minimal weight, taking each arc
to have equal weight.

The following is an open tour of minimal weight, where an open tour visits every arc but does
not necessarily return to where it started. The 'virtual arcs' are an artifact of the way the
tour is worked out: the algorithm works by finding the best way to place two virtual arcs on
a graph and solving the closed problem that uses them - hence vertex 4 is not really part of the graph!

*Resources available*

The complete paper is available in PostScript and
PDF. It will appear in due course in *Software Practice
& Experience*.

## In Java

Code is available in Java as CPP.java.

If you want see how to extract the code used in the paper from the Java source
file, look up warp.

## In Mathematica

- Mathematica notebook. Best if you
set your browser preferences to recognise ".nb" to be run by Mathematica.
- HTML version (readable if you do not have access
to Mathematica).

The *Mathematica* files also include the definition of the Nokia phone
used in the paper.

You can obtain a Mathematica reader from Wolfram Research. You can probably
set up you web browser so that Mathematica notebooks are automatically
opened in the reader. If you have Mathematica itself, notebooks
can be executed to run the algorithm as well.

## Other web sites

See also the pages at the Algorithm
Design Manual, which covers many useful algorithms.

One form of flattery is plagiarism: see a poster
"ON EXERCISING EVERY LINK OF A WEB-SITE WITH MINIMAL EFFORT" by Vaidyanathan
Sivaraman presented at The International
Conference on High Performance Computing (HiPC), 2002. Or see this local
copy, made April 2003: in MS Word or PDF.