Chapter 6:
Applications of Network Models
 CONTENTS Chapter 1 Chapter 2 Chapter 3 Chapter 4 Chapter 5 Chapter 6 Chapter 7 Chapter 8
 6 Applications of Network Models 6.1 Definition of Terms and Notation 6.2 Travel Distances on Networks 6.2.1 Shortest Paths From a Given Node to All Other Nodes 6.2.2 Shortest Paths Between All Pairs of Nodes 6.2.3 Traffic Assignment Problem 6.2.4 Some Complications for Urban Travel 6.2.5 Complexity of Algorithms 6.3 Minimum-Spanning-Tree Problem 6.3.1 Solving the MST Problem 6.4 Routing Problems 6.4.1 Edge Covering: The Chinese Postman's Problem 6.4.2 Chinese Postman's Problem on an Undirected Graph 6.4.3 Obtaining an Euler Tour 6.4.4 Solving the Chinese Postman's Problem 6.4.5 Node Covering: The Traveling Salesman Problem 6.4.6 Solving TSP1 6.4.7 Euclidean TSP 6.4.8 Probabilistic View of the Traveling Salesman Problem 6.4.9 Multiroue Problems 6.4.10 Multiroute Node Covering 6.4.11 m.TSP Problem 6.4.12 Single.Depot VRP 6.4.13 Multidepot VRP 6.4.14 Multiroute Chinese Postman Problem 6.5 Facility Location Problems 6.5.1 Basic Model 6.5.2 Median Problems 6.5.3 Generalization and Extensions 6.5.4 Center Problems 6.5.5 Multiple Centers 6.5.6 Requirements Problems 6.5.7 Set-Covering Problems 6.5.8 Related Problems 6.6 Probabilistic Networks 6.6.1 Description and Some Properties of Probabilistic Networks 6.6.2 Discrete and Finite State Space for Probabilistic Networks 6.6.3 Facility Locations on Probabilistic Networks *** References *** Problems