Combinatorial Optimization

Networks and Matroids

By: EUGENE LAWLER

Write A Review

Paperback | 10 November 2011

At a Glance

Paperback
384 Pages

Dimensions(cm)
20.9 x 13.6 x 2.54

Paperback

RRP $36.25

$34.75

or 4 interest-free payments of $8.69 with

Ships in 5 to 7 business days

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.

Shipping

	Standard Shipping	Express Shipping
Metro postcodes:	$9.99	$14.95
Regional postcodes:	$9.99	$14.95
Rural postcodes:	$9.99	$14.95

Orders over $79.00 qualify for free shipping.

How to return your order

At Booktopia, we offer hassle-free returns in accordance with our returns policy. If you wish to return an item, please get in touch with Booktopia Customer Care.

Additional postage charges may be applicable.

Defective items

If there is a problem with any of the items received for your order then the Booktopia Customer Care team is ready to assist you.

For more info please visit our Help Centre.

You Can Find This Book In

Non-Fiction Mathematics Combinatorics & Graph Theory Algebra Engineering & Technology Technology in General Engineering in General Optimisation Game Theory

Preface	p. iii
Introduction	p. 1
What is Combinatorial Optimization?	p. 1
Some Representative Optimization Problems	p. 2
When is a Problem Solved?	p. 4
The Criterion of Polynomial Boundedness	p. 5
Some Apparently Nonpolynomial-Bounded Problems	p. 8
Methods of Solution	p. 10
Comments and References	p. 12
Mathematical Preliminaries	p. 15
Mathematical Prerequisites	p. 15
Sets and Relations	p. 16
Graphs and Digraphs	p. 20
Subgraphs, Cliques, Multigraphs	p. 24
Connectivity in Graphs	p. 26
Connectivity in Digraphs	p. 28
Cocycles and Directed Cocycles	p. 31
Planarity and Duality	p. 32
Eulerian and Hamiltonian Graphs	p. 36
Linear Programming Problems	p. 39
The Simplex Method	p. 43
Geometric Interpretation	p. 48
Duality Theory	p. 53
Comments and References	p. 58
Shortest Paths	p. 59
Introduction	p. 59
Some Problem Formulations	p. 61
Bellman's Equations	p. 65
Acyclic Networks	p. 68
Networks with Positive Arcs: Dijkstra's Method	p. 70
Solution by Successive Approximations: Bellman-Ford Method Method	p. 74
Improvements in Efficiency: Yen's Modifications	p. 76
Linear Programming Interpretation and Relaxation Procedures	p. 77
Shortest Paths between all Pairs of Nodes: Matrix Multiplication	p. 82
Floyd-Warshall Method	p. 86
Detection of Negative Cycles	p. 90
Networks with Transit Times	p. 92
The Minimal Cost-to-time Ratio Cycle Problem	p. 94
M Shortest Paths: Dreyfus Method	p. 98
M Shortest Paths without Repeated Nodes	p. 100
Comments and References	p. 104
Network Flows	p. 109
Introduction	p. 109
Maximal Flows	p. 110
Maximal Flow Algorithm	p. 114
Efficiency of the Maximal Flow Algorithm	p. 116
Combinatorial Implications of Max-Flow Min-Cut Theorem	p. 120
Linear Programming Interpretation of Max-Flow Min-Cut Theorem	p. 123
Minimum Cost Flows	p. 129
Networks with Losses and Gains	p. 134
Lower Bounds and Circulations	p. 138
The Out-of-Kilter Method	p. 142
Theoretical Improvement in Efficiency of Out-of-Kilter Method	p. 157
Integrality of Flows and the Unimodular Property	p. 160
Application to Project Scheduling	p. 165
Transhipment and Transportation Problems	p. 169
Multiterminal and Multicommodity Flows	p. 173
Comments and References	p. 177
Bipartite Matching	p. 182
Introduction	p. 182
Problem Reductions and Equivalences	p. 184
Counterparts of Network Flow Theorems	p. 188
Mendelsohn-Dulmage Theorem	p. 191
Cardinality Matching Algorithm	p. 193
A Special Case: Convex Graphs	p. 196
Max-Min Matching	p. 197
The Hungarian Method for Weighted Matching	p. 201
A Special Case: Gilmore-Gomory Matching	p. 207
A Novel Optimization Criterion: Gale-Shapley Matching	p. 211
Comments and References	p. 214
Nonbipartite Matching	p. 217
Introduction	p. 217
Problem Formulations	p. 218
Bidirected Flows	p. 223
Augmenting Paths	p. 226
Trees and Blossoms	p. 229
Cardinality Matching Algorithm	p. 233
Duality Theory	p. 239
Linear Programming Formulation of Weighted Matching Problem	p. 242
An O (n[superscript 4]) Weighted Matching Algorithm	p. 247
An O (n[superscript 3]) Weighted Matching Algorithm	p. 252
The Chinese Postman's Problem	p. 259
Comments and References	p. 261
Matroids and the Greedy Algorithm	p. 264
Introduction	p. 264
Three Apparently Unrelated Optimization Problems	p. 265
Matroid Definitions	p. 268
Matching, Transversal, and Partition Matroids	p. 271
Matroid Axiomatics	p. 273
The Matroid Greedy Algorithm	p. 275
Applications of the Greedy Algorithm	p. 278
Matroid Duality	p. 280
Variations of the Greedy Algorithm	p. 283
Prim Spanning Tree Algorithm	p. 285
An Application: Flow Network Synthesis	p. 286
The Steiner Problem and Other Dilemmas	p. 290
Comments and References	p. 296
Matroid Intersections	p. 300
Introduction	p. 300
Problem Formulations	p. 301
Augmenting Sequences and Border Graphs	p. 306
Cardinality Intersection Algorithm	p. 313
Duality Theory	p. 315
Generalized Mendelsohn-Dulmage Theorem, Matroid Sums and Matroid Partitions	p. 317
Matroid Partitioning Algorithm	p. 320
The Shannon Switching Game	p. 324
Weighted Augmenting Sequences	p. 326
Primal Weighted Intersection Algorithm	p. 332
Matroid Polyhedra	p. 334
Explanation of Primal-Dual Method	p. 339
Primal-Dual Weighted Intersection Algorithm	p. 345
A Special Case: Directed Spanning Trees	p. 348
Comments and References	p. 352
The Matroid Parity Problem	p. 356
Introduction	p. 356
Problem Formulations	p. 358
Augmenting Sequences	p. 363
Generalizations	p. 364
Comments and References	p. 367
Author Index	p. 368
Subject Index	p. 371
Table of Contents provided by Syndetics. All Rights Reserved.

Combinatorial Optimization

Networks and Matroids

At a Glance

Paperback

Shipping

How to return your order

Defective items

You Can Find This Book In

More in Mathematics

In the Realm of the Last Man

FROM THE GLOBALLY BESTSELLING AUTHOR OF THE END OF HISTORY AND THE LAST MAN

Numeracy in Early Childhood

Shared Contexts For Teaching And Learning

How to Win At Chess

The Ultimate Guide for Beginners and Beyond

The Art of Gathering

How We Meet and Why It Matters

Maths Sequences for the Early Years F-2

Challenging Children to Reason Mathematically

Antifragile

Things That Gain from Disorder

Oxford Maths for Australian Schools Year 4 Value Pack

3rd Edition

Statistics and Data Handling for Biologists

A Student's Guide

Statistics and Data Handling for Biologists

A Student's Guide

A Beginner's Guide to Structural Equation Modeling

with LISREL, Mplus, and R

Collins Classics - The Republic

Collins Classics

Games, Markets, and Online Learning

Games, Markets, and Online Learning

Dynamics of Marine Structures

Stochastic Control in Energy, Environmental and Resource Management Applications

Emerging Methodologies and Applications in Modelling, Identification and Control

Recent Advances in Information Systems

Proceedings of the ICRAIS, Pointe aux Piments, Mauritius, 10-12 September 2025

Healthcare Quality Measurement

Volume 1, History and Practice of Healthcare Quality Measurement

Healthcare Quality Measurement

Volume 1, History and Practice of Healthcare Quality Measurement

Healthcare Quality Measurement

Volume 2, Statistical Methodology

Healthcare Quality Measurement

Volume 2, Statistical Methodology

Data Science and Social Research III

Epistemology, Methods, Technology, Applications, and Relation to Artificial Intelligence

Kernel-Based Methods

Milestones and New Trends

Modal Semirings and Applications

Trends in Logic

Mathematics of Uncertainty Applied to Global Issues

Sustainability, Mistreatment of Women, Nuclear Power, Smart Cities, Digitalization

This product is categorised by