Combinatorial Optimization: Networks and Matroids

Combinatorial Optimization: Networks and Matroids

by Eugene Lawler


View All Available Formats & Editions
Eligible for FREE SHIPPING
  • Want it by Friday, September 28  Order now and choose Expedited Shipping during checkout.


Combinatorial Optimization: Networks and Matroids by Eugene Lawler

Perceptively written text examines optimization problems that can be formulated in terms of networks and algebraic structures called matroids. Chapters cover shortest paths, network flows, bipartite matching, nonbipartite matching, matroids and the greedy algorithm, matroid intersections, and the matroid parity problems. A suitable text or reference for courses in combinatorial computing and concrete computational complexity in departments of computer science and mathematics.

Product Details

ISBN-13: 9780486414539
Publisher: Dover Publications
Publication date: 11/10/2011
Series: Dover Books on Mathematics
Edition description: Reprint
Pages: 384
Product dimensions: 5.50(w) x 8.50(h) x (d)

Table of Contents

Chapter 1Introduction1
1.What is Combinatorial Optimization?1
2.Some Representative Optimization Problems2
3.When is a Problem Solved?4
4.The Criterion of Polynomial Boundedness5
5.Some Apparently Nonpolynomial-Bounded Problems8
6.Methods of Solution10
Comments and References12
Chapter 2Mathematical Preliminaries15
1.Mathematical Prerequisites15
2.Sets and Relations16
3.Graphs and Digraphs20
4.Subgraphs, Cliques, Multigraphs24
5.Connectivity in Graphs26
6.Connectivity in Digraphs28
7.Cocycles and Directed Cocycles31
8.Planarity and Duality32
9.Eulerian and Hamiltonian Graphs36
10.Linear Programming Problems39
11.The Simplex Method43
12.Geometric Interpretation48
13.Duality Theory53
Comments and References58
Chapter 3Shortest Paths59
2.Some Problem Formulations61
3.Bellman's Equations65
4.Acyclic Networks68
5.Networks with Positive Arcs: Dijkstra's Method70
6.Solution by Successive Approximations: Bellman-Ford Method Method74
7.Improvements in Efficiency: Yen's Modifications76
8.Linear Programming Interpretation and Relaxation Procedures77
9.Shortest Paths between all Pairs of Nodes: Matrix Multiplication82
10.Floyd-Warshall Method86
11.Detection of Negative Cycles90
12.Networks with Transit Times92
13.The Minimal Cost-to-time Ratio Cycle Problem94
14.M Shortest Paths: Dreyfus Method98
15.M Shortest Paths without Repeated Nodes100
Comments and References104
Chapter 4Network Flows109
2.Maximal Flows110
3.Maximal Flow Algorithm114
4.Efficiency of the Maximal Flow Algorithm116
5.Combinatorial Implications of Max-Flow Min-Cut Theorem120
6.Linear Programming Interpretation of Max-Flow Min-Cut Theorem123
7.Minimum Cost Flows129
8.Networks with Losses and Gains134
9.Lower Bounds and Circulations138
10.The Out-of-Kilter Method142
11.Theoretical Improvement in Efficiency of Out-of-Kilter Method157
12.Integrality of Flows and the Unimodular Property160
13.Application to Project Scheduling165
14.Transhipment and Transportation Problems169
15.Multiterminal and Multicommodity Flows173
Comments and References177
Chapter 5Bipartite Matching182
2.Problem Reductions and Equivalences184
3.Counterparts of Network Flow Theorems188
4.Mendelsohn-Dulmage Theorem191
5.Cardinality Matching Algorithm193
6.A Special Case: Convex Graphs196
7.Max-Min Matching197
8.The Hungarian Method for Weighted Matching201
9.A Special Case: Gilmore-Gomory Matching207
10.A Novel Optimization Criterion: Gale-Shapley Matching211
Comments and References214
Chapter 6Nonbipartite Matching217
2.Problem Formulations218
3.Bidirected Flows223
4.Augmenting Paths226
5.Trees and Blossoms229
6.Cardinality Matching Algorithm233
7.Duality Theory239
8.Linear Programming Formulation of Weighted Matching Problem242
9.An O (n[superscript 4]) Weighted Matching Algorithm247
10.An O (n[superscript 3]) Weighted Matching Algorithm252
11.The Chinese Postman's Problem259
Comments and References261
Chapter 7Matroids and the Greedy Algorithm264
2.Three Apparently Unrelated Optimization Problems265
3.Matroid Definitions268
4.Matching, Transversal, and Partition Matroids271
5.Matroid Axiomatics273
6.The Matroid Greedy Algorithm275
7.Applications of the Greedy Algorithm278
8.Matroid Duality280
9.Variations of the Greedy Algorithm283
10.Prim Spanning Tree Algorithm285
11.An Application: Flow Network Synthesis286
12.The Steiner Problem and Other Dilemmas290
Comments and References296
Chapter 8Matroid Intersections300
2.Problem Formulations301
3.Augmenting Sequences and Border Graphs306
4.Cardinality Intersection Algorithm313
5.Duality Theory315
6.Generalized Mendelsohn-Dulmage Theorem, Matroid Sums and Matroid Partitions317
7.Matroid Partitioning Algorithm320
8.The Shannon Switching Game324
9.Weighted Augmenting Sequences326
10.Primal Weighted Intersection Algorithm332
11.Matroid Polyhedra334
12.Explanation of Primal-Dual Method339
13.Primal-Dual Weighted Intersection Algorithm345
14.A Special Case: Directed Spanning Trees348
Comments and References352
Chapter 9The Matroid Parity Problem356
2.Problem Formulations358
3.Augmenting Sequences363
Comments and References367
Author Index368
Subject Index371

Customer Reviews

Most Helpful Customer Reviews

See All Customer Reviews