Next:
Vertex Ordering
Up:
Subgraphs and Supergraphs
Previous:
GT37 MINIMUM CHORDAL
GT38 M
AXIMUM
C
ONSTRAINED
H
AMILTONIAN
C
IRCUIT
I
NSTANCE
: Graph
and subset
of the edges.
S
OLUTION
: A Hamiltonian circuit
C
in
G
, i.e., a circuit that visits every vertex in
V
once.
M
EASURE
: Cardinality of the edges in
S
that are used in the circuit
C
, i.e.,
.
Bad News:
Not approximable within
for some
[
352
].
Comment:
Variation in which the graph is directed has the same bad news [
352
].
Garey and Johnson:
Similar to GT37 and GT38
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997
and subset
of the edges.
.
for some
[
352
].