Path constrained network flows [Elektronische Ressource] / Maren Martens

Path-Constrained Network FlowsDipl.-Math. oec. Maren Martensaus BerlinVom Fachbereich Mathematikder Universita¨t Dortmundzur Erlangung des akademischen GradesDoktor der Naturwissenschaften– Dr. rer. nat. –genehmigte DissertationBerichter: Prof. Dr. Martin SkutellaProf. Dr. Friedrich EisenbrandTag der Disputation: 19. April 2007ContentsIntroduction 11 Preliminaries 71.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.2 Basic Vocabulary and Notation . . . . . . . . . . . . . . . . . 71.3 Network Flows . . . . . . . . . . . . . . . . . . . . . . . . . . 91.3.1 s-t-Flows. . . . . . . . . . . . . . . . . . . . . . . . . . 101.3.2 Minimum Cost Flows . . . . . . . . . . . . . . . . . . . 111.3.3 Multicommodity Flows . . . . . . . . . . . . . . . . . . 121.3.4 Dynamic Flows . . . . . . . . . . . . . . . . . . . . . . 132 Unsplittable Flows 152.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.2 Problem Definition and Notation . . . . . . . . . . . . . . . . 182.3 A Lower Bound for Path-Selecting Algorithms . . . . . . . . . 192.4 Convex Combinations for Multicommodity Flows . . . . . . . 222.4.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . 232.4.2 Constructing the Convex Combination . . . . . . . . . 242.4.3 Analysis of the Construction . . . . . . . . . . . . . . . 282.4.4 Upper Bound for the Congestion . . . . . . . . . . . . 333 k-Splittable Flows 373.1 Introduction . . . . . . . . .