Global Methods for Combinatorial Isoperimetric Problems
With a focus on global methods, this innovative text employs morphisms to transform new problems into more restricted and easily solvable settings while preserving essential structure.
TABLE OF CONTENTS Global Methods for Combinatorial Isoperimetric Problems
Chapter 2: The Minimum Path Problem
2.1 Introduction
In this section and the next, we present the essentials of the theory of minimum path problems. The minimum path problem is arguably the most fundamental and most frequently applied of all optimization problems. These first two sections constitute background for our introduction of global methods. Readers already familiar with the material may wish to use them for a quick review and reference. The main line of our development resumes in Section 2.3 with the reduction of wirelength to minimum path.
2.1.1 Basic definitions
A network, N = ( G; s, t; ?), consists of a directed graph G = ( V, E, ? + , ? ?) (where ? : E ? V give the head and tail ends, respectively, of each edge) with distinguished vertices s and t, and a weight function ? : E ? 
. A u- ? path, P, in G is a sequence of edges, P = ( e 1 , e 2 , , e k), such that ? ? ( e 1) = x 0 = u, ? + ( e k) = x k = ? and for all i, 1 ? i < k, ? + ( e i) = x i = ? ? ( e i+1) (Fig. 2.1). k, the number...
Copyright Cambridge University Press 2004 under license agreement with Books24x7
