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