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 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
circular arc graphs
  MINIMUM GRAPH COLORING
circular-arc graphs
  MINIMUM DOMINATING SET | 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
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
  k-spanner
    MINIMUM EDGE 2-SPANNER
  separator
    MINIMUM B-BALANCED CUT
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 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
  circular arc
    MINIMUM GRAPH COLORING
  circular-arc
    MINIMUM DOMINATING SET | 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 EDGE 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 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 | MINIMUM CHINESE POSTMAN FOR | 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
heaviest 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
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 HORN CORE
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 Partition
    MINIMUM DOMINATING SET
  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
  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
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
  -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 k-Spanner
    MINIMUM EDGE 2-SPANNER
  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 EDGE DISJOINT CYCLE
  Edge Dominating Set
    MINIMUM EDGE DOMINATING SET
  b-Edge Separator
    MINIMUM B-BALANCED CUT
  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
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
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 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 | MINIMUM CHINESE POSTMAN FOR | 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 MINIMUM TRAVELING REPAIRMAN
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