| Combinatorial Optimization (Lecture Notes) (2007) | |||||||||||||||
Abstract | |||||||||||||||
| Contents Preface 7 Lecture I. The Stable Marriage and Stable Roommates Problems 8 1. The Stable Marriage Problem 8 1.1. Definition of the Stable Marriage Problem 8 1.2. The Gale-Shapley Algorithm 9 1.3. Correctness 10 1.4. Male Optimality 10 2. Introduction to Network Stability 11 2.1. The Stable Roommates Problem 11 2.2. Network Definitions 11 2.3. The Stable Roommate Problem and Network Stability 13 Lecture II. The Stable Roommates Problem and Network Stability 15 1. The Stable Roommates Problem and X-Network Stability 15 2. Adjacency-Preserving Circuits and X-Networks 16 3. Network Stability and Simplification 16 Lecture III. The Maximum Flow Problem 20 1. Network Flows 20 1.1. Flows and Pseudo-flows 20 1.2. Cuts 20 1.3. Residual Networks 21 1.4. Augmenting Paths 22 2. The Augmenting Path Algorithm 22 CONTENTS 3 3. The Decomposition Theorem 24 4. The Capacity Scaling Algorithm 26 Lecture IV. Th | |||||||||||||||
Details der Publikation | |||||||||||||||
| |||||||||||||||