Index

claw free graphs

GT1 M INIMUM | GT21 M AXIMUM

cliques

GT13 M INIMUM | GT15 M INIMUM | GT20 M AXIMUM

clustering problems

ND49 M INIMUM | ND50 M INIMUM

coding theory

MS2 N EAREST

coloring of graph

common

point set: SR8 M AXIMUM
sub-tree: GT44 M AXIMUM
subgraph: GT42 M AXIMUM | GT43 M AXIMUM
subtree: SR7 M AXIMUM

connectivity

ND24 M INIMUM | ND25 M INIMUM | ND26 M INIMUM

convex programming

MP17 M INIMUM

covering problems

Covering and Partitioning to GT19 M INIMUM | SP4 M INIMUM | SP5 M INIMUM | SP8 M INIMUM | SR9 M INIMUM

covering with disks

SP8 M INIMUM

cut

balanced: ND21 M INIMUM
directed: ND13 M AXIMUM
flux: ND23 M INIMUM
hypergraph: SP3 M AXIMUM
maximum: ND11 M AXIMUM
maximum k: ND14 M AXIMUM
minimum k: ND16 M INIMUM
multi-cut: ND19 M INIMUM
multiway: ND18 M INIMUM
quotient: ND23 M INIMUM
ratio: ND20 M INIMUM
vertex: ND17 M INIMUM

data storage

Data Storage to SR3 M INIMUM

data storage problems

SR3 M INIMUM

digraph, equivalent

GT35 M INIMUM

disjoint paths

ND44 M AXIMUM | ND45 M INIMUM

dominating set

GT2 M INIMUM | GT4 M INIMUM

edge

2-spanner: GT33 M INIMUM
coloring: GT7 M INIMUM
deletion: GT25 M INIMUM | GT30 M INIMUM
dominating set: GT3 M INIMUM
installation: ND46 M INIMUM
separator: ND21 M INIMUM

elimination tree height

embedded sub-tree

GT44 M AXIMUM

evolutionary trees

exact cover

SP5 M INIMUM

feedback sets in graphs

GT8 M INIMUM | GT9 M INIMUM

finite automata

AL1 M INIMUM

flow problems

Flow Problems to ND46 M INIMUM

front size

geometric problems

graph

bipartite: GT16 M INIMUM | GT23 M AXIMUM | GT24 M INIMUM | GT26 M AXIMUM | GT27 M INIMUM | ND12 M INIMUM
bisection: ND11 M AXIMUM
chordal: GT23 M AXIMUM | GT26 M AXIMUM | GT27 M INIMUM | GT37 M INIMUM | GT37 M INIMUM | ND47 M INIMUM
claw free: GT1 M INIMUM | GT21 M AXIMUM
coloring: GT5 M INIMUM
connectivity: ND24 M INIMUM | ND25 M INIMUM | ND26 M INIMUM
covering with bipartite subgraphs: GT16 M INIMUM
covering with cliques: GT15 M INIMUM
covering with cuts: GT19 M INIMUM
covering with cycles: GT17 M INIMUM | GT18 M INIMUM
diameter: ND28 M INIMUM | ND53 M INIMUM
drawing: ND57 M INIMUM
embedding: ND12 M INIMUM
inference: GT51 M INIMUM
interval: GT23 M AXIMUM | GT26 M AXIMUM | GT36 M INIMUM
motion planning: GP1 M INIMUM
outerplanar: GT23 M AXIMUM | GT26 M AXIMUM | GT27 M INIMUM | GT29 M AXIMUM | ND47 M INIMUM
partition into cliques: GT13 M INIMUM
planar: GT1 M INIMUM | GT1 M INIMUM | GT2 M INIMUM | GT3 M INIMUM | GT5 M INIMUM | GT8 M INIMUM | GT9 M INIMUM | GT10 M AXIMUM | GT11 M AXIMUM | GT21 M AXIMUM | GT23 M AXIMUM | GT26 M AXIMUM | GT27 M INIMUM | GT29 M AXIMUM | GT30 M INIMUM | ND6 M INIMUM | ND15 M INIMUM | ND21 M INIMUM | ND22 M INIMUM | ND23 M INIMUM | ND30 M INIMUM | ND31 M INIMUM | ND34 M INIMUM | ND44 M AXIMUM | ND44 M AXIMUM | ND48 M INIMUM | ND57 M INIMUM
strong connectivity: ND27 M INIMUM
transformation: GT45 M INIMUM
unit disk: GT1 M INIMUM | GT2 M INIMUM | GT3 M INIMUM | GT4 M INIMUM | GT5 M INIMUM | GT10 M AXIMUM | GT11 M AXIMUM | GT21 M AXIMUM

Hamiltonian circuit

GT38 M AXIMUM

heaviest subgraph

GT32 M AXIMUM

hitting set

SP7 M INIMUM

Hopfield nets

MS4 M INIMUM

Horn clauses

Horn core

LO13 M AXIMUM

hypergraph

cut: SP3 M AXIMUM
matching: SP2 M AXIMUM
quotient cut: ND23 M INIMUM

hyperplane consistency

MP12 M AXIMUM

independence number

GT4 M INIMUM

independent

dominating set: GT4 M INIMUM
sequence of vertices: GT22 M AXIMUM
set: GT21 M AXIMUM

induced subgraph

GT23 M AXIMUM | GT26 M AXIMUM | GT34 M AXIMUM | GT43 M AXIMUM

integer programming

MP1 M INIMUM | MP2 M AXIMUM | MP3 M AXIMUM | MP4 M INIMUM

interval graphs

GT23 M AXIMUM | GT26 M AXIMUM | GT36 M INIMUM

isomorphism problems

Iso- and Other Morphisms to GT45 M INIMUM

knapsack problems

MP13 M AXIMUM | MP14 M AXIMUM | MP15 M AXIMUM

lattices

MP16 N EAREST

linear arrangement

GT40 M INIMUM | GT41 M INIMUM

linear systems of relations

MP9 M INIMUM | MP10 M AXIMUM | MP11 M INIMUM

logic problems

Propositional Logic to LO13 M AXIMUM

Longest

Common Subsequence: SR6 L ONGEST
Computation: AL2 L ONGEST
Induced Chordal Subgraph: GT26 M AXIMUM
Induced Cycle: GT26 M AXIMUM
Induced Path: GT26 M AXIMUM
Minimal Common Supersequence: SR4 S HORTEST
Path: ND39 L ONGEST
Path with Forbidden Pairs: GT46 L ONGEST

map labeling

MS12 M AXIMUM

matching problems

GT11 M AXIMUM | GT12 M INIMUM | SP1 M AXIMUM | SP2 M AXIMUM

mathematical programming

Mathematical Programming to MP17 M INIMUM

Maximum

2-Satisfiability

3-Dimensional Matching

SP1 M AXIMUM

3-Satisfiability

Achromatic Number

GT6 M AXIMUM

Acyclic Subgraph

GT9 M INIMUM

Betweenness

MS1 M AXIMUM

Bisection

ND11 M AXIMUM

Bounded 0-1 Programming

MP2 M AXIMUM

Capacity Representatives

SP11 M AXIMUM

Channel Assignment

MS5 M AXIMUM

Clique

GT20 M AXIMUM

k -Colorable Induced Subgraph

GT34 M AXIMUM

k -Colorable Subgraph

GT31 M AXIMUM

Common Embedded Sub-tree

GT44 M AXIMUM

Common Induced Subgraph

GT43 M AXIMUM

Common Point Set

SR8 M AXIMUM

Common Subgraph

GT42 M AXIMUM

Common Subtree

SR7 M AXIMUM

Compatible Binary Constraint Satisfaction

MS10 M AXIMUM

Compression

SR5 S HORTEST

Constrained Hamiltonian Circuit

GT38 M AXIMUM

Constrained Sequencing to Minimize Tardy Task Weight

SS1 M AXIMUM

k -Constraint Satisfaction

LO12 M AXIMUM

k -Cut

ND11 M AXIMUM | ND14 M AXIMUM

Degree-Bounded Connected Subgraph

GT28 M AXIMUM

Directed Cut

ND13 M AXIMUM

Disjoint Connecting Paths

ND44 M AXIMUM

Distinguished Ones

LO6 M AXIMUM

Edge Subgraph

GT32 M AXIMUM

k -Facility Dispersion

ND54 M AXIMUM

k -Facility Location

ND55 M AXIMUM

Geometric

Traveling Salesperson: ND31 M INIMUM

Geometric Square Packing

SP8 M INIMUM

Graph Transformation

GT45 M INIMUM

H-Matching

GT11 M AXIMUM

Horn Core

LO13 M AXIMUM

Hypergraph Cut

SP3 M AXIMUM

Hypergraph Matching

SP2 M AXIMUM

Hyperplane Consistency

MP12 M AXIMUM

Independent Sequence

GT22 M AXIMUM

Independent Set

GT21 M AXIMUM

Independent Set of k -gons

GT21 M AXIMUM

Induced Connected Subgraph with Property P

GT26 M AXIMUM

Induced Subgraph with Property P

GT23 M AXIMUM

Integer k -Choice Knapsack

MP15 M AXIMUM

Integer m -Dimensional Knapsack

MP14 M AXIMUM

Integral " k -Multicommodity Flow on Trees

ND43 M AXIMUM

Knapsack

MP13 M AXIMUM

Leaf Spanning Tree

ND4 M AXIMUM

Map Labeling

MS12 M AXIMUM

Matching of Consistent k -Cliques

GT11 M AXIMUM

Metric

Traveling Salesperson: ND30 M INIMUM

Minimum k -Steiner Tree

Minimum Metric k -TSP

Minimum Metric " k -Spanning Tree

Not-All-Equal 3-Satisfiability

LO4 M AXIMUM

Number of Satisfiable Formulas

LO9 M AXIMUM

Ones

LO6 M AXIMUM

Outerplanar Subgraph

GT29 M AXIMUM

Packing Integer Programming

MP3 M AXIMUM

Planar Subgraph

GT29 M AXIMUM

Priority Flow

ND42 M AXIMUM

Quadratic Programming

MP5 M AXIMUM

Remote Minimum Spanning Tree

k -Satisfiability

LO1 M AXIMUM | LO2 M AXIMUM

Satisfiability of Horn Clauses

Satisfiability of Quadratic Equations over GF[ q ]

AN1 M AXIMUM

Satisfying Linear Subsystem

MP10 M AXIMUM

Scatter TSP

ND33 M INIMUM

k -Set Packing

SP2 M AXIMUM | SP2 M AXIMUM

Set Splitting

SP3 M AXIMUM

Subset Sum

MP13 M AXIMUM

Traveling Salesperson

ND29 M INIMUM

Triangle Packing

GT10 M AXIMUM

Weighted Satisfiability with Bound

LO8 M AXIMUM

metric basis

GT49 M INIMUM

Minimum

0-1 Programming

MP1 M INIMUM

3-Dedicated Processor Scheduling

SS13 M INIMUM

3-Dimensional Assignment

SP10 M INIMUM

3DNF Satisfiability

LO5 M INIMUM

Absolute k -Center

-All-Neighbor k -Center

Assymmetric k -Center

Attraction Radius for Binary Hopfield Net

MS4 M INIMUM

b -Balanced Cut

ND21 M INIMUM

Bandwidth

GT39 M INIMUM

Bend Number

ND57 M INIMUM

Biconnectivity Augmentation

ND26 M INIMUM

Bin Packing

SR1 M INIMUM

Bipartition

GT30 M INIMUM

Block-angular Convex Programming

MP17 M INIMUM

Bottleneck Path Matching

GT12 M INIMUM

Bounded Diameter Augmentation

ND28 M INIMUM

Broadcast Time

ND47 M INIMUM

Capacitated k -Center

k -Capacitated Tree Partition

GT14 M INIMUM

k -Center

Chinese Postman for Mixed Graphs

ND34 M INIMUM

Chinese Postman Problem

ND35 M INIMUM

Chordal Graph Completion

GT37 M INIMUM

Chromatic Index

GT7 M INIMUM

Chromatic Number

Clique Cover

GT15 M INIMUM

Clique Partition

GT13 M INIMUM

k -Clustering

ND49 M INIMUM

k -Clustering Sum

ND50 M INIMUM

Complete Bipartite Subgraph Cover

GT16 M INIMUM

Consistent Finite Automaton

AL1 M INIMUM

Constrained Partition

SP9 M AXIMUM

Covering Integer Programming

MP4 M INIMUM

Crossing Number

ND12 M INIMUM

k -Cut

ND16 M INIMUM

Cut Cover

GT19 M INIMUM

Cut Linear Arrangement

GT41 M INIMUM

Degree Spanning Tree

ND2 M INIMUM

Degree Steiner Tree

ND2 M INIMUM

Diameter Spanning Subgraph

ND6 M INIMUM

Diameters Decomposition

ND53 M INIMUM

Distinguished Ones

LO7 M INIMUM

Dominating Set

GT2 M INIMUM

Dynamic Storage Allocation

SR3 M INIMUM

Edge 2-Spanner

GT33 M INIMUM

Edge Coloring

GT7 M INIMUM

k -Edge Connected Subgraph

ND25 M INIMUM

Edge Deletion

Bipartition: GT30 M INIMUM
k -Partition: GT30 M INIMUM
to Obtain Subgraph with Property P: GT25 M INIMUM

Edge Deletion

Edge Disjoint Cycle Cover

GT18 M INIMUM

Edge Dominating Set

GT3 M INIMUM

b -Edge Separator

ND21 M INIMUM

Elimination Tree Height

Equivalence Deletion

LO11 M INIMUM

Equivalent Digraph

GT35 M INIMUM

Evolutionary Tree

Exact Cover

SP5 M INIMUM

Feedback Arc Set

GT9 M INIMUM

Feedback Vertex Set

GT8 M INIMUM

File Transfer Scheduling

SS18 M INIMUM

Flow-Shop Scheduling

SS15 M INIMUM

Flux Cut

ND23 M INIMUM

Fractional Chromatic Number

Frequency Allocation

MS14 M INIMUM

Front Size

General Routing

ND38 M INIMUM

Generalized 0-1 Assignment

MP6 M INIMUM

Generalized Steiner Network

ND9 M INIMUM

Generalized Tree Alignment

Geometric

3-Degree Spanning Tree: ND3 M INIMUM
Angular Traveling Salesperson: ND31 M INIMUM
Capacitated k -Center: ND48 M INIMUM
k -Clustering: ND49 M INIMUM
k -Spanning Tree: ND1 M INIMUM
Steiner Tree: ND8 M INIMUM
Traveling Salesperson: ND31 M INIMUM

Geometric

Geometric Disk Cover

SP8 M INIMUM

Graph Coloring

Graph Inference

GT51 M INIMUM

Graph Motion Planning

GP1 M INIMUM

Height Two Dimensional Packing

SR2 M INIMUM

Hitting Set

SP7 M INIMUM

Independent Dominating Set

GT4 M INIMUM

Interval Graph Completion

GT36 M INIMUM

Job Shop Scheduling

SS17 M INIMUM

Length Triangulation

ND58 M INIMUM

Linear Arrangement

GT40 M INIMUM

k -Link Path in a Polygon

MS6 M INIMUM

Locally Testable Automaton Order

AL4 M INIMUM

Maximal Independence Number

GT4 M INIMUM

Maximum Disjoint Connecting Paths

ND45 M INIMUM

k -Median

ND52 M INIMUM

Metric

Bottleneck Wandering Salesperson Problem: ND33 M INIMUM
Traveling k -Salesperson Problem: ND32 M INIMUM
Traveling Salesperson: ND30 M INIMUM

Metric

Metric Dimension

GT49 M INIMUM

Multi-Cut

ND19 M INIMUM

Multiprocessor Scheduling

SS6 M INIMUM

Multiprocessor Scheduling with Speed Factors

SS10 M INIMUM

Multiway Cut

ND18 M INIMUM

k -Multiway Separator

ND21 M INIMUM

Net Expansion

ND23 M INIMUM

Network Inhibition on Planar Graphs

ND15 M INIMUM

Nonplanar Edge Deletion

GT29 M AXIMUM

Number of Satisfiable Formulas

LO10 M INIMUM

Ones

LO7 M INIMUM

Open-Shop Scheduling

SS14 M INIMUM

Parallel Processor Total Flow Time

SS11 M INIMUM

k -Partition

GT30 M INIMUM

Partition of Rectangle with Interior Points

MS8 M INIMUM

Path Coloring

ND44 M AXIMUM

Path Width

Permutation Group Base

AL5 M INIMUM

phylogenetic tree distance

MS13 M INIMUM

Planar Record Packing

MP8 M INIMUM

Point-To-Point Connection

GT48 M INIMUM

Precedence Constrained Scheduling

SS7 M INIMUM

Precedence Constrained Sequencing with Delays

SS3 M INIMUM

Preemptive Scheduling with Set-Up Times

SS9 M INIMUM

Quadratic 0-1 Assignment

MP7 M INIMUM

Quotient Cut

ND23 M INIMUM

Ratio-Cut

ND20 M INIMUM

Rectangle Cover

SR9 M INIMUM

Rectilinear Global Routing

ND41 M INIMUM

Register Sufficiency

PO1 M INIMUM

Relevant Variables in Linear System

MP9 M INIMUM

Resource Constrained Scheduling

SS8 M INIMUM

Routing Tree Congestion

ND10 M INIMUM

Rural Postman Problem

ND38 M INIMUM

k -Satisfiability

LO1 M AXIMUM | LO3 M INIMUM

Satisfiability of Horn Clauses

LO3 M INIMUM

Schedule Length

SS19 M INIMUM

Separating Subdivision

ND59 M INIMUM

Sequencing with Release Times

SS4 M INIMUM

Set Cover

SP4 M INIMUM

Single-Sink Edge Installation

ND46 M INIMUM

Size Ultrametric Tree

MS7 M INIMUM

Sorting by Reversals

MS9 M INIMUM

k -Spanning Tree

ND1 M INIMUM

k -Stacker Crane Problem

ND36 M INIMUM | ND37 M INIMUM

Steiner Tree

ND7 M INIMUM

Steiner Trees with Obstacles

ND8 M INIMUM

Storage-Time Sequencing

SS2 M INIMUM

Strip Packing

SR2 M INIMUM

Strong Connectivity Augmentation

ND27 M INIMUM

k -Supplier

ND51 M INIMUM

Survivable Network

ND9 M INIMUM

k -Switching Network

ND56 M INIMUM

Test Collection

SP6 M INIMUM

Time-Cost Tradeoff

SS5 M INIMUM

Travel Robot Localization

GP2 M INIMUM

Traveling Salesperson

ND29 M INIMUM

Tree Alignment

Tree Compact Packing

SR10 M INIMUM

Tree Width