Combinatorial Optimization

Polyhedra and Efficiency

Alexander Schrijver - Collection Algorithms and Combinatorics

2286 pages, parution le 17/01/2003

Ajouter à une liste

Indisponible

Résumé

This book offers an in-depth overview of polyhedral methods and efficient algorithms in combinatorial optimization. These methods form a broad, coherent and powerful kernel in combinatorial optimization, with strong links to discrete mathematics, mathematical programming and computer science.

In eight parts, various areas are treated, each starting with an elementary introduction to the area, with short, elegant proofs of the principal results, and each evolving to the more advanced methods and results, with full proofs of some of the deepest theorems in the area. Over 4000 references to further research are given, and historical surveys on the basic subjects are presented.

L'auteur - Alexander Schrijver

CWI, Amsterdam, The Netherlands

Sommaire

Volume A
- Introduction
- General Preliminaries
- Preliminaries on Graphs
- Preliminaries on Algorithms and Complexity
- Preliminaries on Polyhedra and Linear and Integer Programming
- I- Paths and Flows
  - Shortest Paths: Unit Lengths
  - Shortest Paths: Nonnegative Lengths
  - Shortest Paths: Arbitrary Lengths
  - Disjoint Paths
  - Maximum Flow
  - Circulations and Transshipments
  - Minimum-cost and Circulations
  - Path and Flow Polyhedra and Total Unimodularity
  - Partially Ordered Sets and Path Coverings
  - Connectivity and Gomory-Hu Trees
- II- Bipartite Matching and Covering
  - Cardinality Bipartite Matching and Vertex Cover
  - Weighted Bipartite Matching and the Assignment Problem
  - Linear Programming Methods and the Bipartite Matching Polytope
  - Bipartite Edge Cover and Stable Set
  - Bipartite Edge-Colouring
  - Bipartite b-Matching and Transportation
  - Transversals
  - Common Transversals
- III- Nonbipartite Matching and Covering
  - Cardinality Nonbipartite Matching
  - The Matching Polytope
  - Weighted Nonbipartite Matching Algorithmically
  - Nonbipartite Edge Cover
  - Edge- Colouring
  - T-Joins, Undirected Shortest Paths, and The Chinese Postman
  - 2-Matching, 2-Covers, 2-Factors
  - b-Matchings
  - Capacitated b-Matchings
  - Simple b-Matchings and b-Factors
  - b-Edge Covers
  - Upper and Lower Bounds
  - Bidirected Graphs
  - The Dimension of the Perfect Matching Polytope
  - The Perfect Matching Lattice
Volume B
- IV- Matroids and Submodular Functions
  - Matroids
  - The Greedy Algorithm and the Independent Set Polytope
  - Matroid Intersection
  - Matroid Union
  - Matroid Matching
  - Submodular Functions and Polymatroids
  - Submodular Functions Minimization
  - Polymatroid Intersection
  - Polymatroid Intersection Algorithmically
  - Dilworth Truncation
  - Submodularity More Generally
- V- Trees, Branchings, and Connectors
  - Shortest Spanning Trees
  - Packing and Covering of Trees
  - Longest Branchings and Shortest Arborescences
  - Packing and Covering of Branchings and Arborescences
  - Biconnectors and Bibranchings
  - Minimum Directed Cut Covers and Packing Directed Cut
  - Minimum Directed Cuts and Packing Directed Cut Covers
  - Strong Connectors
  - The Traveling Salesman Problem
  - Matching Forests
  - Submodular Functions on Directed Graphs
  - Graph Orientation
  - Network Synthesis
  - Connectivity Augmentation
- VI- Cliques, Stable Sets, and Colouring
  - Cliques, Stable Sets, and Colouring
  - Perfect Graphs: General Theory
  - Classes of Perfect Graphs
  - Perfect Graphs: Polynomial-Time Solvability
  - T-Perfect Graphs
  - Claw-Free Graphs
Volume C
- VII- Multiflows and Disjoint Paths
  - Multiflows and Disjoint Paths
  - Two Commodities
  - Three or More Commodities
  - T-Paths
  - Planar Graphs
  - Cuts, Odd Circuits, and Multiflows
  - Homotopy and Graphs on Surfaces
- VIII- Hypergraphs
  - Packing and Blocking in Hypergraphs: Elementary Notions
  - Ideal Hypergraphs
  - Mengerian Hypergraphs
  - Binary Hypergraphs
  - Matroids and Multiflows
  - Covering and Antiblocking in Hypergraphs
  - Balanced and Unimodular Hypergraphs

Voir tout

Replier

Caractéristiques techniques

	PAPIER
Éditeur(s)	Springer
Auteur(s)	Alexander Schrijver
Collection	Algorithms and Combinatorics
Parution	17/01/2003
Nb. de pages	2286
Format	16 x 24
Couverture	Relié
Poids	3600g
Intérieur	Noir et Blanc
EAN13	9783540443896
ISBN13	978-3-540-44389-6