## 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 | |

89 other sections not shown

### Common terms and phrases

adjacency matrix arc capacities arc i,j arc lengths assignment problem augmenting path augmenting sequence backtracing base node basic feasible solution bipartite graph bipartite matching blossom cocycle column combinatorial constraints contains cutset digraph directed cycle directed graph directed path dual solution dual variables duality elements equations Euler path example exists finite flow augmenting flow network flow problem follows formulated given go to Step graph G greedy algorithm incidence matrix independent set inequalities integer kilter number labeling procedure linear programming problem max-flow min-cut theorem maximal flow maximum weight minimal minimum cost flow minimum number negative cycles network flow node nonnegative number of arcs objective function obtained optimal solution out-of-kilter method path computation pivot step polynomial primal and dual proof pseudonode S-label scanned Section shortest path problem shown in Figure simplex method solved spanning tree subgraph subset Suppose theory tion vector yellow arcs zero