## Combinatorial Optimization: Networks and MatroidsPerceptively 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. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Chapter | 1 |

Some Representative Optimization Problems | 2 |

When is a Problem Solved? | 4 |

Copyright | |

90 other sections not shown

### Other editions - View all

### Common terms and phrases

acyclic adjacency matrix alternating trees arc lengths assignment problem augmenting path augmenting sequence backtracing base node basic feasible solution bipartite graph bipartite matching cardinality matching cocycle column combinatorial computation constraints contains cutset digraph directed cycle directed graph dual solution dual variables duality Edmonds elements equations example exists finite flow network flow problem follows given go to Step graph G greedy algorithm incidence matrix independent set inequalities integer intersection problem labeling procedure linear programming problem max-flow min-cut theorem max-min maximal flow maximum cardinality maximum number maximum weight minimal negative cycles network flow nonbipartite nonnegative number of arcs objective function obtained optimal solution pair partition matroid path computation polynomial polynomial-bounded primal and dual proof pseudonode Return to Step S-label scanned Section shortest path problem shown in Figure simplex method solve spanning tree subgraph subset Suppose Theorem theory unlabeled unscanned vector weighted matching problem zero