Connections in combinatorial optimization / András Frank.

Saved in:
Bibliographic Details
Main Author: Frank, András, 1949-
Language:English
Published: Oxford : Oxford University Press, 2011.
Series:Oxford lecture series in mathematics and its applications ; 38.
Subjects:
Combinatorial optimization.
Connections (Mathematics)
Physical Description:xxiii, 639 pages : illustrations ; 24 cm.
Format: Book
Contents:
  • Machine generated contents note: pt. I BASIC COMBINATORIAL OPTIMIZATION
  • 1. Elements of graphs and hypergraphs
  • 1.1. Fundamentals
  • 1.2. Cut functions and connectivity concepts
  • 1.3. Special graphs and digraphs
  • 1.4. Special hypergraphs and bi-set systems
  • 1.5. Complexity of problems and algorithms
  • 2. Connectivity, paths, and matchings
  • 2.1. 2-connection of graphs
  • 2.2. Strong connectivity
  • 2.3. Degree-constrained orientations
  • 2.4. Bipartite matchings
  • 2.5. Disjoint paths
  • 3. Elements of network optimization
  • 3.1. Cheapest paths and feasible potentials
  • 3.2. Cheapest trees and arborescences
  • 3.3. Weighted matchings of bipartite graphs
  • 3.4. Flows and circulations
  • 3.5. Computing maximum flows
  • 3.6. Cheapest flows
  • 4. Elements of polyhedral combinatorics
  • 4.1. Linear inequality systems and polyhedra
  • 4.2. Total unimodularity
  • 4.3. Applications of totally unimodular matrices
  • 5. Elements of matroid theory.
  • 5.1. Independence and rank
  • 5.2. Circuits and connectivity
  • 5.3. Bases, rank, and co-rank
  • 5.4. Constructing matroids
  • 5.5. Matroid algorithms and polyhedra
  • pt. II HIGHER-ORDER CONNECTIONS
  • 6. Efficient algorithms for flows and cuts
  • 6.1. Push-relabel algorithms
  • 6.2. Computing a minimum cut of a digraph
  • 6.3. Computing a minimum cut of an undirected graph
  • 6.4. Strongly polynomial algorithm for cheapest m-flows
  • 7. Structure and representations of cuts
  • 7.1. Cactus representation of minimum cuts
  • 7.2. Local edge-connectivities
  • 7.3. Solid sets
  • 7.4. Sparse certificates for directed graphs and hypergraphs
  • 7.5. Sparse certificates for undirected graphs
  • 8. The splitting-off operation and constructive characterizations
  • 8.1. Undirected splitting
  • 8.2. Directed splitting
  • 8.3. Further constructive characterizations
  • 8.4. Packing paths
  • 9. Orientations of graphs and hypergraphs
  • 9.1. Rooted k-edge-connected orientations and reorientations
  • 9.2. Global k-edge-connection.
  • 9.3. Common generalization: (k, l)-edge-connected orientations
  • 9.4. Orientation of hypergraphs
  • 9.5. Mixed graphs and orientations
  • 9.6. Optimal orientations and reorientations
  • 9.7. Optimal strongly connected reorientation
  • 9.8. Well-balanced orientations
  • 10. Trees and arborescences: packing and covering
  • 10.1. Packing arborescences
  • 10.2. Packing branchings
  • 10.3. Further generalizations
  • 10.4. Covering by branchings, trees, and forests
  • 10.5. Packing trees and forests
  • 11. Preserving and improving connections
  • 11.1. Augmenting edge-connectivity of undirected graphs
  • 11.2. Augmenting edge-connectivity of directed graphs
  • 11.3. Augmenting ST-edge- and node-connectivity of digraphs
  • 11.4. Rooted k-connections
  • pt. III SEMIMODULAR OPTIMIZATION
  • 12. Setting the stage
  • aspects and approaches
  • 12.1. Two aspects of investigation
  • 12.2. Convexity and submodularity
  • 12.3. Abstract extensions of the Konig-Hall theorem
  • 13. Matroid optimization
  • 13.1. Unweighted matroid intersection.
  • 13.2. Weighted matroid intersection
  • 13.3. Sum of matroids
  • 13.4. Matroids from intersecting sub- and supermodular functions
  • 13.5. Count matroids
  • 14. Generalized polymatroids
  • 14.1. Semimodular functions and their polyhedra
  • 14.2. Constructions and operations
  • 14.3. Intersection with a box and with a plank
  • 14.4. Intersection of two g-polymatroids
  • 14.5. The greedy algorithm
  • 15. Relaxing semimodularity
  • 15.1. Truncation
  • 15.2. Applications to branchings and augmentations
  • 15.3. Full truncation
  • 15.4. Graph orientations via base-polyhedra
  • 16. Submodular flows
  • 16.1. Submodular and supermodular flows
  • 16.2. A push-relabel algorithm for submodular flows
  • 16.3. Optimization over submodular flows
  • 17. Covering supermodular functions by digraphs
  • 17.1. Supermodular frameworks with TDI systems
  • 17.2. Non-TDI frameworks for covering set-functions
  • 17.3. Non-TDI frameworks for covering bi-set functions
  • 18. Solutions to selected problems.