Combinatorial Optimization: Networks and MatroidsCourier Corporation, 1 בינו׳ 2001 - 374 עמודים 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. |
תוכן
lntroduction | 12 |
Mathematical Preliminaries | 15 |
Shortest Paths | 59 |
Network Flows | 109 |
Bipartite Matching | 182 |
Nonbipartite Matching | 217 |
Matroids and the Greedy Algorithm | 264 |
Matroid Intersections | 300 |
The Matroid Parity Problem | 356 |
מהדורות אחרות - הצג הכל
Combinatorial Optimization: Networks and Matroids <span dir=ltr>Eugene Lawler</span> תצוגה מקדימה מוגבלת - 2012 |
מונחים וביטויים נפוצים
a₁ acyclic alternating trees applied arc lengths assignment problem augmenting path augmenting sequence b₁ backtracing base node bipartite graph bipartite matching c₁ cardinality matching cocycle combinatorial computation constraints contains convex cutset D. R. Fulkerson digraph directed cycle dual solution dual variables e₁ Edmonds elements equations example exists feasible solution 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 M₁ M₂ Math max-flow min-cut theorem maximal flow maximum cardinality maximum number maximum weight minimal negative cycles network flow number of arcs O(n² O(n³ obtained optimal solution pair partition matroid path computation proof pseudonode Return to Step S-label scanned Section shortest path problem shown in Figure solve sp₁ spanning tree subgraph subset Suppose Theorem theory u₁ unlabeled unscanned vector w₁ weighted matching problem x₁ zero
הפניות לספר זה
Data Structures and Network Algorithms <span dir=ltr>Robert Endre Tarjan</span> אין תצוגה מקדימה זמינה - 1983 |