A Simple O ( n 2 )Algorithm for the All-Pairs Shortest Path Problem on an Interval Graph Prakash Mirchandani Katz Graduate School of Business, University of Pittsburgh, Pittsburgh, Pennsylvania 15260 Let G denote an interval graph with n vertices and unit weight edges. In this paper, we present a simple O ( n ‘ ) algorithm for solving the all-pairs shortest path problem on graph G . A recent algorithm for this problem has the same time-complexity but is fairly complicated to describe. However, our algorithm is concise to state, intuitive to understand, and easy to implement. 0 7996 John Wiley & Sons, Inc. 1. INTRODUCTION A n interval graph [ 2 ] is a graph whose vertices have a one-to-one correspondence with unique intervals on the real line such that two vertices in the graph are adjacent to each other if and only if the corresponding intervals intersect. The study of interval graphs is important since we can use them to model applications from many diverse fields such as genetics, traffic engineering, and marketing (see 13, 51). Let G be a connected interval graph, and let n denote the number of vertices of G. Ravi et al. [ 4 ] described an O ( n 2 )algorithm to solve the all-pairs shortest path problem on an interval graph in which each edge has unit length. This bound is the tightest possible since any graph has O ( n 2 )pairs of nodes. Given an interval graph, the authors constructed a corresponding “neighborhood tree” and extensively used the characteristics of this tree to develop and prove the correctness of their algorithm. The neighborhood tree structure is interesting and may prove useful in other problem contexts on the interval graph. However, its construction and use results in a fairly complex algorithm for the all-pairs shortest path problem on interval graphs. Indeed, the neighborhood tree structure is not required for solving the all-pairs shortest path problem on interval graphs. In this communication, we develop a much simpler algorithm for solving the all-pairs shortest path problem on an interval graph G . This algorithm is concise to state, intuitive to understand, and easy to implement. We as- sume that we are given the interval representation of graph G , i.e., we are given I , , u, , i = 1, 2, . . . , n , where I, and u, are the lower and upper endpoints of each of the n intervals corresponding to the n vertices of graph G. We can make this assumption without any loss of generality since given any graph we can check whether it is an interval graph and, if so, construct its interval representation in linear time [ I ] . We refer to the interval defined by I, and u, as vertex interval i. We assume that each vertex interval is open and that no two vertex intervals have a common endpoint [ 21. We reindex the vertex intervals, if necessary, by their lower endpoints, i.e., for two distinct vertex intervals i l and i 2 , i l < i2 if and only if I,, < I,>. Let the index of each vertex of interval graph G equal the index of the corresponding vertex interval. Observe that every path with vertices i l , i z , . . . , i, in the interval graph G corresponds to a “path” through vertex intervals i , , iz, . . . , i, in the interval representation of G. In this representation, every pair of consecutive intervals in the ordered list i l , i z , . . . , i, intersect and the ‘‘length’’ of the path is q - 1 . Thus, we can equivalently denote any path of G by a sequence of nodes or by a sequence of the corresponding intervals. L e t { I , , u , : i = 1 , 2 , . . . , n}bethesetofallendpoints of the vertex intervals with cardinality m + 1. (Note that m 1 = 2n since all I, and u, are distinct.) List all the elements of this set in ascending order. Let each of the m consecutive pairs of this ordered list describe an open interval, which we refer to as an overlap interval. Observe that an overlap interval may be defined by the intersection + NETWORKS, Vol. 27 (1996) 215-217 ic, 1996 John Wiley & Sons, Inc. CCC 0028-3045/96/030215-03 215 216 MIRCHANDANI of 2 or more vertex intervals or may simply be a part of some vertex interval. Let L, and U, f o r j = 1, 2, . . . , m denote the lower and upper endpoints of overlap interval j . Let these intervals be indexed by their lower endpoints, i.e., for two distinct overlap intervals j , and J 2 , j , < J2 if and only if L,, < LJ2.Our procedure for indexing the vertex and overlap intervals implies that L , = I , , U, = LJ+, f o r j = 1 , 2 , . . . , m - 1, and U, = u,. Let a, and b,, respectively, denote the lowest- and highest-indexed vertex intervals that intersect with overlap interval j for j = 1, 2, . . . , m . Given the endpoints of the vertex intervals, we can trivially determine a, and bJf o r j = 1, 2, . . . , m in U ( n 2 )time. Note that for any J , I., 5 [b, < Mu,, Uh,. 2. PROPERTIES OF THE INTERVAL REPRESENTATION We next describe several properties o f the interval representation of graph G. We will use these properties in proving the correctness o f our shortest path algorithm. The validity of these properties relies upon the assumptions that we have made in Section 1 about the interval representation of graph G. Recall that we have assumed that the vertex intervals (each vertex interval corresponds to a unique vertex of G ) are open and that no two vertex intervals have a common endpoint. Furthermore, pairs of adjacent endpoints define the overlap intervals;, 1 I; I m ,and both vertex and overlap intervals are indexed by their lower endpoints. Also, a, and bj, respectively, denote the lowest- and highest-indexed vertex intervals that intersect with overlap interval j . Corollary 2. Let J be the index of any overlap interval such that 1 I j 5 m - 1 . I f b, < b,,,, then b,,, = i * , where i* = { i: U, = L,,, = 1, } . Lemma 3. Let; he the index of any overlap interval. Let i denote the index of any vertex interval such that i < b,. Then, either ( i ) vertex intervals i and b, intersect each other or (ii) a shortest path.fiom vertex interval i to vertex interval b, passes through vertex interval a,. Proof: Suppose that i < bj and vertex intervals i and bJ do not intersect each other. Hence, the shortest path length from i to b, is at least 2. We show that a shortest path from vertex interval i to vertex interval 6, passes through vertex interval aJ by considering two cases: CASE( i ). I, > I, . Since i < b, and vertex intervals i and b, do not intersect each other, 1; < u, < /,. These inequalities together with 1, > [., and lb, < u,,, Ub, imply that I, < 1, < u, < lb, < u,,, ub,. Thus, the path i , aj, b, is a valid path of length 2 from node i to b,. Since the length of the shortest path from i to b, is at least 2, the path i , a,, h, is optimal. CASE ( i i ) . I, < I,,. Let the shortest path from i to b,, denoted by P , consist of vertex intervals i = i , , iz, i 3 , . . . , i,, bJ. Suppose Path P does not contain vertex interval a,. Let index h = argmaxk{ I,, < la,, 1 I k I q }. Observe that i/, < a, since I,, < I,,. Furthermore, a, is the lowest-indexed vertex interval that intersects overlap intervalj. Thus, vertex interval ih does not intersect overlap interval;. Hence, u,, < lbland h < q , i.e., Path P contains some vertex interval between vertex intervals h and 6, and its length is at least h + 1. Next note that I,, < I,, < u,, < ib, < u,,, ub,. Thus, we can construct the path i = i , , i 2 , . . . , ih, a,, b,, which is at most as long as Path P and passes through a,. w I Lemma I . Let J he the index of any overlap interval such ;I m - 1 . Ifb, < b,,,, then a, = a,,,. thai 1 I Prouf Recollect that the endpoints of the overlap intervals are defined by the endpoints of the vertex intervals. Suppose that U, = Lj,, = u,*,for some vertex interval i*, 1 I i* I n . Let Sj+,denote the set of all vertex intervals that intersect overlap interval j 1. Since the endpoints of ~ l vertex l intervals are unique and L,,, is the upper endpoint of vertex interval i*, 1, I LJ and u, 2 U,,, > U, for all i E S,,, . Thus, all vertex intervals in S,,, also intersect overlap interval;, and, hence, bj > b,,, . This contradicts the condition that b, < bj,, stated in Lemma 1 . Consequently, Uj = L,,, = l j * ,for some vertex interval i*, 1 I i* i n . Let Sj denote the set of all vertex intervals that intersect overlap interval j . Since the endpoints of all vertex intervals are unique and U, is the lower endpoint of vertex interval i*, lj I Lj < L,+, and u, 2 U,+, for all i E Sj. Thus, all vertex intervals in Sj also intersect overlap interval j 1. In fact, S,,, = S, U { i* } . Sime lj*> min { 1,: i E S,} and vertex intervals are indexed by their lower endpoints, a, = aj,,. + + , 3. THE ALL-PAIRS SHORTEST PATH ALGORITHM We now describe the all-pairs shortest path algorithm SP. Let d*( x, y ) denote the shortest path length between vertices x and y , and d ( x , y ) denote a valid upper bound on d*( x,y ) identified by Algorithm SP. Algorithm SP initializes the values of d ( x , y ) to ( i ) 0 if x equals y , (ii) 1 if vertex x is adjacent to vertex y , and (iii) n otherwise. The algorithm then recursively updates these values. After the algorithm terminates, d ( x , y ) equals d*( x,y ) for all 11x,y1n. Algorithm SP STEP0. Preprocessing: Determine a, and bJ for all j = 1, 2, . . . , m O ( n 2 ) ALGORITHM FOR ALL-PAIRS SHORTEST PATH PROBLEM Moreover, d ( k , bh+l)= d( bh+l,k ) = d*( bh+,,k ) = d*( k , bh+l). STEP1. Initialization: d ( x , y ) := STEP [ 0, if x equals y ; 1, if x is adjacent to y ; n , otherwise; 2. Recursion: forj := 1, m do begin for i := 1, b, do begin d(b,, i ) := min(d(b,, i ) , 1 + d(a,, i ) ) ; d( i , b,) := d(b,, i ) ; end; end; Lemma 4. After iteration j of the recursion, d ( x , y ) = d*(x, y ) for all 1 I x, y I b,. Proof: We prove this lemma by induction on the number of iterations. The lemma is clearly true after the first iteration. Assume that the lemma is true after iteration h <.j, i.e., d ( x , y ) = d * ( x , y ) for all 1 Ix, y Ibh. We will show, in the induction step, that d ( x , y ) = d*( x , y ) for all 1 Ix , y I bh+l after iteration h 1 . The claim is clearly true if bh 2 bh+,.Hence, consider that hh+ > bh . Therefore, ah+ = ah I bh, where the equality follows from Lemma 1 and the inequality is a consequence ofthe definitions of ah and bl,. Hence, ah+, < bh+l. Now consider vertex k I bh+,.If k = bh+,,then + , Also, d ( k ,bh+i)= d(bh+lrk)= d*(bh+lrk ) = d * ( k ,bh+l). Now assume that k < bh+,.We consider two cases: CASE( i ) . Vertex k is adjacent to vertex bh+l. If vertex k is adjacent to vertex bh+,, Furthermore, d ( k , bh+,)= d(bh+l, k ) = d * ( k , bh+l). 217 = d*(bh+l, k ) CASE( i i ) . Vertex k is not adjacent to vertex bh+l. If vertex k is not adjacent to vertex bh+l, then, by Lemma 3, the shortest path from bh+lto k passes through a,,,, . Since ah+, < bh+,,the induction hypothesis implies that d( k , ah+,)( = d( ah+,, k ) ) is the shortest distance between vertices k and ah+,.Consequently, Theorem 5. Algorithm S P j n d s the optimal solution to the all-pairs shortest path problem on an interval graph with edges of unit length in O ( n 2 )time. Proqf.’ By Lemma 4, Algorithm SP finds the optimal solution to the all-pairs shortest path problem on an interval graph with unit edge lengths. Steps 0 and 1 of the algorithm take O ( n 2 )time each. Also, since m = 2n - I , the running time of Step 2 is O( m n ) = O( n’). Thus, the running time of the algorithm is O( n’). 4. CONCLUSION One question that arises from this work is whether the all-pairs shortest path problem can be solved in O ( n 2 ) time on interval graphs when edge weights do not all equal unity. Observe, however, that complete graphs are interval graphs. Hence. if the arc weights are assigned arbitrarily, then the complexity of any algorithm for the all-pairs shortest path problem on interval graphs cannot be better than the complexity of an algorithm for the all-pairs shortest path problem on general graphs. Many NP-complete problems (e.g., the Hamiltonian circuit problem, the domination and the independent domination problem, and the domatic number problem) on general graphs can be solved in polynomial time when defined on interval graphs. It would be interesting to investigate whether the approach suggested in this article can also be used for solving these problems. REFERENCES K. S. Booth and G. S. Leuker, Testing for the consecutive ones property, interval graphs and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci. 13 ( 1976) 335379. M. C. Golumbic, Algorithmic Graph Theory and Per/& Graphs. Academic Press, New York ( 1980). P. Mirchandani, R. Kohli, and A. Tamir, Capacitated location problems on a straight line. Working Paper ( 1994). Trans. Sci., to appear. R. Ravi, M. V. Marathe, and C. Pandu Rangan, An optimal algorithm to solve the all-pair shortest path problem on interval graphs. Networks 22 (1992) 21-35. F. S. Roberts, Graph Theory and its Applications to Problems ofsociety SIAM Press, Philadelphia ( 1978). Received March 24, 1992 Accepted December 7, 1994

1/--страниц