Book contents
- Frontmatter
- Contents
- Preface
- Introduction
- 0 Polytopes and Linear Programming
- 1 Matroids and the Greedy Algorithm
- 2 Minimum-Weight Dipaths
- 3 Matroid Intersection
- 4 Matching
- 5 Flows and Cuts
- 6 Cutting Planes
- 7 Branch-&-Bound
- 8 Optimizing Submodular Functions
- Appendix: Notation and Terminology
- References
- Indexes
2 - Minimum-Weight Dipaths
Published online by Cambridge University Press: 28 January 2010
- Frontmatter
- Contents
- Preface
- Introduction
- 0 Polytopes and Linear Programming
- 1 Matroids and the Greedy Algorithm
- 2 Minimum-Weight Dipaths
- 3 Matroid Intersection
- 4 Matching
- 5 Flows and Cuts
- 6 Cutting Planes
- 7 Branch-&-Bound
- 8 Optimizing Submodular Functions
- Appendix: Notation and Terminology
- References
- Indexes
Summary
One of the simplest combinatorial-optimization problems is that of finding a minimum-weight dipath in an edge-weighted digraph (under some natural restrictions on the weight function). Not only are there rather simple algorithms for this problem, but algorithms for the minimum-weight dipath problem are fundamental building blocks for developing solution methods for more complicated problems.
Let G be a strict digraph. A v w diwalk is a sequence of edges ei, 1 ≤ i ≤ p (with p ≥ 0), such that t(e1) = v (if p > 0), h(ep) = w (if p > 0), and h(ei) = t(ei+1), for 1 ≤ i < p. Neither the edges nor the vertices need be distinct. The v w diwalk imputes the sequence of vertices v = t(e1),h(e1) = t(e2), h(e2) = t(e3), …, h(ep-1) = t(ep), h(ep) = w. If no vertex in this imputed vertex sequence is repeated, then the vw diwalk is called a vw dipath. In such a case, every vertex of the imputed sequence other than v and w is called an interior vertex. Note that the empty sequence of edges is a vv diwalk for any vertex v; the associated imputed sequence of vertices is also empty, so the empty sequence of edges is a vv dipath. If v = w, and the only repetition in the imputed vertex sequence is the consonance of the first element with the last, then the diwalk is a dicycle.
- Type
- Chapter
- Information
- A First Course in Combinatorial Optimization , pp. 75 - 83Publisher: Cambridge University PressPrint publication year: 2004