next up previous
Next: About this document ... Up: A compendium of NP Previous: Bibliography

Index

achromatic number
MAXIMUM ACHROMATIC NUMBER
alignment
MINIMUM TREE ALIGNMENT
array partition
MINIMUM ARRAY PARTITION
balanced connected partition
MAXIMUM BALANCED CONNECTED PARTITION
bandwidth
MINIMUM BANDWIDTH | MINIMUM DIRECTED BANDWIDTH
betweenness
MAXIMUM BETWEENNESS
bin packing
MINIMUM BIN PACKING
binary constraints
MAXIMUM COMPATIBLE BINARY CONSTRAINT
bipartite graph
MINIMUM INDEPENDENT DOMINATING SET
bipartite graphs
MINIMUM COMPLETE BIPARTITE SUBGRAPH | MAXIMUM INDUCED SUBGRAPH WITH | MINIMUM VERTEX DELETION TO | MAXIMUM INDUCED CONNECTED SUBGRAPH | MINIMUM VERTEX DELETION TO | MINIMUM CROSSING NUMBER
bipartition
MINIMUM EDGE DELETION K-PARTITION
bisection of graph
MAXIMUM CUT
broadcast time
MINIMUM BROADCAST TIME
butterfly graphs
MAXIMUM DISJOINT CONNECTING PATHS
caterpillar
MINIMUM BANDWIDTH | MINIMUM GRAPH INFERENCE
channel assignment
MAXIMUM CHANNEL ASSIGNMENT
Chinese postman problem
MINIMUM CHINESE POSTMAN FOR | MINIMUM K-CHINESE POSTMAN PROBLEM
chordal graphs
MAXIMUM INDUCED SUBGRAPH WITH | MAXIMUM INDUCED CONNECTED SUBGRAPH | MINIMUM VERTEX DELETION TO | MINIMUM CHORDAL GRAPH COMPLETION | MINIMUM BROADCAST TIME
chromatic index
MINIMUM EDGE COLORING
chromatic number
MINIMUM GRAPH COLORING
circle graphs
MINIMUM INDEPENDENT DOMINATING SET
circular arc graphs
MINIMUM GRAPH COLORING
circular-arc graphs
MAXIMUM DOMATIC PARTITION | MAXIMUM INDUCED SUBGRAPH WITH
claw free graphs
MINIMUM VERTEX COVER | MAXIMUM INDEPENDENT SET
cliques
MINIMUM CLIQUE PARTITION | MINIMUM CLIQUE COVER | MAXIMUM CLIQUE
clustering problems
MINIMUM K-CLUSTERING | MINIMUM K-CLUSTERING SUM
coding theory
NEAREST CODEWORD
coloring of graph
MINIMUM GRAPH COLORING
common
point set
MAXIMUM COMMON POINT SET
sub-tree
MAXIMUM COMMON EMBEDDED SUB-TREE
subgraph
MAXIMUM COMMON SUBGRAPH | MAXIMUM COMMON INDUCED SUBGRAPH
subtree
MAXIMUM COMMON SUBTREE
connectivity
MINIMUM K-VERTEX CONNECTED SUBGRAPH | MINIMUM K-EDGE CONNECTED SUBGRAPH | MINIMUM BICONNECTIVITY AUGMENTATION
convex programming
MINIMUM BLOCK-ANGULAR CONVEX PROGRAMMING
covering problems
Covering and Partitioning to MINIMUM CUT COVER | MINIMUM SET COVER | MINIMUM EXACT COVER | MINIMUM GEOMETRIC DISK COVER | MAXIMUM D-VECTOR COVERING | MINIMUM RECTANGLE COVER
covering with disks
MINIMUM GEOMETRIC DISK COVER
cut
balanced
MINIMUM B-BALANCED CUT
directed
MAXIMUM DIRECTED CUT
flux
MINIMUM QUOTIENT CUT
hypergraph
MAXIMUM SET SPLITTING
maximum
MAXIMUM CUT
maximum k
MAXIMUM K-CUT
minimum k
MINIMUM K-CUT
multi-cut
MINIMUM MULTI-CUT
multiway
MINIMUM MULTIWAY CUT
quotient
MINIMUM QUOTIENT CUT
ratio
MINIMUM RATIO-CUT
vertex
MINIMUM VERTEX K-CUT
data storage
Data Storage to MAXIMUM D-VECTOR COVERING to MINIMUM DYNAMIC STORAGE ALLOCATION
data storage problems
MINIMUM DYNAMIC STORAGE ALLOCATION
decision tree
MINIMUM DECISION TREE
dense subgraph
MAXIMUM EDGE SUBGRAPH
digraph, equivalent
MINIMUM EQUIVALENT DIGRAPH
disjoint paths
MAXIMUM DISJOINT CONNECTING PATHS | MINIMUM MAXIMUM DISJOINT CONNECTING
dominating set
MINIMUM DOMINATING SET | MINIMUM INDEPENDENT DOMINATING SET
edge
coloring
MINIMUM EDGE COLORING
deletion
MINIMUM EDGE DELETION TO | MINIMUM EDGE DELETION K-PARTITION
dominating set
MINIMUM EDGE DOMINATING SET
installation
MINIMUM SINGLE-SINK EDGE INSTALLATION
separator
MINIMUM B-BALANCED CUT
k-spanner
MINIMUM EDGE K-SPANNER
elimination tree height
MINIMUM TREE WIDTH
embedded sub-tree
MAXIMUM COMMON EMBEDDED SUB-TREE
evolutionary trees
MINIMUM TREE ALIGNMENT | MINIMUM PHYLOGENETIC TREE DISTANCE
exact cover
MINIMUM EXACT COVER
facility dispersion
MAXIMUM K-FACILITY DISPERSION
facility location
MINIMUM FACILITY LOCATION | MAXIMUM K-FACILITY LOCATION
feedback sets in graphs
MINIMUM FEEDBACK VERTEX SET | MINIMUM FEEDBACK ARC SET
finite automata
MINIMUM CONSISTENT FINITE AUTOMATON
flow problems
Flow Problems to MINIMUM UNSPLITTABLE FLOW
folding of strings
MAXIMUM STRING FOLDING
front size
MINIMUM TREE WIDTH
geometric problems
MINIMUM K-SPANNING TREE | MINIMUM GEOMETRIC 3-DEGREE SPANNING | MAXIMUM MINIMUM METRIC K-SPANNING | MINIMUM GEOMETRIC STEINER TREE | MINIMUM GEOMETRIC TRAVELING SALESPERSON | MINIMUM LENGTH TRIANGULATION | MINIMUM GEOMETRIC DISK COVER | MINIMUM PLANAR RECORD PACKING | MINIMUM K-LINK PATH IN
graph
bipartite
MINIMUM INDEPENDENT DOMINATING SET | MINIMUM COMPLETE BIPARTITE SUBGRAPH | MAXIMUM INDUCED SUBGRAPH WITH | MINIMUM VERTEX DELETION TO | MAXIMUM INDUCED CONNECTED SUBGRAPH | MINIMUM VERTEX DELETION TO | MINIMUM CROSSING NUMBER
bisection
MAXIMUM CUT
butterfly
MAXIMUM DISJOINT CONNECTING PATHS
chordal
MAXIMUM INDUCED SUBGRAPH WITH | MAXIMUM INDUCED CONNECTED SUBGRAPH | MINIMUM VERTEX DELETION TO | MINIMUM CHORDAL GRAPH COMPLETION | MINIMUM CHORDAL GRAPH COMPLETION | MINIMUM BROADCAST TIME
circle
MINIMUM INDEPENDENT DOMINATING SET
circular arc
MINIMUM GRAPH COLORING
circular-arc
MAXIMUM DOMATIC PARTITION | MAXIMUM INDUCED SUBGRAPH WITH
claw free
MINIMUM VERTEX COVER | MAXIMUM INDEPENDENT SET
coloring
MINIMUM GRAPH COLORING
connectivity
MINIMUM K-VERTEX CONNECTED SUBGRAPH | MINIMUM K-EDGE CONNECTED SUBGRAPH | MINIMUM BICONNECTIVITY AUGMENTATION
covering with bipartite subgraphs
MINIMUM COMPLETE BIPARTITE SUBGRAPH
covering with cliques
MINIMUM CLIQUE COVER
covering with cuts
MINIMUM CUT COVER
covering with cycles
MINIMUM VERTEX DISJOINT CYCLE | MINIMUM VERTEX DISJOINT CYCLE | MINIMUM VERTEX DISJOINT CYCLE | MINIMUM VERTEX DISJOINT CYCLE
diameter
MINIMUM BOUNDED DIAMETER AUGMENTATION | MINIMUM DIAMETERS DECOMPOSITION
drawing
MINIMUM BEND NUMBER
embedding
MINIMUM CROSSING NUMBER
inference
MINIMUM GRAPH INFERENCE
interval
MAXIMUM INDUCED SUBGRAPH WITH | MAXIMUM INDUCED CONNECTED SUBGRAPH | MINIMUM INTERVAL GRAPH COMPLETION
motion planning
MINIMUM GRAPH MOTION PLANNING
outerplanar
MAXIMUM INDUCED SUBGRAPH WITH | MAXIMUM INDUCED CONNECTED SUBGRAPH | MINIMUM VERTEX DELETION TO | MAXIMUM PLANAR SUBGRAPH | MINIMUM BROADCAST TIME
partition into cliques
MINIMUM CLIQUE PARTITION
planar
MINIMUM VERTEX COVER | MINIMUM DOMINATING SET | MINIMUM EDGE DOMINATING SET | MINIMUM GRAPH COLORING | MINIMUM FEEDBACK VERTEX SET | MINIMUM FEEDBACK ARC SET | MAXIMUM TRIANGLE PACKING | MAXIMUM H-MATCHING | MAXIMUM INDEPENDENT SET | MAXIMUM INDUCED SUBGRAPH WITH | MAXIMUM INDUCED CONNECTED SUBGRAPH | MINIMUM VERTEX DELETION TO | MAXIMUM PLANAR SUBGRAPH | MINIMUM EDGE DELETION K-PARTITION | MINIMUM DIAMETER SPANNING SUBGRAPH | MINIMUM NETWORK INHIBITION ON | MINIMUM B-BALANCED CUT | MINIMUM B-VERTEX SEPARATOR | MINIMUM QUOTIENT CUT | MINIMUM METRIC TRAVELING SALESPERSON | MINIMUM GEOMETRIC TRAVELING SALESPERSON | MAXIMUM DISJOINT CONNECTING PATHS | MAXIMUM DISJOINT CONNECTING PATHS | MINIMUM K-CENTER | MINIMUM BEND NUMBER
strong connectivity
MINIMUM STRONG CONNECTIVITY AUGMENTATION
transformation
MINIMUM GRAPH TRANSFORMATION
unit disk
MINIMUM VERTEX COVER | MINIMUM DOMINATING SET | MINIMUM EDGE DOMINATING SET | MINIMUM INDEPENDENT DOMINATING SET | MINIMUM GRAPH COLORING | MAXIMUM TRIANGLE PACKING | MAXIMUM H-MATCHING | MAXIMUM INDEPENDENT SET
heavy subgraph
MAXIMUM EDGE SUBGRAPH
hitting set
MINIMUM HITTING SET
Hopfield nets
MINIMUM ATTRACTION RADIUS FOR
Horn clauses
MAXIMUM K-SATISFIABILITY
Horn core
MAXIMUM HORN CORE
Horn subformula
MAXIMUM RENAMABLE HORN SUBFORMULA
hypergraph
cut
MAXIMUM SET SPLITTING
matching
MAXIMUM SET PACKING
quotient cut
MINIMUM QUOTIENT CUT
hyperplane consistency
MAXIMUM HYPERPLANE CONSISTENCY
independent
dominating set
MINIMUM INDEPENDENT DOMINATING SET
sequence of vertices
MAXIMUM INDEPENDENT SEQUENCE
set
MAXIMUM INDEPENDENT SET
independent set
MINIMUM INDEPENDENT DOMINATING SET
induced subgraph
MAXIMUM INDUCED SUBGRAPH WITH | MAXIMUM INDUCED CONNECTED SUBGRAPH | MAXIMUM K-COLORABLE INDUCED SUBGRAPH | MAXIMUM COMMON INDUCED SUBGRAPH
integer programming
MINIMUM 0-1 PROGRAMMING | MAXIMUM BOUNDED 0-1 PROGRAMMING | MAXIMUM PACKING INTEGER PROGRAMMING | MINIMUM COVERING INTEGER PROGRAMMING
interval graphs
MAXIMUM INDUCED SUBGRAPH WITH | MAXIMUM INDUCED CONNECTED SUBGRAPH | MINIMUM INTERVAL GRAPH COMPLETION
isomorphism problems
Iso- and Other Morphisms to MINIMUM GRAPH TRANSFORMATION
knapsack problems
MAXIMUM KNAPSACK | MAXIMUM INTEGER M-DIMENSIONAL KNAPSACK | MAXIMUM INTEGER K-CHOICE KNAPSACK | MAXIMUM CLASS-CONSTRAINED KNAPSACK
lattices
NEAREST LATTICE VECTOR
linear arrangement
MINIMUM LINEAR ARRANGEMENT | MINIMUM CUT LINEAR ARRANGEMENT
linear systems of relations
MINIMUM RELEVANT VARIABLES IN | MAXIMUM SATISFYING LINEAR SUBSYSTEM | MINIMUM UNSATISFYING LINEAR SUBSYSTEM
logic problems
Propositional Logic to MAXIMUM RENAMABLE HORN SUBFORMULA
Longest
Common Subsequence
LONGEST COMMON SUBSEQUENCE
Computation
LONGEST COMPUTATION
Induced Chordal Subgraph
MAXIMUM INDUCED CONNECTED SUBGRAPH
Induced Cycle
MAXIMUM INDUCED CONNECTED SUBGRAPH
Induced Path
MAXIMUM INDUCED CONNECTED SUBGRAPH
Minimal Common Supersequence
SHORTEST COMMON SUPERSEQUENCE
Path
LONGEST PATH
Path with Forbidden Pairs
LONGEST PATH WITH FORBIDDEN
map labeling
MAXIMUM MAP LABELING
matching problems
MAXIMUM H-MATCHING | MINIMUM BOTTLENECK PATH MATCHING | MAXIMUM 3-DIMENSIONAL MATCHING | MAXIMUM SET PACKING
mathematical programming
Mathematical Programming to MINIMUM BLOCK-ANGULAR CONVEX PROGRAMMING
Maximum
2-Satisfiability
MAXIMUM K-SATISFIABILITY
3-Dimensional Matching
MAXIMUM 3-DIMENSIONAL MATCHING
3-Satisfiability
MAXIMUM K-SATISFIABILITY
d-Vector Covering
MAXIMUM D-VECTOR COVERING
Achromatic Number
MAXIMUM ACHROMATIC NUMBER
Acyclic Subgraph
MINIMUM FEEDBACK ARC SET
Agreement Subtree
MINIMUM PHYLOGENETIC TREE DISTANCE
Balanced Connected Partition
MAXIMUM BALANCED CONNECTED PARTITION
Betweenness
MAXIMUM BETWEENNESS
Bisection
MAXIMUM CUT
Bounded 0-1 Programming
MAXIMUM BOUNDED 0-1 PROGRAMMING
Capacity Representatives
MAXIMUM CAPACITY REPRESENTATIVES
Channel Assignment
MAXIMUM CHANNEL ASSIGNMENT
Class-Constrained Knapsack
MAXIMUM CLASS-CONSTRAINED KNAPSACK
Clique
MAXIMUM CLIQUE
k-Clustering Sum
MINIMUM K-CLUSTERING SUM
k-Colorable Induced Subgraph
MAXIMUM K-COLORABLE INDUCED SUBGRAPH
k-Colorable Subgraph
MAXIMUM K-COLORABLE SUBGRAPH
Common Embedded Sub-tree
MAXIMUM COMMON EMBEDDED SUB-TREE
Common Induced Subgraph
MAXIMUM COMMON INDUCED SUBGRAPH
Common Point Set
MAXIMUM COMMON POINT SET
Common Subgraph
MAXIMUM COMMON SUBGRAPH
Common Subtree
MAXIMUM COMMON SUBTREE
Compatible Binary Constraint Satisfaction
MAXIMUM COMPATIBLE BINARY CONSTRAINT
Compression
SHORTEST COMMON SUPERSTRING
Constrained Sequencing to Minimize Tardy Task Weight
MAXIMUM CONSTRAINED SEQUENCING TO
k-Constraint Satisfaction
MAXIMUM K-CONSTRAINT SATISFACTION
k-Cut
MAXIMUM CUT | MAXIMUM K-CUT
Degree-Bounded Connected Subgraph
MAXIMUM DEGREE-BOUNDED CONNECTED SUBGRAPH
Directed Cut
MAXIMUM DIRECTED CUT
Disjoint Connecting Paths
MAXIMUM DISJOINT CONNECTING PATHS
Distinguished Ones
MAXIMUM DISTINGUISHED ONES
Domatic Number
MAXIMUM DOMATIC PARTITION
Domatic Partition
MAXIMUM DOMATIC PARTITION
Edge Subgraph
MAXIMUM EDGE SUBGRAPH
k-Facility Dispersion
MAXIMUM K-FACILITY DISPERSION
k-Facility Location
MAXIMUM K-FACILITY LOCATION
Frequency Allocation
MAXIMUM FREQUENCY ALLOCATION
Geometric
Traveling Salesperson
MINIMUM GEOMETRIC TRAVELING SALESPERSON
Geometric Square Packing
MINIMUM GEOMETRIC DISK COVER
Graph Transformation
MINIMUM GRAPH TRANSFORMATION
H-Matching
MAXIMUM H-MATCHING
Horn Core
MAXIMUM HORN CORE
Hypergraph Cut
MAXIMUM SET SPLITTING
Hypergraph Matching
MAXIMUM SET PACKING
Hyperplane Consistency
MAXIMUM HYPERPLANE CONSISTENCY
Independent Sequence
MAXIMUM INDEPENDENT SEQUENCE
Independent Set
MAXIMUM INDEPENDENT SET
Independent Set of k-gons
MAXIMUM INDEPENDENT SET
Induced Connected Subgraph with Property P
MAXIMUM INDUCED CONNECTED SUBGRAPH
Induced Subgraph with Property P
MAXIMUM INDUCED SUBGRAPH WITH
Integer k-Choice Knapsack
MAXIMUM INTEGER K-CHOICE KNAPSACK
Integer m-Dimensional Knapsack
MAXIMUM INTEGER M-DIMENSIONAL KNAPSACK
Integral k-Multicommodity Flow on Trees
MAXIMUM INTEGRAL K-MULTICOMMODITY FLOW
Knapsack
MAXIMUM KNAPSACK
Leaf Spanning Tree
MAXIMUM LEAF SPANNING TREE
Map Labeling
MAXIMUM MAP LABELING
Matching of Consistent k-Cliques
MAXIMUM H-MATCHING
Metric
Traveling Salesperson
MINIMUM METRIC TRAVELING SALESPERSON
Minimum
Metric k-Spanning Tree
MAXIMUM MINIMUM METRIC K-SPANNING
Metric k-TSP
MAXIMUM MINIMUM METRIC K-SPANNING
Spanning Tree Deleting k Edges
MAXIMUM MINIMUM SPANNING TREE
k-Steiner Tree
MAXIMUM MINIMUM METRIC K-SPANNING
Not-All-Equal 3-Satisfiability
MAXIMUM NOT-ALL-EQUAL 3-SATISFIABILITY
Number of Satisfiable Formulas
MAXIMUM NUMBER OF SATISFIABLE
Ones
MAXIMUM DISTINGUISHED ONES
Outerplanar Subgraph
MAXIMUM PLANAR SUBGRAPH
Packing Integer Programming
MAXIMUM PACKING INTEGER PROGRAMMING
Planar Subgraph
MAXIMUM PLANAR SUBGRAPH
Priority Flow
MAXIMUM PRIORITY FLOW
Quadratic Programming
MAXIMUM QUADRATIC PROGRAMMING
Rectangle Packing
MINIMUM RECTANGLE TILING
Remote Minimum Spanning Tree
MAXIMUM MINIMUM METRIC K-SPANNING
Renamable Horn Subformula
MAXIMUM RENAMABLE HORN SUBFORMULA
k-Satisfiability
MAXIMUM SATISFIABILITY | MAXIMUM K-SATISFIABILITY
Satisfiability of Horn Clauses
MAXIMUM K-SATISFIABILITY
Satisfiability of Quadratic Equations over GF[q]
MAXIMUM SATISFIABILITY OF QUADRATIC
Satisfying Linear Subsystem
MAXIMUM SATISFYING LINEAR SUBSYSTEM
Scatter TSP
MINIMUM METRIC BOTTLENECK WANDERING
k-Section
MAXIMUM K-CUT
k-Set Packing
MAXIMUM SET PACKING | MAXIMUM SET PACKING
Set Splitting
MAXIMUM SET SPLITTING
String Folding
MAXIMUM STRING FOLDING
Subforest
MAXIMUM SUBFOREST
Subset Sum
MAXIMUM KNAPSACK
Traveling Salesperson
MINIMUM TRAVELING SALESPERSON
Triangle Packing
MAXIMUM TRIANGLE PACKING
Weighted Satisfiability with Bound
MAXIMUM WEIGHTED SATISFIABILITY WITH
Maximum quadratic assignment
MAXIMUM QUADRATIC ASSIGNMENT
metric basis
MINIMUM METRIC DIMENSION
Minimum
0-1 Programming
MINIMUM 0-1 PROGRAMMING
3-Dedicated Processor Scheduling
MINIMUM 3-DEDICATED PROCESSOR SCHEDULING
3-Dimensional Assignment
MINIMUM 3-DIMENSIONAL ASSIGNMENT
3DNF Satisfiability
MINIMUM 3DNF SATISFIABILITY
Absolute k-Center
MINIMUM K-CENTER
$\alpha$-All-Neighbor k-Center
MINIMUM K-CENTER
Array Partition
MINIMUM ARRAY PARTITION
Assymmetric k-Center
MINIMUM K-CENTER
Attraction Radius for Binary Hopfield Net
MINIMUM ATTRACTION RADIUS FOR
b-Balanced Cut
MINIMUM B-BALANCED CUT
Bandwidth
MINIMUM BANDWIDTH
Bend Number
MINIMUM BEND NUMBER
Biconnectivity Augmentation
MINIMUM BICONNECTIVITY AUGMENTATION
Bin Packing
MINIMUM BIN PACKING
Bipartition
MINIMUM EDGE DELETION K-PARTITION
Bisection
MAXIMUM CUT
Block-angular Convex Programming
MINIMUM BLOCK-ANGULAR CONVEX PROGRAMMING
Bottleneck Path Matching
MINIMUM BOTTLENECK PATH MATCHING
Bounded Degree Spanning Tree
MINIMUM GEOMETRIC 3-DEGREE SPANNING
Bounded Diameter Augmentation
MINIMUM BOUNDED DIAMETER AUGMENTATION
Broadcast Time
MINIMUM BROADCAST TIME
Capacitated k-Center
MINIMUM K-CENTER
k-Capacitated Tree Partition
MINIMUM K-CAPACITATED TREE PARTITION
k-Center
MINIMUM K-CENTER
Chinese Postman for Mixed Graphs
MINIMUM CHINESE POSTMAN FOR
Chinese Postman Problem
MINIMUM K-CHINESE POSTMAN PROBLEM
Chordal Graph Completion
MINIMUM CHORDAL GRAPH COMPLETION
Chromatic Index
MINIMUM EDGE COLORING
Chromatic Number
MINIMUM GRAPH COLORING
Clique Cover
MINIMUM CLIQUE COVER
Clique Partition
MINIMUM CLIQUE PARTITION
k-Clustering
MINIMUM K-CLUSTERING
k-Clustering Sum
MINIMUM EDGE DELETION K-PARTITION | MINIMUM K-CLUSTERING SUM
Color Sum
MINIMUM COLOR SUM
Coloring with Defect d
MINIMUM GRAPH COLORING
Communication Cost Spanning Tree
MINIMUM COMMUNICATION COST SPANNING
Complete Bipartite Subgraph Cover
MINIMUM COMPLETE BIPARTITE SUBGRAPH
Consistent Finite Automaton
MINIMUM CONSISTENT FINITE AUTOMATON
Constrained Partition
MAXIMUM CONSTRAINED PARTITION
Covering Integer Programming
MINIMUM COVERING INTEGER PROGRAMMING
Crossing Number
MINIMUM CROSSING NUMBER
k-Cut
MINIMUM K-CUT
Cut Cover
MINIMUM CUT COVER
Cut Linear Arrangement
MINIMUM CUT LINEAR ARRANGEMENT
Decision Tree
MINIMUM DECISION TREE
Degree Spanning Tree
MINIMUM DEGREE SPANNING TREE
Degree Steiner Tree
MINIMUM DEGREE SPANNING TREE
Diameter Spanning Subgraph
MINIMUM DIAMETER SPANNING SUBGRAPH
Diameters Decomposition
MINIMUM DIAMETERS DECOMPOSITION
Directed Bandwidth
MINIMUM DIRECTED BANDWIDTH
Distinguished Ones
MINIMUM DISTINGUISHED ONES
Dominating Set
MINIMUM DOMINATING SET
Dynamic Storage Allocation
MINIMUM DYNAMIC STORAGE ALLOCATION
Edge Coloring
MINIMUM EDGE COLORING
k-Edge Connected Subgraph
MINIMUM K-EDGE CONNECTED SUBGRAPH
Edge Deletion
Bipartition
MINIMUM EDGE DELETION K-PARTITION
k-Partition
MINIMUM EDGE DELETION K-PARTITION | MINIMUM K-CLUSTERING SUM
to Obtain Subgraph with Property P
MINIMUM EDGE DELETION TO
Edge Disjoint Cycle Cover
MINIMUM VERTEX DISJOINT CYCLE
Edge Dominating Set
MINIMUM EDGE DOMINATING SET
b-Edge Separator
MINIMUM B-BALANCED CUT
Edge k-Spanner
MINIMUM EDGE K-SPANNER
Elimination Tree Height
MINIMUM TREE WIDTH
Equivalence Deletion
MINIMUM EQUIVALENCE DELETION
Equivalent Digraph
MINIMUM EQUIVALENT DIGRAPH
Evolutionary Tree
MINIMUM TREE ALIGNMENT
Exact Cover
MINIMUM EXACT COVER
Facility Location
MINIMUM FACILITY LOCATION
Feedback Arc Set
MINIMUM FEEDBACK ARC SET
Feedback Vertex Set
MINIMUM FEEDBACK VERTEX SET
File Transfer Scheduling
MINIMUM FILE TRANSFER SCHEDULING
Flow-Shop Scheduling
MINIMUM FLOW-SHOP SCHEDULING
Flux Cut
MINIMUM QUOTIENT CUT
Fractional Chromatic Number
MINIMUM GRAPH COLORING
Front Size
MINIMUM TREE WIDTH
General Routing
MINIMUM GENERAL ROUTING
Generalized 0-1 Assignment
MINIMUM GENERALIZED 0-1 ASSIGNMENT
Generalized Steiner Network
MINIMUM GENERALIZED STEINER NETWORK | MINIMUM SINGLE-SINK EDGE INSTALLATION
Generalized Tree Alignment
MINIMUM TREE ALIGNMENT
Geometric
3-Degree Spanning Tree
MINIMUM GEOMETRIC 3-DEGREE SPANNING
Angular Traveling Salesperson
MINIMUM GEOMETRIC TRAVELING SALESPERSON
Capacitated k-Center
MINIMUM K-CENTER
k-Clustering
MINIMUM K-CLUSTERING
Disk Cover
MINIMUM GEOMETRIC DISK COVER
k-Spanning Tree
MINIMUM K-SPANNING TREE
Steiner Tree
MINIMUM GEOMETRIC STEINER TREE
Traveling Salesperson
MINIMUM GEOMETRIC TRAVELING SALESPERSON
Graph Coloring
MINIMUM GRAPH COLORING
Graph Inference
MINIMUM GRAPH INFERENCE
Graph Motion Planning
MINIMUM GRAPH MOTION PLANNING
Height Two Dimensional Packing
MINIMUM HEIGHT TWO DIMENSIONAL
Hitting Set
MINIMUM HITTING SET
Independent Dominating Set
MINIMUM INDEPENDENT DOMINATING SET
Interval Graph Completion
MINIMUM INTERVAL GRAPH COMPLETION
Job Shop Scheduling
MINIMUM JOB SHOP SCHEDULING
Latency Problem
MINIMUM TRAVELING REPAIRMAN
Length Equivalent Frege Proof
MINIMUM LENGTH EQUIVALENT FREGE
Length Triangulation
MINIMUM LENGTH TRIANGULATION
Linear Arrangement
MINIMUM LINEAR ARRANGEMENT
k-Link Path in a Polygon
MINIMUM K-LINK PATH IN
Local Register Allocation
MINIMUM LOCAL REGISTER ALLOCATION
Locally Testable Automaton Order
MINIMUM LOCALLY TESTABLE AUTOMATON
Maximal Independent Set
MINIMUM INDEPENDENT DOMINATING SET
Maximal Matching
MINIMUM MAXIMAL MATCHING
Maximum Disjoint Connecting Paths
MINIMUM MAXIMUM DISJOINT CONNECTING
k-Median
MINIMUM K-MEDIAN
Metric
Bottleneck Wandering Salesperson Problem
MINIMUM METRIC BOTTLENECK WANDERING
Traveling k-Salesperson Problem
MINIMUM METRIC TRAVELING K-SALESPERSON
Traveling Salesperson
MINIMUM METRIC TRAVELING SALESPERSON
Traveling Salesperson Path
MINIMUM METRIC TRAVELING SALESPERSON
Metric Dimension
MINIMUM METRIC DIMENSION
Multi-Cut
MINIMUM MULTI-CUT
Multiprocessor Scheduling
MINIMUM MULTIPROCESSOR SCHEDULING
Multiprocessor Scheduling with Speed Factors
MINIMUM MULTIPROCESSOR SCHEDULING WITH
Multiway Cut
MINIMUM MULTIWAY CUT
k-Multiway Separator
MINIMUM B-BALANCED CUT
Net Expansion
MINIMUM QUOTIENT CUT
Network Inhibition on Planar Graphs
MINIMUM NETWORK INHIBITION ON
Nonplanar Edge Deletion
MAXIMUM PLANAR SUBGRAPH
Number of Satisfiable Formulas
MINIMUM NUMBER OF SATISFIABLE
Numerical Taxonomy
MINIMUM NUMERICAL TAXONOMY
Ones
MINIMUM DISTINGUISHED ONES
Open-Shop Scheduling
MINIMUM OPEN-SHOP SCHEDULING
Parallel Processor Total Flow Time
MINIMUM PARALLEL PROCESSOR TOTAL
k-Partition
MINIMUM EDGE DELETION K-PARTITION
Partition of Rectangle with Interior Points
MINIMUM PARTITION OF RECTANGLE
Path Coloring
MAXIMUM DISJOINT CONNECTING PATHS
Path Width
MINIMUM TREE WIDTH
Permutation Group Base
MINIMUM PERMUTATION GROUP BASE
phylogenetic tree distance
MINIMUM PHYLOGENETIC TREE DISTANCE
Planar Record Packing
MINIMUM PLANAR RECORD PACKING
Point-To-Point Connection
MINIMUM POINT-TO-POINT CONNECTION
Precedence Constrained Scheduling
MINIMUM PRECEDENCE CONSTRAINED SCHEDULING
Precedence Constrained Sequencing with Delays
MINIMUM PRECEDENCE CONSTRAINED SEQUENCING
Preemptive Scheduling with Set-Up Times
MINIMUM PREEMPTIVE SCHEDULING WITH
Quadratic 0-1 Assignment
MINIMUM QUADRATIC 0-1 ASSIGNMENT
Quotient Cut
MINIMUM QUOTIENT CUT
Ratio-Cut
MINIMUM RATIO-CUT
Rectangle Cover
MINIMUM RECTANGLE COVER
Rectangle Tiling
MINIMUM RECTANGLE TILING
Rectilinear Global Routing
MINIMUM RECTILINEAR GLOBAL ROUTING
Red-Blue Separation
MINIMUM RED-BLUE SEPARATION
Register Sufficiency
MINIMUM REGISTER SUFFICIENCY
Relevant Variables in Linear System
MINIMUM RELEVANT VARIABLES IN
Resource Constrained Scheduling
MINIMUM RESOURCE CONSTRAINED SCHEDULING
Ring Loading
MINIMUM RING LOADING
Routing Cost Spanning Tree
MINIMUM COMMUNICATION COST SPANNING
Routing Tree Congestion
MINIMUM ROUTING TREE CONGESTION
Rural Postman Problem
MINIMUM GENERAL ROUTING
k-Satisfiability
MAXIMUM SATISFIABILITY | MINIMUM K-SATISFIABILITY
Satisfiability of Horn Clauses
MINIMUM K-SATISFIABILITY
Schedule Length
MINIMUM SCHEDULE LENGTH
Separating Subdivision
MINIMUM SEPARATING SUBDIVISION
Sequence Alignment
MINIMUM TREE ALIGNMENT
Sequencing with Release Times
MINIMUM SEQUENCING WITH RELEASE
Set Cover
MINIMUM SET COVER
Single-Sink Edge Installation
MINIMUM SINGLE-SINK EDGE INSTALLATION
Size Ultrametric Tree
MINIMUM SIZE ULTRAMETRIC TREE
Sorting by Reversals
MINIMUM SORTING BY REVERSALS
k-Spanning Tree
MINIMUM K-SPANNING TREE
k-Stacker Crane Problem
MINIMUM STACKER CRANE PROBLEM | MINIMUM K-STACKER CRANE PROBLEM
k-Steiner Tree
MINIMUM STEINER TREE | MINIMUM STEINER TREE | MINIMUM SINGLE-SINK EDGE INSTALLATION
Steiner Trees with Obstacles
MINIMUM GEOMETRIC STEINER TREE
Storage-Time Sequencing
MINIMUM STORAGE-TIME SEQUENCING
Strip Packing
MINIMUM HEIGHT TWO DIMENSIONAL
Strong Connectivity Augmentation
MINIMUM STRONG CONNECTIVITY AUGMENTATION
Sum of Squares
MINIMUM SUM OF SQUARES
k-Supplier
MINIMUM K-SUPPLIER
Survivable Network
MINIMUM GENERALIZED STEINER NETWORK
k-Switching Network
MINIMUM K-SWITCHING NETWORK
Test Collection
MINIMUM TEST COLLECTION
Time-Cost Tradeoff
MINIMUM TIME-COST TRADEOFF
Travel Robot Localization
MINIMUM TRAVEL ROBOT LOCALIZATION
Traveling Repairman
MINIMUM TRAVELING REPAIRMAN
Traveling Salesperson
MINIMUM TRAVELING SALESPERSON
Tree Alignment
MINIMUM TREE ALIGNMENT
Tree Compact Packing
MINIMUM TREE COMPACT PACKING
Tree Width
MINIMUM TREE WIDTH
Two-Processor Flow-Shop Scheduling with Batch Set-Up Times
MINIMUM TWO-PROCESSOR FLOW-SHOP SCHEDULING
Unsatisfying Linear Subsystem
MINIMUM UNSATISFYING LINEAR SUBSYSTEM
Unsplittable Flow
MINIMUM UNSPLITTABLE FLOW
Upgrading Spanning Tree
MINIMUM UPGRADING SPANNING TREE
Vehicle Scheduling on Tree
MINIMUM VEHICLE SCHEDULING ON
k-Vertex Connected Subgraph
MINIMUM K-VERTEX CONNECTED SUBGRAPH
Vertex Cover
MINIMUM VERTEX COVER
Vertex Deletion to Obtain Connected Subgraph with Property @ P
MINIMUM VERTEX DELETION TO
Vertex Deletion to Obtain Subgraph with Property P
MINIMUM VERTEX DELETION TO
Vertex Disjoint Cycle Cover
MINIMUM VERTEX DISJOINT CYCLE
Vertex k-Cut
MINIMUM VERTEX K-CUT
b-Vertex Separator
MINIMUM B-VERTEX SEPARATOR
Weighted Completion Time Scheduling
MINIMUM WEIGHTED COMPLETION TIME
Weighted Satisfiability
MINIMUM DISTINGUISHED ONES
multicommodity flow
MAXIMUM INTEGRAL K-MULTICOMMODITY FLOW
multiprocessor scheduling problems
Multiprocessor Scheduling to MINIMUM 3-DEDICATED PROCESSOR SCHEDULING
Nearest
Codeword
NEAREST CODEWORD
Lattice Vector
NEAREST LATTICE VECTOR
Nearest String
NEAREST STRING
network inhibition
MINIMUM NETWORK INHIBITION ON
numerical taxonomy
MINIMUM NUMERICAL TAXONOMY
outerplanar graphs
MAXIMUM INDUCED SUBGRAPH WITH | MAXIMUM INDUCED CONNECTED SUBGRAPH | MINIMUM VERTEX DELETION TO | MAXIMUM PLANAR SUBGRAPH | MINIMUM BROADCAST TIME
packing problems
MAXIMUM TRIANGLE PACKING | MAXIMUM SET PACKING | MINIMUM GEOMETRIC DISK COVER | MINIMUM BIN PACKING | MINIMUM HEIGHT TWO DIMENSIONAL | MINIMUM PLANAR RECORD PACKING
partition
domatic
MAXIMUM DOMATIC PARTITION
partitioning problems
Covering and Partitioning | MINIMUM K-CAPACITATED TREE PARTITION | MINIMUM K-CAPACITATED TREE PARTITION to MINIMUM CUT COVER | MINIMUM QUOTIENT CUT | MINIMUM ARRAY PARTITION
path
longest
MAXIMUM INDUCED CONNECTED SUBGRAPH | LONGEST PATH WITH FORBIDDEN | LONGEST PATH
matching
MINIMUM BOTTLENECK PATH MATCHING
shortest
SHORTEST PATH WITH FORBIDDEN | SHORTEST WEIGHT-CONSTRAINED PATH
width
MINIMUM TREE WIDTH
permutations
MINIMUM PERMUTATION GROUP BASE | MINIMUM SORTING BY REVERSALS
phylogenetic trees
MINIMUM TREE ALIGNMENT | MINIMUM PHYLOGENETIC TREE DISTANCE
planar graphs
MINIMUM VERTEX COVER | MINIMUM DOMINATING SET | MINIMUM EDGE DOMINATING SET | MINIMUM GRAPH COLORING | MINIMUM FEEDBACK VERTEX SET | MINIMUM FEEDBACK ARC SET | MAXIMUM TRIANGLE PACKING | MAXIMUM H-MATCHING | MAXIMUM INDEPENDENT SET | MAXIMUM INDUCED SUBGRAPH WITH | MAXIMUM INDUCED CONNECTED SUBGRAPH | MINIMUM VERTEX DELETION TO | MAXIMUM PLANAR SUBGRAPH | MINIMUM EDGE DELETION K-PARTITION | MINIMUM DIAMETER SPANNING SUBGRAPH | MINIMUM NETWORK INHIBITION ON | MINIMUM B-BALANCED CUT | MINIMUM B-VERTEX SEPARATOR | MINIMUM QUOTIENT CUT | MINIMUM METRIC TRAVELING SALESPERSON | MINIMUM GEOMETRIC TRAVELING SALESPERSON | MAXIMUM DISJOINT CONNECTING PATHS | MAXIMUM DISJOINT CONNECTING PATHS | MINIMUM K-CENTER | MINIMUM BEND NUMBER
polygon, link path
MINIMUM K-LINK PATH IN
polygon, subdivision
MINIMUM SEPARATING SUBDIVISION
preemptive scheduling
MINIMUM PREEMPTIVE SCHEDULING WITH
printed circuit board assembly
MINIMUM METRIC TRAVELING SALESPERSON
proof
of tautology
MINIMUM LENGTH EQUIVALENT FREGE
quadratic equations
MAXIMUM SATISFIABILITY OF QUADRATIC
quadratic programming
MAXIMUM QUADRATIC PROGRAMMING
rectangle cover
MINIMUM RECTANGLE COVER
rectangle packing
MINIMUM RECTANGLE TILING
rectangle partition
MINIMUM PARTITION OF RECTANGLE
rectangle tiling
MINIMUM RECTANGLE TILING
register allocation
MINIMUM LOCAL REGISTER ALLOCATION
register sufficiency
MINIMUM REGISTER SUFFICIENCY
ring loading
MINIMUM RING LOADING
robot motion planning
MINIMUM GRAPH MOTION PLANNING | MINIMUM TRAVEL ROBOT LOCALIZATION | SHORTEST PATH MOTION IN
routing
general
MINIMUM GENERAL ROUTING
rectilinear
MINIMUM RECTILINEAR GLOBAL ROUTING
trees
MINIMUM ROUTING TREE CONGESTION
routing problems
Routing Problems to MAXIMUM QUADRATIC ASSIGNMENT
rural postman problem
MINIMUM GENERAL ROUTING
satisfiability
equivalence deletion
MINIMUM EQUIVALENCE DELETION
maximizing ones
MAXIMUM DISTINGUISHED ONES
minimizing ones
MINIMUM DISTINGUISHED ONES
not-all-equal
MAXIMUM NOT-ALL-EQUAL 3-SATISFIABILITY
of CNF clauses
MAXIMUM SATISFIABILITY | MAXIMUM K-SATISFIABILITY | MINIMUM K-SATISFIABILITY
of CNF formulas
MAXIMUM NUMBER OF SATISFIABLE | MINIMUM NUMBER OF SATISFIABLE
of DNF clauses
MINIMUM 3DNF SATISFIABILITY | MAXIMUM K-CONSTRAINT SATISFACTION
weighted
MAXIMUM WEIGHTED SATISFIABILITY WITH
scheduling problems
Multiprocessor Scheduling to MINIMUM VEHICLE SCHEDULING ON
separation of point sets
MINIMUM RED-BLUE SEPARATION
sequence alignment
MINIMUM TREE ALIGNMENT
sequencing problems
Sequencing and Scheduling to MINIMUM TIME-COST TRADEOFF
set
cover
MINIMUM SET COVER | MINIMUM EXACT COVER
dominating
MINIMUM DOMINATING SET | MINIMUM EDGE DOMINATING SET
hitting
MINIMUM HITTING SET
independent
MAXIMUM INDEPENDENT SET
independent dominating
MINIMUM INDEPENDENT DOMINATING SET
packing
MAXIMUM SET PACKING
partition
MAXIMUM CONSTRAINED PARTITION | MINIMUM SUM OF SQUARES
splitting
MAXIMUM SET SPLITTING
set problems
Sets and Partitions to MINIMUM RECTANGLE TILING
shop scheduling problems
Shop Scheduling to MINIMUM JOB SHOP SCHEDULING
Shortest
Common Supersequence
SHORTEST COMMON SUPERSEQUENCE
Common Superstring
SHORTEST COMMON SUPERSTRING
Computation
SHORTEST COMPUTATION
Maximal Common Non-Supersequence
SHORTEST COMMON SUPERSEQUENCE
Maximal Common Subsequence
LONGEST COMMON SUBSEQUENCE
Path Motion in 3 Dimensions
SHORTEST PATH MOTION IN
Path with Forbidden Pairs
SHORTEST PATH WITH FORBIDDEN
Watchman Route
MINIMUM TRAVEL ROBOT LOCALIZATION
Weight-Constrained Path
SHORTEST WEIGHT-CONSTRAINED PATH
sorting by reversals
MINIMUM SORTING BY REVERSALS
spanning
subgraphs
MINIMUM DIAMETER SPANNING SUBGRAPH | MINIMUM K-VERTEX CONNECTED SUBGRAPH | MINIMUM K-EDGE CONNECTED SUBGRAPH
trees
MINIMUM K-SPANNING TREE | MINIMUM DEGREE SPANNING TREE | MINIMUM GEOMETRIC 3-DEGREE SPANNING | MAXIMUM LEAF SPANNING TREE | MAXIMUM MINIMUM METRIC K-SPANNING | MAXIMUM MINIMUM METRIC K-SPANNING | MAXIMUM MINIMUM SPANNING TREE
sparsest cut
MINIMUM RATIO-CUT
stacker crane problem
MINIMUM STACKER CRANE PROBLEM | MINIMUM K-STACKER CRANE PROBLEM
Steiner
networks
MINIMUM GENERALIZED STEINER NETWORK
trees
MINIMUM DEGREE SPANNING TREE | MAXIMUM MINIMUM METRIC K-SPANNING | MINIMUM STEINER TREE | MINIMUM GEOMETRIC STEINER TREE
storage-time sequencing
MINIMUM STORAGE-TIME SEQUENCING
string folding
MAXIMUM STRING FOLDING
strip packing
MINIMUM HEIGHT TWO DIMENSIONAL
strong connectivity
MINIMUM STRONG CONNECTIVITY AUGMENTATION
sub-tree
MAXIMUM COMMON EMBEDDED SUB-TREE
subgraph
k-colorable
MAXIMUM K-COLORABLE SUBGRAPH | MAXIMUM K-COLORABLE INDUCED SUBGRAPH
common
MAXIMUM COMMON SUBGRAPH | MAXIMUM COMMON INDUCED SUBGRAPH
degree-bounded connected
MAXIMUM DEGREE-BOUNDED CONNECTED SUBGRAPH
heaviest
MAXIMUM EDGE SUBGRAPH
induced
MAXIMUM INDUCED CONNECTED SUBGRAPH
subgraph problems
Subgraphs and Supergraphs to MINIMUM EQUIVALENT DIGRAPH
subsequences
LONGEST COMMON SUBSEQUENCE
supergraph problems
MINIMUM EQUIVALENT DIGRAPH to MINIMUM CHORDAL GRAPH COMPLETION
supersequences
SHORTEST COMMON SUPERSEQUENCE
superstrings
SHORTEST COMMON SUPERSTRING
survivable networks
MINIMUM GENERALIZED STEINER NETWORK
switching network
MINIMUM K-SWITCHING NETWORK
test collection
MINIMUM TEST COLLECTION
traveling repairman
MINIMUM TRAVELING REPAIRMAN
traveling salesperson problems
MAXIMUM MINIMUM METRIC K-SPANNING | MINIMUM TRAVELING SALESPERSON | MINIMUM METRIC TRAVELING SALESPERSON | MINIMUM METRIC TRAVELING K-SALESPERSON
tree
alignment
MINIMUM TREE ALIGNMENT
width
MINIMUM TREE WIDTH
triangle packing
MAXIMUM TRIANGLE PACKING
triangulation
MINIMUM LENGTH TRIANGULATION
Turing machines
LONGEST COMPUTATION | SHORTEST COMPUTATION
ultrametric trees
MINIMUM SIZE ULTRAMETRIC TREE
unit disk graphs
MINIMUM VERTEX COVER | MINIMUM DOMINATING SET | MINIMUM EDGE DOMINATING SET | MINIMUM INDEPENDENT DOMINATING SET | MINIMUM GRAPH COLORING | MAXIMUM TRIANGLE PACKING | MAXIMUM H-MATCHING | MAXIMUM INDEPENDENT SET
unsplittable flow
MINIMUM UNSPLITTABLE FLOW
vertex
cover
MINIMUM VERTEX COVER
deletion
MINIMUM VERTEX DELETION TO | MINIMUM VERTEX DELETION TO
separator
MINIMUM B-VERTEX SEPARATOR
wandering salesperson problem
MINIMUM METRIC BOTTLENECK WANDERING


Viggo Kann
2000-03-20