Next:
Covering and Partitioning
Up:
A compendium of NP
Previous:
Improving the compendium
Index
Graph Theory
Graph Theory
Covering and Partitioning
M
INIMUM
V
ERTEX
C
OVER
M
INIMUM
D
OMINATING
S
ET
M
AXIMUM
D
OMATIC
P
ARTITION
M
INIMUM
E
DGE
D
OMINATING
S
ET
M
INIMUM
I
NDEPENDENT
D
OMINATING
S
ET
M
INIMUM
G
RAPH
C
OLORING
M
INIMUM
C
OLOR
S
UM
M
AXIMUM
A
CHROMATIC
N
UMBER
M
INIMUM
E
DGE
C
OLORING
M
INIMUM
F
EEDBACK
V
ERTEX
S
ET
M
INIMUM
F
EEDBACK
A
RC
S
ET
M
INIMUM
M
AXIMAL
M
ATCHING
M
AXIMUM
T
RIANGLE
P
ACKING
M
AXIMUM
H-M
ATCHING
M
INIMUM
B
OTTLENECK
P
ATH
M
ATCHING
M
INIMUM
C
LIQUE
P
ARTITION
M
INIMUM
K
-C
APACITATED
T
REE
P
ARTITION
M
AXIMUM
B
ALANCED
C
ONNECTED
P
ARTITION
M
INIMUM
C
LIQUE
C
OVER
M
INIMUM
C
OMPLETE
B
IPARTITE
S
UBGRAPH
C
OVER
M
INIMUM
V
ERTEX
D
ISJOINT
C
YCLE
C
OVER
M
INIMUM
C
UT
C
OVER
Subgraphs and Supergraphs
M
AXIMUM
C
LIQUE
M
AXIMUM
I
NDEPENDENT
S
ET
M
AXIMUM
I
NDEPENDENT
S
EQUENCE
M
AXIMUM
I
NDUCED
S
UBGRAPH WITH
P
ROPERTY
P
M
INIMUM
V
ERTEX
D
ELETION TO
O
BTAIN
S
UBGRAPH WITH
P
ROPERTY
P
M
INIMUM
E
DGE
D
ELETION TO
O
BTAIN
S
UBGRAPH WITH
P
ROPERTY
P
M
AXIMUM
I
NDUCED
C
ONNECTED
S
UBGRAPH WITH
P
ROPERTY
P
M
INIMUM
V
ERTEX
D
ELETION TO
O
BTAIN
C
ONNECTED
S
UBGRAPH WITH
P
ROPERTY
P
M
AXIMUM
D
EGREE-
B
OUNDED
C
ONNECTED
S
UBGRAPH
M
AXIMUM
P
LANAR
S
UBGRAPH
M
INIMUM
E
DGE
D
ELETION
K
-
PARTITION
M
AXIMUM
K
-C
OLORABLE
S
UBGRAPH
M
AXIMUM
S
UBFOREST
M
AXIMUM
E
DGE
S
UBGRAPH
M
INIMUM
E
DGE
K
-S
PANNER
M
AXIMUM
K
-C
OLORABLE
I
NDUCED
S
UBGRAPH
M
INIMUM
E
QUIVALENT
D
IGRAPH
M
INIMUM
I
NTERVAL
G
RAPH
C
OMPLETION
M
INIMUM
C
HORDAL
G
RAPH
C
OMPLETION
Vertex Ordering
M
INIMUM
B
ANDWIDTH
M
INIMUM
D
IRECTED
B
ANDWIDTH
M
INIMUM
L
INEAR
A
RRANGEMENT
M
INIMUM
C
UT
L
INEAR
A
RRANGEMENT
Iso- and Other Morphisms
M
AXIMUM
C
OMMON
S
UBGRAPH
M
AXIMUM
C
OMMON
I
NDUCED
S
UBGRAPH
M
AXIMUM
C
OMMON
E
MBEDDED
S
UB-TREE
M
INIMUM
G
RAPH
T
RANSFORMATION
Miscellaneous
L
ONGEST
P
ATH WITH
F
ORBIDDEN
P
AIRS
S
HORTEST
P
ATH WITH
F
ORBIDDEN
P
AIRS
M
INIMUM
P
OINT-
T
O-
P
OINT
C
ONNECTION
M
INIMUM
M
ETRIC
D
IMENSION
M
INIMUM
T
REE
W
IDTH
M
INIMUM
G
RAPH
I
NFERENCE
Viggo Kann
2000-03-20
