Index

MAXIMUM BALANCED CONNECTED PARTITION

array partition

MINIMUM ARRAY PARTITION

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 EDGE DELETION K-PARTITION

bipartite graphs

bipartition

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

circle graphs

circular arc graphs

MAXIMUM DOMATIC PARTITION | MAXIMUM INDUCED SUBGRAPH WITH

circular-arc graphs

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 K-VERTEX CONNECTED SUBGRAPH | MINIMUM K-EDGE CONNECTED SUBGRAPH | MINIMUM BICONNECTIVITY AUGMENTATION

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

convex programming

MINIMUM BLOCK-ANGULAR CONVEX PROGRAMMING

covering problems

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

MAXIMUM COMMON EMBEDDED SUB-TREE

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 ATTRACTION RADIUS FOR

geometric problems

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

Horn clauses

MAXIMUM RENAMABLE HORN SUBFORMULA

Horn core

MAXIMUM HORN CORE

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

MAXIMUM INDUCED SUBGRAPH WITH | MAXIMUM INDUCED CONNECTED SUBGRAPH | MAXIMUM K-COLORABLE INDUCED SUBGRAPH | MAXIMUM COMMON INDUCED SUBGRAPH

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 3-DIMENSIONAL MATCHING

3-Dimensional Matching

3-Satisfiability

MAXIMUM D-VECTOR COVERING

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

MAXIMUM MINIMUM METRIC K-SPANNING

Remote Minimum Spanning Tree

Renamable Horn Subformula

MAXIMUM RENAMABLE HORN SUBFORMULA

k-Satisfiability

MAXIMUM SATISFIABILITY | MAXIMUM K-SATISFIABILITY

Satisfiability of Horn Clauses

MAXIMUM SATISFIABILITY OF QUADRATIC

Satisfiability of Quadratic Equations over GF[q]

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

$\alpha$ -All-Neighbor k-Center

Array Partition

MINIMUM ARRAY PARTITION

Assymmetric k-Center

MINIMUM ATTRACTION RADIUS FOR

Attraction Radius for Binary Hopfield Net

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-CAPACITATED TREE PARTITION

k-Capacitated Tree Partition

k-Center

MINIMUM CHINESE POSTMAN FOR

Chinese Postman for Mixed Graphs

Chinese Postman Problem

MINIMUM K-CHINESE POSTMAN PROBLEM

Chordal Graph Completion

MINIMUM CHORDAL GRAPH COMPLETION

Chromatic Index

MINIMUM EDGE COLORING

Chromatic Number

MINIMUM EDGE DELETION K-PARTITION | MINIMUM K-CLUSTERING SUM

Clique Cover

MINIMUM CLIQUE COVER

Clique Partition

MINIMUM CLIQUE PARTITION

k-Clustering

MINIMUM K-CLUSTERING

k-Clustering Sum

Color Sum

MINIMUM COLOR SUM

Coloring with Defect d

MINIMUM COMMUNICATION COST SPANNING

Communication Cost Spanning Tree

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 EQUIVALENCE DELETION

Equivalence Deletion

Equivalent Digraph

MINIMUM EQUIVALENT DIGRAPH

Evolutionary Tree

MINIMUM FACILITY LOCATION

Exact Cover

MINIMUM EXACT COVER

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

Front Size

MINIMUM GENERALIZED 0-1 ASSIGNMENT

General Routing

MINIMUM GENERAL ROUTING

Generalized 0-1 Assignment

Generalized Steiner Network

MINIMUM GENERALIZED STEINER NETWORK | MINIMUM SINGLE-SINK EDGE INSTALLATION

Generalized 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 MOTION PLANNING

Graph Inference

MINIMUM GRAPH INFERENCE

Graph Motion Planning

Height Two Dimensional Packing

MINIMUM HEIGHT TWO DIMENSIONAL

Hitting Set

MINIMUM HITTING SET

Independent Dominating Set

MINIMUM INTERVAL GRAPH COMPLETION

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 MAXIMUM DISJOINT CONNECTING

Maximal Matching

MINIMUM MAXIMAL MATCHING

Maximum Disjoint Connecting Paths

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 PERMUTATION GROUP BASE

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 RECTILINEAR GLOBAL ROUTING

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 SEQUENCING WITH RELEASE

Sequencing with Release Times

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 COMPACT PACKING

Tree Compact Packing

Tree Width

MINIMUM TWO-PROCESSOR FLOW-SHOP SCHEDULING

Two-Processor Flow-Shop Scheduling with Batch Set-Up Times

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

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

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 PARTITION OF RECTANGLE

rectangle partition

rectangle tiling

MINIMUM LOCAL REGISTER ALLOCATION

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