close

Вход

Забыли?

вход по аккаунту

?

380

код для вставкиСкачать
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
Документ
Категория
Без категории
Просмотров
5
Размер файла
288 Кб
Теги
380
1/--страниц
Пожаловаться на содержимое документа