Combinatorial Optimization: Networks and Matroids
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.
What people are saying - Write a review
We haven't found any reviews in the usual places.
Matroids and the Greedy Algorithm
The Matroid Parity Problem
Other editions - View all
alternating trees applied arc i,j arc lengths assignment problem augmenting path augmenting sequence backtracing base node bipartite graph bipartite matching cardinality matching Chapter cocycle combinatorial constraints contains convex cutset D. R. Fulkerson digraph directed cycle dual solution dual variables duality Edmonds elements equations example exists feasible solution finite flow network flow problem follows formulated given go to Step graph G greedy algorithm incidence matrix independent set inequalities integer intersection problem labeling procedure linear programming problem Math max-flow min-cut theorem maximal flow maximum cardinality maximum number maximum weight minimal minimum cost flow negative cycles network flow nonbipartite number of arcs obtained optimal solution outermost blossom pair partition matroid path computation polynomial primal and dual proof pseudonode Return to Step S-label scanned Section shortest path problem shown in Figure solve spanning tree Steiner subgraph Suppose Theorem theory unlabeled unscanned vector weighted matching problem zero