Next:
ND36 MINIMUM STACKER
Up:
Routing Problems
Previous:
ND34 MINIMUM CHINESE
-
I
NSTANCE
:
Multigraph
, initial vertex
, length
for each
.
-
S
OLUTION
:
A collection of
k
cycles, each containing the initial vertex
,
that collectively traverse every edge in the graph at least once.
-
M
EASURE
:
The maximum length of the
k
cycles.
-
Good News:
Approximable within
2-1/k
[
112
].
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997