UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

On some problems on k-trees and partial k-trees Skorin-Kapov, Darko 1989

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-UBC_1989_A1 S57.pdf [ 4.26MB ]
Metadata
JSON: 831-1.0098333.json
JSON-LD: 831-1.0098333-ld.json
RDF/XML (Pretty): 831-1.0098333-rdf.xml
RDF/JSON: 831-1.0098333-rdf.json
Turtle: 831-1.0098333-turtle.txt
N-Triples: 831-1.0098333-rdf-ntriples.txt
Original Record: 831-1.0098333-source.json
Full Text
831-1.0098333-fulltext.txt
Citation
831-1.0098333.ris

Full Text

ON SOME PROBLEMS ON K-TREES AND PARTIAL K-TREES By D A R K O SKORIN-KAPOV B. Sc The University of Zagreb, Yugoslavia, 1978 M . Sc. The University of Zagreb, Yugoslavia, 1983  A THESIS SUBMITTED IN PARTIAL F U L F I L L M E N T O F T H E REQUIREMENTS FOR T H E D E G R E E O F D O C T O R OF PHILOSOPHY in T H E F A C U L T Y OF G R A D U A T E STUDIES (Department of Commerce and Business Administration)  We accept this thesis as conforming to the required standard  T H E UNIVERSITY O F BRITISH COLUMBIA May 1989 ©  Darko Skorin-Kapov , 1989  In  presenting  this  degree at the  thesis  in  partial fulfilment  of  University of  British Columbia,  I agree  freely available for reference copying  of  department publication  this or  and study.  thesis for scholarly by  of this  his  or  her  M f t C g ^  The University of British Columbia Vancouver, Canada  Date Jt(UA  DE-6 (2/88)  2  0  purposes  , MSl  that the  may be It  thesis for financial gain shall not  C 0 H  requirements  I further agree  representatives.  permission.  Department of  the  that  advanced  Library shall make it  by the  understood be  an  permission for extensive  granted  is  for  allowed  that without  head  of  my  copying  or  my written  ABSTRACT The objective of this thesis is to investigate some structural and algorithmic properties of ktrees and partial k-trees. A k-tree can be constructed from a k-complete graph by recursively adding a new vertex which is adjacent to all vertices of an existing k-complete subgraph. Partial k-trees are graphs embeddable in a k-tree with the same vertex set. They are natural generalizations of forests and series-parallel graphs which are the first two members of the hierarchy of partial k-trees. The many  applications of k-trees and partial k-trees have motivated their study from both  an  algorithmic and a theoretical point of view. For example, k-trees arise in reliable communication network design problems (Farley (1981), Farley and Proskurowski (1982), Neufeld and Colbourn (1983), W a l d and Colbourn (1983), Colbourn and Proskurowski (1984)) and in the study of the complexity of certain type of queries in a relational data base system (Arnborg (1979)). Moreover, the class of k-trees is special in the sense that many problems, which are NP-complete for arbitrary graphs, are solvable in polynomial time when restricted to k-trees or partial k-trees (Arnborg and Proskurowski (1989)). In Chapter 2 of the thesis we analyze a fixed cost spanning forest ( F C S F ) problem, defined over a graph G, in which some customers require service that can be generated at some facilities' sites. Both the set of customers and facilities' sites are represented by nodes in G. There is a fixed cost for opening each facility and a cost for delivering the service from open facilities to the customers. Customers do not necessarily have to receive the service directly from an open facility, but possibly through other intermediate customers. We develop a linear time algorithm for solving the F C S F problem when the customers and potential facilities' sites are located on a series-parallel network or, equivalently, a partial 2-tree. We further analyze a related cost allocation problem, in which we seek a fair method for allocating the cost of providing the service to the customers. We formulate this cost allocation problem as a cooperative game and show that, in general, the core of this cooperative game may be empty. However, we provide a sufficient condition, which can be  verified in polynomial time, for the nonemptiness of the core of this game. A k-tree can be reduced to the k-complete graph by sequentially removing k-degree vertices with completely connected neighbors. We use this reduction process to develop, in Chapter 3, efficient algorithms for several optimization problems on k-trees and partial k-trees.  In particular,  we develop a linear time algorithm to find shortest simple paths from a given vertex to all other vertices in a k-tree, we compute the diameter of a k-tree with equal edge lengths in linear time, and we construct an 0(n ) k+2  algorithm to solve the Simple Plant Location problem in an n-vertex  partial k-tree. In Chapter 4 we present a new characterization of a k-path between two vertices u and v, in an equal weight k-tree G, by means of minimal k and k+1 cliques with respect to certain partial orders defined on the collections of all k and k+l cliques in a k-tree. We use it to develop an algorithm to decompose  0(n ) 2  a vertex set V of a k-tree G to a m i n i m u m number of components, such  that for any pair of vertices i and j in the same component, the cable distance between  i and j is  bounded by a positive integer R. We also compute the k-cable diameter of a k-tree with equal edge lengths in linear time. In Chapter 5 we derive some separation properties of partial k-trees and use them to develop N C algorithms for recognizing partial 2-trees and 3-trees. Explicitly, we prove the existence of a kseparator in a partial k-tree graph and construct a linear time algorithm that finds such a separator in k-trees.  This algorithm can be used to obtain a balanced binary decomposition of a k-tree in  0(n log n) time.  We derive some other separation properties of partial k-trees and use them to  construct a balanced decomposition of an embedding of a k-connected partial k-tree when k = 2 and 3.  Finally, we construct N C algorithms for the recognition of a partial k-tree for k — 2 and 3,  which run in 0(log n) time using, respectively, 0(n ) 2  3  in  and 0 ( n ) processors. 4  Table of Contents ABSTRACT  i i  LIST OF FIGURES  i»  LIST OF TABLES  vii  ACKNOWLEDGEMENT  viii  I  INTRODUCTION  1  1.1 Graph-Theoretic Definitions  2  1.2 Combinatorial Optimization Problems  7  1.3 Special Classes of Graphs  10  1.4 Recognition of k-Trees and Partial k-Trees  :  1.5 Summary of the Results  II  III  13 17  FIXED COST SPANNING FOREST PROBLEM  19  2.1 Preliminaries  20  2.2 A Linear Time Algorithm  23  2.3 The Core of the FCSF Game on Series Parallel Graphs  30  ON SOME OPTIMIZATION PROBLEMS ON K-TREES AND PARTIAL K-TREES  36  3.1 Single Source Shortest Paths Problem in k-Trees  37  3.2 Diameter of a k-Tree  40  3.3 Simple Plant Location (SPL) Problem on Partial k-Trees  42  iv  IV  V  K - C A B L E S A N D K - P A T H S IN K - T R E E S  47  4.1 A n R k-Cable Distance Decomposition Problem  47  4.2 k-Cable Diameter of a k-Tree  56  N C A L G O R I T H M S F O R RECOGNIZING P A R T I A L 2-TREES A N D 3-TREES  60  5.1 k-Separators  61  5.2 Some Separation Properties of Partial k-Trees  66  5.3 N C Algorithms for Recognition of Partial k-Trees for k = 2 and 3  69  5.4 N C Algorithm for Recognizing Partial 3-Trees  72  BIBLIOGRAPHY  80  v  List of Figures Figure 1.1  T w o drawings of the same graph  Figure 1.2  Partial 3-tree G  3 14  Figure 2.1 a:  AnSPM  b:  A binary decomposition tree T of G  Figure 22  21  G  21 32  G = (V, E)  vi  List of Tables  Table 1.1 Upper bound of k for special classes of graphs x  vii  Acknowledgement I would like to express my sincere appreciation to the University of British Columbia and especially to the Faculty of Commerce and Business Administration for their hospitality and financial support given through Dean Earle D . McPhee Memorial Fellowship in Commerce and Business Administration, Leslie G . J . Wong Memorial Fellowship, University of British Columbia Graduate Fellowship and Graduate Travel Grant. M y sincere thanks go to the Division of Management Science for giving me the opportunity to be one of their P h D students. I am deeply indebted to Professor  Daniel Granot, my supervisor, for his guidance,  friendliness, many valuable suggestions and comments and financial support. I would also like to thank the other members of my dissertation committee Dr Richard Anstee, D r Frieda Granot and Dr Maurice Queyranne for their helpful suggestions. Finally, special thanks with love to my wife Jadranka and our daughters Lea and Nina for their patience and understanding.  vm  To my mother Marija Skorin and to my father Dinko Skorin  Mojoj majci Mariji Skorin i mom ocu Dinku Skorinu  ix  Chapter I INTRODUCTION  The objective of this thesis is to investigate some structural and algorithmic properties of ktrees and partial k-trees. k-trees are a generalization of trees, which can be viewed as 1-trees. They can be constructed from the completely connected (complete) graph on addition of vertices, each of which is connected with  k edges to  k vertices by the repeated  k completely connected vertices.  Partial k-trees are partial graphs of k-trees, i.e., graphs obtained by deleting edges from k-trees. They generalize the notion of forests and series-parallel graphs which are respectively, partial 1-trees and partial 2-trees. The study of the class of k-trees and their partial graphs was motivated by some practical questions concerning the reliability of communication networks in the presence of constrained lineand-site failures (Farley (1981) , Farley and Proskurowski (1982) , Neufeld and Colbourn (1983)) . Therein the vertices  V  represent  sites or nodes in the network, and the edges  1  represent  communication lines. Since lines are typically costly, communication between sites is usually not done directly but via other sites. A tree network is an obvious solution. However, for a tree network site and/or line failures are catastrophic. One way to overcome this failures is to increase the connectivity (Hakimi and T a m i n (1973)). Farley (1981) proposed isolated failure immune (IFI) networks which can survive site and line failures as long as they are isolated. He also showed that two-trees are m i n i m u m IFI networks,  (k-fl)-trees are IfcFI networks in which at most k nonisolated  failures are allowed. This, together with the fact that for a fixed  k, k-trees have a number of edges  which is linear in the size of a vertex set (and thus seem to be economical), makes k-trees attractive for use in the design of reliable communication networks. Studies of k-trees and partial k-trees were also motivated in view of their relevance in modelling the complexity of queries in data base systems. Indeed the evaluation of a certain class of conjuctive data base queries was shown to be equivalent to the embedding of an associated graph, obtained from the query syntax, into a (k— 1)tree, for a m i n i m u m k (Arnborg (1979)). Moreover, partial k-trees have arisen in some real world problems. A s an example, the reliability graph of a battle ship, constructed for weapons effect simulations, had several thousand vertices but was found to be a partial 4-tree (Arnborg (1978)). Further, many examples used in the engineering literature of communication networks are usually partial 4-trees and often series-parallel graphs. Finally, the class of k-trees is special in the sense that many problems which are NP-complete for arbitrary graphs, were shown to be solvable in polynomial time when restricted to this class of graphs; see, for example Arnborg and Proskurowski (1989).  The introduction is organized as follows. In Section 1.1 we review some standard graphtheoretic definitions and in Section 1.2 we discuss several well known optimization problems on general graphs. In Section 1.3 we identify some special classes of graphs. In particular we present  2  some known characteristics of partial k-trees and a number of classes of graphs that are subclasses of partial k-trees. Many graph optimization problems, that are NP-hard on general graphs, can be solved in polynomial time when restricted to these special classes of graphs. Section 1.4 is an overview of the known results on the recognition of partial k-trees and their embeddings into k-trees. Finally in Section 1.5 we give a summary of results obtained in this thesis.  1.1 GRAPH-THEORETIC DEFINITIONS  We present below some basic graph theory notation and definitions. For some recommended graph theory books the reader is referred to Harary (1969) and Berge (1985). A undirected graph or simply a graph  G  is defined to be a pair  (V, E) ,  elements called vertices (or sometimes nodes) and unordered pairs of  V,  E  where  V  is a family  is a set  x  2  (e , e ,• • •, e ) l  called edges (or sometimes arcs). If an element  more than once in the family  { v , v , • • •, v } of  2  m  e = (u,v)  n  of elements of of E appears  E , it is called a multiple edge. A n edge of the form (v,v)  is called a  loop. Graphs without multiple edges are called simple. If the edges are ordered pairs, then D = (V, E) , is called a directed graph ( or a digraph). In a directed graph  D = (V,E)  the vertices  u  and  v are called the tail and the head of the  directed edge (u,v) , respectively. (Note that very often for both undirected and directed graphs an edge from a vertex  u  to a vertex  v is denoted by  (u,v)  , even though  {u,v}  would be more  appropriate for undirected graphs. The concepts of a multiple arc, a simple graph and a loop for directed graphs are analogous to those for undirected graphs.  3  Fig. 1.1 Two drawings of the same graph  We shall say that an edge («,v) connects the vertices « and v. The vertices u and v are adjacent if there is an edge connecting  « and v. The edge («,t>) is said to be incident to the  vertices u and v, and conversely. The vertices « and v are called the ends of the edge (u,v) . Commonly, graphs are represented by a drawing i n which vertices are represented by small circles and edges are lines connecting them (see Fig. 1.1). Some representations of graphs that are appropriate for computer implementation  are an  edge list, an incidence matrix and an adjacency matrix. A n edge list simply contains an entry for each edge (u,v) . Representation by edge lists is the most appropriate for the algorithms studied i n the  thesis. In the case of the graph i n F i g 1.1 such a list contains (1,2) , (1,3) , (1,4) ,  (2,3) , (2,4) , (3,4) . Each- row of a vertex-edge incidence matrix is identified with a vertex and each column with an edge. If the vertices are numbered by the index  4  i and edges by the index  k the  incidence matrix of an undirected graph  G , A = (a ) ik  is defined as follows :  1 if vertex i is incident to edge k 0 otherwise  In the case of a directed graph  D  the edge-vertex incidence matrix  A — (a ) ik  is defined as  follows:  ( The adjacency matrix  B = (6,j)  and columns indexed by connecting  +1 if i is a head of a directed edge k — 1 if i is a tail of a directed edge k 0 otherwise  of an undirected graph  G= (V, E)  V and defined as follows : (6 )  = /,  tJ  i and j . So  is a matrix with both rows  where  / is the number of edges  G is simple if and only if its adjacency matrix is a  {0,1}—matrix. In  the case of a directed simple graph D the adjacency matrix B = (6- -) is defined as follows : t  1 if there is a directed edge with a head j and a tail i 0 otherwise  For any vertex  v £ V,  the neighborhood of v in a graph  vertices adjacent to v . The degree of a vertex of a directed graph W  D = (V, E)  is a set of vertices such that  leave  V \ W.  If  W C V,  the set of directed edges in  v is the cardinality of its neighborhood. In the case  we say that the directed edge (u,v) v £ W and  then 6~(W) E  G is defined as the set of all  leaving  w £ W,  then  enters v and leaves  (v,w)  is said to enter  denotes the set of edges in E entering W. We let  5  6~{v)  and  6 (v) +  stand for  u . If  W and to  W and 6 ({x/}) -  6 (W) +  and  6 ({v})  and are called in-degree of v and outdegree of v , respectively.  +  A path in a graph of the form  G = (V,E)  ( v , t , v , e , 0  x  are edges such that  x  e  v_ t  x  0  t  connecting v  t  t  t  «  0  1  =  and v  0  , e , v ) , where v ,  , u,) € .E , for  =  0  are vertices and  t  t.  1, 2  is a sequence  t  W e refer to  v , 0  e , ••• , e x  t  t>  as the  t  Pv v • A path is simple if all its vertices and edges are distimct. If v = v  endpoints of the path then the path  {  2  Pv v (or p(v ,v ))  ,  0  t  0  t  Pv v is called a cycle. A cycle without repeated edges or vertices (except for the 0  t  endpoints) is called a simple cycle. A directed path from  v  Q  to  v  in a digraph D = (V, E) is  t  defined similarly as in the undirected case except that in this case the edges in the path are directed. A graph is connected if any two vertices in it are connected by a path. Connectedness by paths induces an equivalence relation on the vertices. Its classes are called the connected components of the graph. A digraph  D  is called weakly connected if its underlying undirected graph is  connected. D is strongly connected if there is a directed path in  p  uv  for any two vertices u and v  D. A graph  G = (V',E') 1  is a subgraph of G = (V,E)  if V  is the family of all edges of G which have both ends in V , then and denoted by A graph  G'(V')  1  C V and Ef C E. If  1  is said to be induced by  G  G is an embedding of the graph  G  1  if it can be obtained from  G  1  V  1  by addition of some  G = (V, E) is a set of pairwise adjacent vertices of G . If a graph K  is a clique having p vertices we call it the complete graph on p vertices and denote it by K  S  1  . A partial graph of G contains all its vertices and a subset of its edges.  edges. A clique in the graph  subset  E  5 of V is a separator of a graph  p  G = (V, E) if the subgraph G( V \ S) induced by  has two or more connected components. A graph  G = (V, E)  V \  is called k-connected (or  sometimes k-point-connected) if the cardinality of any minimal separator of G is at least k .  6  . A  A contraction of an edge from  in  G = (V, E)  E and identifying the vertices u and v . A graph  can be obtained from results in a graph H  e = (u,v)  is obtained by removing e =  G is contractible to a graph (?' if G '  G by a sequence of edge contractions in  G \ e with the same vertex set as  is a minor of a graph  G.  Edge extraction of  G and the edge family  G if it can be obtained from  (u,v)  e in G  E \ {e} . A graph  G by a finite number of contractions and  edge extraction operations. Let  G  x  =  (^II-^I)  if there exist mappings from  V  t  into  a n (  i  & and  G = (V , E ) 2  0  2  with  2  be any two graphs.  being from  , ti^)) and !^((t) , w )) 2  2  is homeomorphic to  x  2  x  0(w) , and no two paths  2  E , onto a set of paths of G  V , such that for each edge (v,w) G E , the path 2  G  s  n  a  r  e  a  and  G  x  0  \P((v,w)) has ends <9(a) and  vertex except possibly an end of  paths. Let  $ = {5j , S , • • •, S } 2  n  S. The intersection graph of f  be a family of distinct nonempty subsets of S whose union is  is a graph whose vertices are identified with sets in f, with  S  f  and Sj adjacent whenever t ^ j and 5,- D Sj ^ 0. In general, graphs and directed graphs are very useful in representing systems or structures that may be considered as  set of elements, certain pairs of which are related in a specific way.  However, in many applications arising in business, engineering, biological and social sciences, graphs and digraphs are not sufficient to adequately represent the system or structure under study. In such cases, usually numerical values are attached to the vertices and/or edges to represent construction cost, flow capacities, probabilities of destruction and so on, see, for example Ford and Fulkerson (1962). In general, any graph to which such additional structure has been added is called network. For example, a network  G = (V, E)  is a weighted graph such that each edge  7  e 6 E  has a  'length' (weight) weights. Distance  w(e) . For any  u , v £ V,  between two vertices  the length of the path p(u,v) is the sum of its edge  « and  a is defined as the length of the shortest simple  path p(u,v) .  1.2 COMBINATORIAL OPTIMIZATION PROBLEMS  A n instance of an optimization problem is a pair points and  (F,c) ,  where  F  is the set of feasible  c is the cost function, c : F —• R . The problem is to find an f £ F for which c{J)  < c(g) for all g £ F.  1  Such a point /  is called an optimal solution to the given instance or, for  short, an optimal solution. A n optimization problem is a set  J  of instances of an optimization  problem. For example an instance of a minimum spanning tree problem has a given integer  n > 0  and n x n symmetric distance matrix (d j) . The problem is to find a spanning tree, (V, E) on n t  vertices that has minimal total edge length. (By a spanning tree we mean an undirected graph (V, E) with  that is connected and has no cycles.) For this example V = {1,-••,»}} and c:(V,E)^  £  (  l  |  i  )  e  £  d  {j  F = | a l l spanning trees  ( V, E) ,  .  One can naturally divide optimization problems into continuous optimization problems and discrete (combinatorial) optimization problems. In combinatorial problems, we usually look for an object from a finite or possibly infinite set. The challenge in combinatorial optimization is to develop algorithms for which the number of elementary computational steps used to obtain an optimal solution of an instance of the problem is acceptably small. Complexity theory categorizes problems in terms of the form of mathematical functions expressing amounts of computation as a  8  function of instance size. If, for example, some algorithm uses a number of elementary operations that can be expressed as third order polynomial of the problem size, n , we say that the algorithm is order the  n , or simply 0(n ) 3  3  . Generally accepted measure of efficient performance of an algorithm in  realm of combinatorial optimization is that of 'polynomial boundness'. A n algorithm is  considered 'good' if the required number of elementary computational steps to solve an instance of the problem is bounded by a polynomial in the size of the problem. For a given optimization problem a closely related recognition version of the problem can be defined. Given an instance (F,c) of an optimization problem and an integer  L , is there a feasible solution / G F such that  L . The class of recognition problems that can be solved by a polynomial time algorithm P . A recognition problem certificate for  A  is in the class  N P if for a  yes  Clearly  P is contained in  outstanding open problem whether P = N P . It is strongly suspected that B be two recognition problems. It is said that there exists a polynomial time algorithm cost a  (hypothetical) algorithm  reduction of A problem  x  A  for  A  P ^ N P . Let A  and  B i f and only if  that uses several times as a subroutine at unit  B . The algorithm A  and which can be  N P . However it is an  reduces in polynomial time to  .A  is called a polynomial-time  polynomially transforms to another recognition  x , we can construct a string  is a yes instance of A  x  if and only if y  y in polynomial time (in the size of  is a yes instance of  B . A recognition  A € N P is said to be NP-complete if all other problems in N P polynomially transform to  A . Problem A to  -4. for  B . A recognition problem  B if, given any string  x) such that problem  to  S  A  is called  instance x of A , there exists a  x , whose length is bounded by a polynomial in the size of  checked for validity in polynomial time.  c(f) <  is called NP-hard if it can be shown that all problems in N P polynomially reduce  but it is unknown whether  A  belongs to  N P . Problem that is NP-hard is as hard as any  problem in N P . For precise definitions of complexity of an algorithm, P ,  9  N P , NP-completeness  and NP-hardness, see, for example, Papadimitriou and Steiglitz (1982) and  Garey and Johnson  (1979). It has been shown that many NP-hard graph problems become solvable in polynomial time when restricted to special structure graphs. Such special graphs are presented in the next section. Below we list several well-known NP-hard problems (Garey and Johnson (1979) to which we further refer in the sequel.  Shortest Path Problem (allowing negative cycles) G = (V, E) € R. 1  is a weighted graph, such that each edge e £ E has a 'length' (weight)  For a given pair of vertices u , v £ V find the length of a shortest simple path  w(e)  p(u,v).  Longest Path Let  G — (V, E)  be a weighted graph, such that for each edge e £ E,  u , v £ V find the longest simple path  w(e) £ R .  For  and a set of vertices D ,  DC  +  p(u,v).  Steiner Tree Problem Given a connected undirected weighted graph  G = ( V, E)  V ; find a tree T in G , whose vertex set contains D with a m i n i m u m total edge-weight.  M a x i m u m Independent Set For a given graph independent set in a graph edge (u,v)  G — (V,E) G = (V, E)  find the maximum size of an independent set. ( A n is a subset  is not in E.)  10  V  1  C V such that for all u , v £ V , the 1  M i n i m u m Dominating Set For a given graph  G = (V, E) compute the minimum size of a dominating set. ( A set  D  C V is dominating in G if every vertex in V is either in D or it is adjacent to a vertex in D.)  Chromatic Number For a given graph  G = (V, E) compute the size of a smallest set L of colors such that V  can be colored with elements from  L in such a way that no two adjacent vertices have the same  color.  Hamiltonian cycle For a given graph  G = (V, E) , decide whether there exist a simple cycle passing through  every vertex.  Simple Plant Location Problem in a Graph Let each vertex function  G = (V, E) be an undirected weighted graph with v £  V  associate a fixed cost ,  c , v  w(e) > 0  to open a facility ,  for all e € E.  With  and a transportation cost  g ( • ) which is a nondecreasing function of its argument. Each vertex is viewed as both a v  potential facility site as well as a customer. Find a subset of vertices F, F C V,  11  that minimizes :  1.3 SPECIAL CLASSES OF GRAPHS  W e describe bellow several classes of graphs which were extensively studied in the literature and some of which can be viewed as special cases of the class of partial k-tree graphs. Many optimization problems which are  NP-hard for general graphs were shown to be polynomially  solvable when restricted to these classes of graphs. Trees are possibly the simplest class of graphs. Trees are undirected, connected graphs without cycles. Forests are undirected graphs that are acyclic but not necessarily connected. G = (V, E)  is an almost tree with a parameter smaller than or equal to  spanning tree  T  that are not in Let  G,  in each biconnected component of  i f and only if for some  G there are at most  k edges of G  T.  G = (V, E)  be a graph, with  n .  1=  A linear ordering of  G  is a bijective  V —• { 1 ,• • • , n } . A linear ordering / of G is said to have bandwidth k if k =  mapping / : max  of  k  ' ^l f( ) u  ut £  ~ f( ) v  I  • The bandwidth k of  G,  denoted by bandwidth(G), is the minimum  bandwidth of a linear ordering / over all possible orderings of G . Series-Parallel graphs are undirected graphs that can be constructed recursively from its edges by series and parallel compositions. (Definitions of series and parallel compositions are given in chapter II). Planar graphs are those graphs that do not contain K  5  or K  3j3  homeomorphs. (They  can be drawn in the plane in such a way that no two lines representing edges intersect except at a common endpoint.) Outerplanar homemorphic to  K  4  or K  2f3  (or 1-outerplanar) graphs are graphs that do not contain graph  • (Or equivalently they are planar graphs that can be drawn in the  plane in such a way that all their vertices are on the same face.) For  12  k > 2,  a graph is k-  outerplanar i f and only if it is planar and it has a planar embedding such that if all vertices on the exterior face and all adjacent edges are deleted, then the connected components of the remaining graph are all (k— l)-outerplanar. A graph  G = (V, E)  is a Halin graph if it can be obtained by embedding a tree without  vertices of degree 2 in the plane and connecting its leaves by a cycle that crosses none of its edges. G — (V, E)  is a chordal graph if and only if every cycle with length exceeding three has an edge  joining two non-consecutive vertices in the cycle. k-trees can be defined as follows. The fc-clique is a k-tree, and a k-tree of more than  k  vertices can be constructed by adding a new vertex and new edges connecting it to all vertices of some fc-clique of a smaller k-tree. Partial k-trees are partial graphs of k-trees. Many NP-complete problems were solved in polynomial time on trees and forests, using mostly dynamic programming approaches, see, for example, Johnson (1985). Linear time algorithms for finding maximum independent  set and minimum dominating set on almost k-trees were  developed in Corneil and Perl (1984) and Coppersmith and Vishkin (1985). The technique used therein is to subdivide the problem into a collection of subproblems on the biconnected components, and for each of these to use a tree algorithm as a subroutine. The number of such calls vary, depending on the way how the excess edge influence the solution. Monien and Sudborough (1981) use a dynamic programming approach to show that a number of problems on bandwidth restricted graphs have polynomial solutions. Most of the NP-complete problems remain NP-complete when restricted to planar graphs (Johnson (1985)). However, many NP-complete problems can be solved in polynomial time on series parallel graphs. Indeed, Takamizawa et. al. (1982) provide a general approach to characterize a family of NP-complete problems, that are solvable in linear time on two  13  terminal series-parallel graphs. They consider graph properties defined by means of a finite set of graphs which are forbidden configurations in graphs with these properties. Among other problems they solve the maximum independent vertex set problem, the m i n i m u m dominating set problem and the Steiner tree problem. In Bern et. al. (1985) a different general approach was taken for solving combinatorial optimization problems. Namely a general methodology  for constructing linear time  algorithms is developed therein for graphs which are defined by certain rules of composition. Their approach is applicable for a wide range of problems on series-parallel graphs, outerplanar graphs, Halin graphs, and bandwidth-limited graphs. Chordal graphs can be characterized in terms of 'perfect elimination ordering'. That is, a graph  G — (V,E)  and only if there exist an ordering of the vertex set induced subgraph  G( V \ U { Vj : j = 1,  i — 1})  V , say of  with  | V\ = n is a chordal graph if  v , v , • • •, v , such that in the vertex x  2  G, i > 1, v  n  and its adjacent nodes  t  therein form a clique (Golumbic (1980)). A perfect elimination order was used to develop polynomial algorithms for many graph problems that are NP-complete for general inputs (Johnson (1985)). Note that k-trees are chordal graphs ( although not all chordal graphs are k-trees). Arnborg and Proskurowski (1989) have analyzed the complexity of NP-complete problems on partial k-trees, and developed linear time algorithms for the following problems: vertex cover, independent set, dominating set, graph k-colorability, Hamiltonian cycle and network reliability. They have shown that partial k-trees are ^-decomposable graphs. (A graph and only if either it has at most  k + 1 vertices, or there is a separator  G is ^-decomposable if  S of G with at most k  vertices such that each of the connected components of G \ S augmented by S with completely connected vertices is ^-decomposable.) Since the component partial k-trees interact only  through  the separators, solutions to subproblems on the component partial k-trees may be combined to form a solution for the given partial k-tree. Using the ^-decomposable property of partial k-trees Arnborg  14  and Proskurowski (1989) and Corneil and Keil (1987) developed a general algorithm paradigm to solve efficiently some difficult problems on graphs with bounded decomposability.  We note that  since k-trees are chordal graphs these results are related to those obtained by G a v r i l (1972) in which polynomial algorithms were developed  for solving the problems of finding m a x i m u m independent  set, m i n i m u m coloring, maximum clique and m i n i m u m clique covering for chordal graphs. Observe that the class of partial k-trees can be viewed as a unifying framework for some of the special graphs discussed above. Indeed, every graph (in the worst case  G — ( V , E)  is a partial k-tree for some k  k = \V\ — 1 ). Moreover, with many well known classes of graphs one can  associate an upper bound, fcj , such that these classes can be viewed as partial k-trees for some not exceeding k . r  Table 1.1 provides such an upper bound  k^  for several classes of graphs. (A  more detailed overview of these results is presented in Bodlaender (1986).  Class of graphs Trees, forests  1  Almost trees with parameter  k  k +  Graphs with bandwidth at most k  Jb  Series parallel graphs  2  Outerplanar graphs  2  Halin graphs  5  k-outerplanar graphs  3*  chordal graphs with max. clique size k  Table 1.1 Upper bound of k  15  t  k  -  *  for special classes of graphs  1  1  1.4  RECOGNITION OF k-TREES AND PARTIAL k-TREES It is easy to check in linear time whether a given graph  G  is a k-tree by simply removing  successively k-degree vertices (every k-tree has at least two such vertices) and its adjacent edges until the graph  G  becomes empty. Thus if we can reduce a graph  G  to an empty graph by such an  elimination process i t is a k-tree. However the recognition of partial k-trees is much more difficult and the characterization of partial k-trees as decomposable graphs (see Section 1.3) does not seem to provide an efficient algorithm for the recognition of this class of graphs. The separator property is lost in partial k-trees. Namely, in a partial k-tree we may  find a 'small' separator which cannot be  extended to a k-clique in an embedding of this partial k-tree into a k-tree. For example, if we extend the 3-separator  5 =  {s^ , s  graph which contains K  5  2  ,s } 3  of the partial 3-tree  G  in F i g 1.2 to a 3-clique, we obtain a  as a subgraph and thus is not a partial 3-tree.  Fig 1.2  Partial 3-tree  16  G  Therefore, since the various polynomial algorithms which solve NP-hard optimization problems on partial k-trees (like vertex cover, chromatic number or graph reliability) require a suitable embedding of the partial k-tree into a k-tree, efforts are devoted to recognize efficiently partial k-trees and find their embeddings into k-trees. Actually, there are two types of recognition problems. The first one is of finding an embedding, of a partial k-tree into a k-tree and the second problem is of finding the minimal value of  k, for which the given graph is a partial k-tree. This  second recognition problem is important since the above algorithms, though linear in the size of the input, are exponential in k.  For k = 2 and 3 , the recognition and embedding problem has been  solved by finding a set of reductions on graphs such that any graph can be reduced to the empty graph if and only if it is a partial k-tree (see W a l d and Colbourn (1983) for and Proskurowski (1986) for  k = 3 ).  This set of reductions yield  0(n)  k = 2 and Arnborg and  O(nlogn)  time  algorithms for the recognition of partial 2-trees and partial 3-trees, respectively. However, already for the case of  k =  4  there is no easy known generalization of these methods. Arnborg and  Proskurowski (1985) presented an incomplete set of reduction rules for partial k-trees which can be used i n a heuristic decomposition method. They experimented with these heuristics, and for small values of k (up to 7) most of the graphs which they tested were correctly recognized.  Arnborg et. al. (1987) have shown that the problem of finding the smallest number  k  such  that a given graph is a partial k-tree is NP-complete. However, they also presented therein an 0(n ) k+2  time algorithm for the recognition of a partial k-tree when k is fixed. Present research is  directed towards a better polynomial time recognition algorithm. Robertson and Seymour (1986) have proved that there exists an  0(n ) 2  algorithm to recognize partial k-trees. However their result  is not constructive ; only the existence of such an algorithm is demonstrated and no method is provided to construct it.  17  W i t h the increasing use of highly parallel computers, it has become desirable to identify optimization problems that can be solved fast in parallel. In particular, there has been a considerable interest in problems which have parallel algorithms running in time bounded by a polynomial in the logarithm of the size of the input (i.e. , in poly-log time) and using a number of processors polynomial in the input size. Such a problem belong to the class N C (Pippenger (1979)). Some of the reasons for this interest in the class N C are: (i)  N C C P . N C algorithms are more efficient compared to their sequential versions. Further they make use of a 'reasonable' amount of hardware, namely, the processors.  (ii) The class N C is 'robust' under reasonable changes in the underlying machine models of parallel computation. A very basic issue in parallel complexity theory is to find the most appropriate model of a computer. Different models could lead to different computations and the number of steps executed by the same algorithm would be different, depending on the model of machine considered. The basic differences between various models are concerned with how they deal with read and write conflicts of memory access. The widely excepted model of a R A M (Random Access Machine) consists of a readonly input tape, a write-only output tape, a program and a memory (Aho et.al. (1974)). Fortune and Wyllie (1978) proposed the model P R A M  (Parallel Random Access Machine) for parallel  computations, which is an extension of the R A M model. In a P R A M model simultaneous reads are allowed, while simultaneous writes are not. Other models of shared memory parallel machines have been proposed i n the literature, like C R C W  (Concurrent Read Concurrrent Write) P R A M  (Vishkin  (1983)) in which all the processors have access to a common memory and run synchronously and both simultaneous reading as well as writing on common memory locations are allowed. The N C algorithms that we consider in this thesis assume C R C W P R A M model.  18  Edenbrandt (1985) constructed a parallel algorithm for the recognition of chordal graphs that requires  processors and takes  improved his processor bound to  0(n ) 4  O(logn)  time. Chandrasekharan and Iyengar (1986)  . Tseng (1987) constructed an algorithm that recognizes  whether a given 2-connected graph is series-parallel in  0(log n) 3  time using  0(n )  processors.  4  Bodlaender (1988) has constructed an algorithm for the recognition of graphs that have a tree width less than  k (or, equivalently are partial k-trees), which runs in O(logn)  time and uses  0(n ) 3k+4  processors. Thus, parallelism has decreased the running time but is quite inefficient in the use of processors.  1.5 SUMMARY OF THE RESULTS  We provide bellow a summary of the results obtained in the thesis. In chapter II, we analyze the fixed cost spanning forest ( F C S F ) problem , defined over a network set of communities M,  M C V.  G = (V, E)  in which the  D , D C V, require service that can be generated at a set of facilities' sites  There is a fixed cost for opening each facility and a cost for delivering the service  from open facilities to the communities. A n y community receiving the service from an open facility can deliver it to adjacent communities. We develop a linear time algorithm for solving the F C S F problem when the underlying network  G  has a series parallel structure. We further analyze a  related cost allocation problem, in which we seek a fair method for allocating the cost of providing the service to the customers. We formulate this cost allocation problem as a cooperative game and show that, in general, the core of this cooperative game may be empty. However, we provide a sufficient condition, which can be verified in polynomial time, for the nonemptiness of the core of  19  this game. It is well known that a k-tree can be reduced to the k-complete graph by sequentially removing fc-degree vertices with completely connected neighbors. In the third chapter we use this reduction process to develop efficient algorithms for several optimization problems on k-trees and partial k-trees. The complexity of algorithms developed on k-trees and partial k-trees the thesis expressed in terms of number of vertices and  k  is  is assumed throughout to be a fixed constant.  Observe that the number of edges of a k-tree is linear in the number of vertices for a fixed  k . We  develop a linear time algorithm to find shortest simple paths from a given vertex to all other vertices in a k-tree, we compute the diameter (the longest path) and the vertex center of a k-tree with equal edge lengths in linear time and we construct an  0(n ) k+2  algorithm to solve the Simple  Plant Location problem in an n-vertex partial k-tree. In chapter I V we study the notion of k-cable and k-path in a k-tree. The k-cable , C(u,v) , is a collection of k vertex-disjoint paths between vertices  u  and  ti in a ^-connected graph. We  define the length of the k-cable , C(u,v) , as the sum of the lengths of the the k-cable distance between two vertices these two vertices. A k-path subgraphs  KP =  such that  T  {  vertices u and  u and  2  2  3  n  k + 1 complete  , Qn > , starting and ending with a k-clique and  contains exactly two of the distinct k-cliques v in a k-tree  and  v is the length of the shortest k-cable between  is an alternating sequence, KP , of distinct k and  < Q , T , Q >T , • • • , T x  k paths in C(u,v)  Qi_i  and  Q . t  A k-path between  G is induced by all the minimal k-separators of u and  D in  G.  We provide a new characterization of a k-path between two vertices u and v , in an equal weight k-tree  G , in terms of minimal k and k + 1 cliques with respect to certain partial orders defined  on the collections of all k and  k + 1 cliques in  20  G . Further, for an equal weight k-tree  G =  ( V , E) and a positive integer vertex set  R , R > 2k — 1 , we develop an 0(n ) 2  V into a m i n i m u m number of components, V , V , 1  vertices i and j , i ^ j € V* and < = 1 , • • • , / ,  algorithm to decompose the  ••• , V\ such that for any pair of  2  the cable distance between  i and j does not  exceed R . W e also develop in chapter I V an algorithm to compute the k-cable diameter of a k-tree with equal edge lengths in linear time. Finally in chapter V we introduce the notion of a k-separator G = (V, E) . A k-separator is a set of vertices S, into sets  V  a vertex in  x  and V  1  V  2  satisfying :  with a vertex in  (k > 2) of an n-vertex graph  \S\ = k , which induces a partition of  V\ S  (i) | V.-1 < J^J n , i — 1 , 2 , and (ii) no edge in E connects V • We prove the existence of a k-separator for partial k-trees 2  and construct a linear time algorithm for generating such a separator in k-trees. This algorithm can be used to construct a balanced binary decomposition tree of a k-tree in  O(nlogn)  time. We  further derive some other separation properties of partial k-trees which are used to construct a balanced decomposition of an  embedding of a k-connected partial k-tree into a k-tree when  k =  2 , 3 . Finally , we develop parallel algorithms for the recognition of partial k-trees when £ = 2 , 3 . These algorithms require 0(log n) 2  time and use, respectively, 0(n ) 3  21  and  0(n ) 4  processors.  Chapter II FIXED COST SPANNING FOREST PROBLEM  Let edges E.  G = (V, E) The subset  potential facilities' sites.  be a connected undirected network with a set of vertices D ,  D C V ,  is a set of communities and  M ,  V and a set of  M C V , is a set of  Open facilities provide service which is required by the communities, and  any community receiving the service can in turn deliver it to adjacent communities. Each community in  D  is required to be connected, perhaps through other communities, to an open  facility. There is a cost, £ E, i f edge in  D  c > 0 , for opening facility t  i G M and a cost  c((i,j)) =  • > 0 ,  is used to deliver service. The objective is to provide service to the communities  at a m i n i m u m cost. We will refer to the above optimization problem as the Fixed Cost  Spanning Forest ( F C S F ) problem. The F C S F problem is equivalent to the Steiner Tree problem on an augmented network derived from  G by adding a new vertex, denoted by  G  1  o , and joining it to the set of all potential  facilities' sites M . The cost of any newly added edge (O,J) , i <E M , in G  1  is c  oi  = c- . Clearly, (  an optimal solution to the F C S F problem can be produced by finding a minimum cost Steiner tree in  G  1  whose vertex set contains  connected undirected weighted graph  D  1  = D U { o } . For the other direction suppose that a  G = (V,E)  22  and a set of vertices  D , D C V are given and  we want to find a tree T in G , whose vertex set contains D with a minimum total edge weight. To transform this problem to F C S F problem we identify set choose an arbitrary vertex in  D  D with the set of communities and we  and pronounce it a facility site at which a facility can be  established at zero cost. Thus, since the Steiner Tree problem is known to be NP-hard (Garey and Johnson (1979)), in general, so is our F C S F problem. When the underlying network  G — (V,E) is a tree, the augmented network  G  1  =  (V \E') is a series parallel graph without loops or parallel edges or, equivalently, it is a partial two1  tree (Wald and Colbourn (1983)). Therefore, since there exist linear time algorithms for solving the Steiner Tree problem on partial-two trees (see, e.g., W a l d and Colbourn (1983), Prodon et al. (1985), Rardin et al. (1982), Takamizawa et al. (1982)) and  Cornuejols et. al. (1985) one can  employ these algorithms to solve the F C S F problem on a tree network. The main purpose of this chapter is to develop a linear time algorithm for solving the F C S F problem when the network  G = (V, E) is restricted to have a series parallel structure. We further  examine a cost allocation problem associated with the F C S F problem, in which one seeks a fair method for allocating the cost of providing the service among the communities. The rest of the chapter is organized as follows. In Section 2.1 we review standard definitions regarding series-parallel graphs, and in Section 2.2 we develop a linear time algorithm for solving the F C S F problem on a series parallel graph. In Section 2.3 we examine a cost allocation problem associated with the F C S F problem. We formulate this cost allocation problem as a cooperative game and show that, in general, the core of this game may be empty when G is a series parallel network. Nevertheless, we provide a sufficient condition for the nonemptiness of the core of this game, which can be verified in polynomial time.  23  2.1 PRELIMINARIES  This section reviews several standard graph-theoretic concepts to be employed in the sequel. Series-parallel multigraph ( S P M ) is associated with two vertices called terminals and can be constructed recursively as. follows: A single edge is a S P M ; its end vertices are the two terminals. Further, if Q  x  and  Q  2  are S P M s with terminals  i(Qi) , j(Qi)  and  i(Q )  > HQ2) 1 respectively,  2  so are the multigraphs obtained by each of the following compositions.  Series composition Identify a terminal of Q , say j(Qi) , with a terminal of Q , say x  of the new multigraph are i(Qi)  i(Q ) • The terminals  2  2  and j(Q ) • 2  Parallel composition Identify one terminal of  Q , say l  second terminal of Q , j(Qi) , with j(Q )1  2  i(Qi) , with one terminal of  Q  2  , say i(Q2) , and the  The terminals of the new multigraph are the two vertices  where the identifications occur. The above  recursive construction  of a S P M  G  can be represented by a binary  decomposition tree (see, e.g., Valdes et al. (1982)). This is a rooted binary tree T i n which each vertex  Q corresponds to some series-parallel submultigraph of G , denoted by G( Q) , obtained as  follows. Each vertex of  T  that has degree one represents a distinct edge of  G . If  Q  is not a  degree one vertex, then it is either of a series (S) or parallel (P) type. If  Q is a parent of Q  Q  by the respective series or  2  , then  G(Q)  is submultigraph obtained from  parallel composition. In particular, if  Q  G(Q ) 1  is the root of  and  G(Q )  T , G(Q)  2  1  is the multigraph  G.  and  The  construction of a binary decomposition tree of a given S P M can be done in linear time, see, e.g.,  24  Valdes et al. (1982). Figure 2.1 below illustrates a binary decomposition tree of an S P M .  Figure 2.1a: A n S P M G  Figure 2.1b: A binary decomposition tree T of G  A n optimal solution , X* , to the F C S F problem specifies the set of facilities Af, that are opened at the optimum. Each open facility set of communities through a connected network  » , » G Af*, is providing the service to a  T,* = (V,*,£,*) , which can be assumed to be a  tree. The optimal value of the F C S F problem, associated with X* , is given by :  E <+ E c  ieAf*  E ,*c  ieAf* 0',*)e£-  25  Af*, Af* C  The Directed Steiner Tree problem, which is closely related to our F C S F problem, is defined with respect to a directed weighted graph G = (V,E) subset of vertices  D C V , find a directed tree  . Namely, given a vertex  o 6  T in G , rooted away from vertex  V and a  o and whose  vertex set contains D , such that the total edge-weight of T is m i n i m u m .  2.2 A LINEAR TIME ALGORITHM W e develop in this section a linear time algorithm for solving the F C S F problem on an S P M G = (V, E) with a set of communities D , D C V , and a set of facilities' sites simplicity of presentation, we assume that  G does not contain parallel edges. The algorithm starts  by constructing a binary decomposition tree , T , of the underlying S P graph of  Q , except for those corresponding to the leaves of  parallel composition of two subgraphs correspond to vertices  Q  and  1  Q  2  q , q , q , respectively, in 1  2  successor vertices of q in T , and Starting from the leaves of  and T  G . Every vertex q  Q — (VQ,EQ) of G , with terminals  T designates a series parallel subgraph  Each such subgraph  M , M C V. For  Q  2  i(Q) and j(Q) .  T , is either a series or  of G . That is, if the subgraphs T , then  q and l  q  2  Q , Q  1  Q  l  2  are the two immediate  are said to be the sons of Q .  and proceeding towards its root, for each vertex  q of  the algorithm solves certain special cases of the F C S F problem in the corresponding subgraph The solution of these special cases in  , Q  T Q.  Q  is based on solutions of identical cases in the sons of Q ,  and Q , whose composition created  Q , and which were previously obtained by the algorithm.  2  A t the final stage, when graph  q is the root of T, the corresponding subgraph  Q coincides with our SP  G and an optimal solution for the F C S F on G is at hand. The special instances of the F C S F problem that we need to solve are derived from some  26  restrictions we impose on the terminals of the S P subgraphs we encounter. Explicitly, for each subgraph  Q  associated with a vertex  q of the binary decomposition tree  T , we compute the  following optimal values :  II: f(Q,u  ,0),  Q  IV:  V: /(Q,0,i(g)),  /(Q,i(Q),0) ,  VIII:  VII : f(Q, UQ ,j(Q)) , X:  f(Q,i(Q),i(Q))  ,  XI:  f(QJ,v ),  III:  Q  VI : f(Q,u  Q  f(Q,i(Q),v )  ,  Q  IX:  ,v ) Q  ,  f(Q,i(Q),j(Q))  ,  f(Q,j(Q),j(Q))  A l l the above eleven cases can be viewed as combinations of the following three types of optimal values and their symmetric counterparts : /(Q,0, . ) -optimal value of a F C S F problem in Q  when there are no restrictions on the terminal  problem in facility  Q  UQ , UQ G M D VQ , and  seek the optimal value, f(Q,i(Q) i(Q)  n V  Q  f(Q,i{Q),  M'=  i(Q)  at no cost. Thus, for example, in case  Now, let  from the open facility at  Q = (VQ,EQ)  binary decomposition tree  VIII  we  from some facility  VQ , VQ G M'  we seek the optimal value , f(Q, i(Q), i(Q)) , of  Q in which an open facility is available at  is provided to terminal j(Q)  from some  ,VQ) , of the F C S F problem in Q in which a facility is available  M \ {i(Q)} , and in case X  the F C S F problem in  i(Q)  • ) - optimal value of a F C S F problem in Q when  at no cost and the service is provided to terminal j(Q)  where  .) - optimal value of a F C S F  in which it is required that service is delivered to the terminal  a facility can be established at the terminal  at  i(Q) ; /(Q,UQ,  i(Q)  at no cost, and the service  i(Q) .  be any subgraph of  G associated with'the vertex  q of the  T , and assume that for some optimal solution to the F C S F problem in  G vertex v , v G VQ , receives the service from facility  u , u j£ VQ . Then , our algorithm uses  throughout the simple observation that the path which is used to deliver the service from  27  « to v  in this optimal solution must pass through at least one of the terminals  i( Q) or j( Q) of Q .  Recurrence Rules In the first step we find decomposition tree  f(Q,  •, •)  for all  Q  corresponding to the leaves of the  T , for all cases I-XI above. That is, using, for example, complete enumeration  we solve the above eleven cases of F C S F problems restricted to the different edges of G .  Parallel composition Let that  Q  Q  2  Q is derived from  Qi , Q  2  and  j(Qi) = j(Q ) 2  I  and  1  Q  be the sons of Q i and  Q  Q , according to the binary decomposition tree  by parallel composition. Then, we identify the terminals of  2  in accordance with parallel composition, i.e.  and we compute f(Q,  T , such  i(Q) = i(Qi) = i{Q ) i  J(Q) =  2  . , . ) as follows :  f(Q ,0,0)]  /(Q,0,0) = min { [ / ( Q j , 0 , 0 ) +  , [/(^,  2  [f(Qi,KQi)J)  + f{Q ,VQ M, 2  2  \f(QiAQi)AQi))  ,0) +  f(Q , 2  i(Q ),0)] 2  lf(Qn<b,v ) + Ql  /(<32,MQ ))], 2  + /(0 .«g .«g )]. lf(Qi,u J(Qi)) 2  2  Ql  2  f(Q2,KQ ),KQ2))}, +  +  + /(<*W(02).i(C2))],  2  \f(QiAQi)AQi))  ,  f(Q2,u ,J(Q ))}, Q2  2  V(QiAQi)AQi))  +  / ( Q , < Q ) . ^ ) ] . Lf(0i,« ,j(0i)) + /(02,«'(02),«o )]. 2  2  2  gi  2  \J(QiAQi)*« ) + /«?2.«g .i(02))] }• Ql  II  f(Q,« ,9) Q  = min{ [/(Qn^.0)  f(Q2,*q M 3  2  + /(Q ,i(Q ),0)], [ / ( O i , , 0 ) 2  +  2  . [ / ( Q i . ^ . X G i ) ) + /(Q2. «'(<&). «g )] . [/(<?!,%> 2  28  V  + / ( 3  , * ( Q  2  2  ) , . \f(Qu*Qi),v )  +  Ql  f(Q2^Q AQi))]. 2  \f(QiAQi)AQi))  + / ( « 2 . « o , « g ) ] , \f(QiAQi)AQi))  /(«2.«g ,j'(0 ))]>  [/(<&.* AQi)) +  2  2  2  +  2  f(Q2AQ7)AQ2))]  Ql  « ' ( 0 i ) , « ) + f(Q2AQ2)AQ2))\.  \f(QiAQi)AQi))  gi  >  +  f(Q2,<Q ),v )}}. 2  /(Q,0,^g)  analogous to  Q2  II.  / ( Q , i ( Q ) , 0 ) = min { [/(Qi, i ( Q i ) , 0) + / ( Q , i ( Q ) , 0 ) ] , [/(Qj 2  f(Q AQ2)AQ2))],  \f(QiAQi)AQi))  2  ^  2  +  /(Q .«'(%),«g )l.  +  2  2  [/(Qi,i(<?iMQi)) + / ( Q , i ( Q ) , i ( Q ) ) ] , [/(Qi,i(Qi),i(Qi)) + 2  2  2  /(Q ,i(Q MQ ))] }• 2  f(Q,$AQ))  2  2  analogous to I V . >  f(Q,u ,v ) Q  Q  ,v )  = min { [/(Q,,i.^  + / ( Q , i ( Q ) , j ( Q ) ) ] , \f(Qi AQi) AQi)) + 2  Q  2  2  + /( 32. '( 3 ).^ )] i  f(Q , Q ,VQ )],  \f(Qi>* AQi))  \f(QiAQi),v )  + f(Q2,*Q AQ2))],  u  2  2  2  <  Ql  Ql  3  /(<2 ,i(Q MQ ))], [/(0i,f(0i),» ) 2  2  2  g i  \J(QiAQi)AQi))  + f(Q2,*<j AQ2))]. 2  ?  <  2  2  [/(Oi.^.iCOi)) + + /(Q ,;(Q ),y(Q ))], 2  2  \f{QiAQi)AQi))  2  +  /(Q2,«'(02),«Q )]}. 2  f(Q,u ,j(Q)) Q  = min { [ / ( g  1  , « g  i  +  /( 0 , «Q , J'( % ) ) ] } • 2  2  29  /(Q ,*(<? ),./(Q ))] , [ / ( Q i , i « ? i ) , J « ? i ) ) 2  2  2  +  VIII  f(Q,i(Q),v )  analogous to V I I .  IX  f(Q, i( Q), j( Q)) =f(Q  X  f(Q,i(Q),i(Q))  Q  i( Qi), j( Qi)) + f(Q ,«'(Q ),  lt  2  = min { [ / ( ^ , { ( Q J , { ( Q J )  j( Q )).  2  2  + f(Q ,i(Q ),j(Q ))} 2  2  ,  2  [f(Q ),i(Q ),j(Q )) 1  1  1  + /(Oa,«'(%).«(%))] } •  XI  f(Q,j(Q),j(Q))  = min {  [/(QnKQO.KQj)) +  f(Q ,j(Q ),;(Q ))1. 2  2  2  [/(Qi.i(Gi),j(«i)) + / ( Q , . « ? ) , i « ? ) ) ] } • 2  2  2  Series Composition Let  Q and Q be the sons of Q, according to the binary decomposition tree, with t  2  corresponding terminals from  Q  i(Q\) , j(Qi) and i(Q ) , j(Q ) > respectively, such that 2  2  Q is derived  and Q by series composition. Then, the terminals of Q are i(Q) = i(Qi) and j(Q)  x  2  = j(Q ) . (Note that when the composition took place, the terminals  j(Q\) and i{Q ) were  2  identified, i.e., j(Qi) = i(Q )-) 2  We then compute  2  f(Q , . , . ) from values of f(Qi, • , • ) and  /($2' • ' • ) i previously computed, as follows :  I  / ( Q , 0 , 0 ) = min { [ / ( & , 0 ,0) +/(Q2,0,0)] , [ / ( O i J , ^ ) + / ( Q , « ( Q ) , 0)] , 2  [/(Qi,0,i(Qi)) + /(Q ,««j 0)]}. 2  II  f(Q,u ,<H) Q  2>  = min {[/(^,1*^,0) + / ( Q , 0 , 0 ) ] , [ / ( Q i , ^ , ^ ) + 2  /(3 ,*(<? ),0)] , [ / ( G i . t ^ X O i J ) 2  2  30  + /(g,« j ,0)], 2  < 2  2  + / ( Q , « g , 0 ) ] }•  lf(QiJ(Qi)d(Qi))  /(Q,0,fg)  2  2  analagous to I I .  f(Q,*Q)J)  = min | [ / ( < ? ! , i ( + / ( Q , 0 , 0 ) ] , [ / ( Q i , * ( & ) , « 2  / ( Q , * ( Q ) , 0 ) ] , \f(QuKQi)M)) 2  f(Q,®,J(Q))  f(Q,u ,v ) Q  Q  ) +  + f(Q2,"q M  2  [f(Qi,KQi),KQi))  Q i  ,  2  + f(Q ,KQ2)M  } •  2  analogous to I V .  + / ( Q a . M ^ ) ] , [f(Qi, u ^, v J +  = min[[f(Q ,u ,9) 1  Qi  Q  /(Q ,«(<? ),»Q )] - [f(Qi^ ^ ) 2  2  2  Ql  [f(Qi,v J(Qi))  Q  + /(<? ,'(Q M<? ))],  Ql  2  2  2  + f(Q2,«Q ,VQ )},  Ql  2  +  2  /(^2.«Q .WQ )] } • 2  f(Q,u ,j(Q)) Q  2  = min { [ / ( Q i , t i ^ , 0) + f(Q , 0,i( Q ))] , [ / ( G i , » 2  2  /(Q ,j(Q ),;(Q ))], 2  2  Ql  \f(Qi,« AQi))  2  \f(Qi,* ,v )  Ql  +  Ql  AQi)) +  f(Q2,u ,j(Q ))}, Q2  2  + /(Q ,i(Q ),j(Q ))] } .  Q  2  2  2  f(Q, i(Q), ^g) analagous to V I I .  f(QAQ)AQ))  = min { \f{Q ,i{Q ),%) l  l  + / ( Q , 0 , ; ( Q ) ) ] , [f(QiAQi)^ ) 2  2  Ql  \f(QiAQi)AQi))  f(Q2AQ2)AQ2))\>  \f(QiAQi)AQi))  +  /(<?2.«'(02).i(G))],  + /(02,«Q,i(0))], \f(QiAQi)AQJ) 2  31  2  + 2  +  /(<?,XG),;(%))]}• 2  2  x  f(QAQ)AQ))  = f(QiAQi)AQi))  + /(<?,*'(<9MQ)) •  xi  f(Q,j(Q),j(Q))  =  + /(Q .i(Q ),i(Q ))-  2  2  2  2  2  2  Validity of The Algorithm  Lemma 2.2.1 The algorithm solves the F C S F problem on a series-parallel graph.  Proof:  A t each iteration, starting from the leaves, the algorithm solves cases  subgraph  Q associated with a vertex  q in the binary decomposition tree  finite number of iterations we reach the root of series parallel graph  T  T.  I-XI for some Clearly, after a  whose associated subgraph coincides with our  G . T h e n , / ( G , 0 , 0 ) is the optimal value of the F C S F problem on G .  •  Complexity of The Algorithm Lemma 2.2.2 DC  For a S P graph  G = ( V , E) with  V and a set of potential facilities' sites  n vertices (| V\ = n) , a set of communities  M C V , the F C S F problem can be solved in time  which is linear in n .  Proof:  The binary decomposition tree  T can be constructed in linear time (Valdes et al. (1982)).  32  Further , T has  m < 2n — 3 leaves and  (m — 1) vertices which are of degree greater than 1.  The proof then follows since the amount of computation associated with each vertex of T a constant time.  Comment dynamic  requires  •  Berne et al. (1985) have developed a general methodology for constructing linear time programming  algorithms  for  a  certain  class  of graph  optimization problems  on  decomposable graphs. Their methodology is applicable to our F C S F problem on S P graphs, and an algorithm based on this methodology would be similar to the algorithm presented here. Although this chapter has less general scope, it has the advantage that the recurrence rules are determined explicitly which is naturally required for any implementation. Moreover, as is shown in the next section, an optimal solution for the F C S F problem can be employed in order to verify, in polynomial time, whether a sufficient condition for the nonemptiness of the core of a cost allocation game associated with this problem is satisfied.  2.3 THE CORE OF THE FCSF GAME ON SP GRAPHS  We examine in this section a cost allocation problem associated with the F C S F problem, and for this purpose we need first to introduce the following game theoretic definitions and notation. Let 7 V = { 1 , 2 , • • • , * » }  be a finite set of players and let  c : 2 ^ —+ R with  c(0) = 0  be a  characteristic function defined over subsets of N referred to as coalitions. If c(N) designates a cost that has to be shared by all the players then the pair (JV; c) is called a (cost) cooperative game, or simply a game. For x £ R  n  game  (N; c)  satisfies  and  S C N , let z(5) =  i ' ^  x  c o s  * U a  o c a  *i°  n  v e c t  or  a; in a  x(N) = c(N) , and the solution theory of cooperative games is concerned  33  with the selection of a reasonable subset of cost allocation vectors. Central to the solution theory of cooperative games is the concept of solution referred to as the core of a game. The core of a game  (N\ c) consists of all vectors x € R  n  such that  x(S) <  c(S) for all S C N , and x(N) = c( JV) . Observe that the core consists of all allocation vectors x which provide no incentive for any coalition to secede. In general, the core of a game may be empty.  The  cost allocation problem associated with the F C S F problem is concerned with the  allocation of the cost incurred for satisfying the communities' demand for service. W e will formulate this cost allocation problem as a cooperative game and analyze its core. Formally, given a F C S F problem, defined on facilities' sites  G = (V, E)  with a set of communities  M C V , we denote by  FCSFg  FCSFg  c(0) = 0 and for each  and a set of potential  , for S C D , the F C S F problem obtained from  the original problem by simply replacing D by S. is such that  D C V  S C D , c(5)  Then, the pair ( D ; c) , where  c : 2'^' —• R  is the m i n i m u m objective function value of  , is a cooperative game in characteristic function form, to be referred to as the Fixed Cost  Spanning Forest ( F C S F ) game. In general, the F C S F game generalizes several cooperative games studied in the literature which were used to analyze a variety of cost allocation problems. For example, the F C S F game generalizes Littlechild's (1974) airport game and Megiddo's (1978) tree game. When  D = V , the  core of the F C S F game coincides with the core of the minimum cost spanning tree (m.c.s.t.) game (associated with the augmented network G ) , which is known to have a nonempty core, see, e.g., 1  Bird (1976) and D . Granot and G . Huberman (1981). For the case when  D ^  V , D . Granot and  F . Granot (1987) have shown that the core of the F C S F game is not empty provided that tree structure. Unfortunately, this result cannot be extended to cases when  G has a  G has a more general  structure than a tree. Indeed, we provide below an example demonstrating that the core of a F C S F  34  game defined over a graph consisting of a simple cycle may be empty. Explicitly, consider the network  G = (V, E)  {1,2,3,4,5,6},  E=  communities and  M = {4,5,6}  = 1 for all  G E and that c — \ for all i £  shown in Figure 2.2 below. Therein,  {(1,4), (4,2), (2,5), (5,3), (3,6), (6,1)},  D = { 1 , 2 , 3 } - is the set of  is the set of possible facilities' sites. Further, we assume that M.  {  The core, C , of the F C S F game associated with G is given by:  C = { x € R: 3  x + x 2  3  «i < 2 , x  < 2, x  2  < 3 , x + x x  V =  2  + x  3  3  < 2 , x + x x  2  < 3 , x + x  = 5 } .  Figure 2.2  35  G = (V,E)  Y  3  < 3,  c~  Now, one can easily verify that the core constraints induced by the three two-members coalitions imply that  + x  + x  2  3  < 4ij for any core allocation. Thus, since any core allocation x must  distribute the entire cost, i.e., associated with  x  1  + x  2  + x  3  = 5 , we conclude that the core of the F C S F game  G , displayed in Figure 2.2 , is empty.  The proof of the nonemptiness of the core of a F C S F game when  G is a tree, provided by  D . Granot and F . Granot (1987), employs the polyhedral characterization of the Directed Steiner Tree problem in series-parallel graphs given by Prodon et al. (1985). T o describe this polyhedral characterization, as applied to our F C S F problem, we first need to replace the graph with the directed graph directed edges  G — (V ,E)  <i,j>  and  <j,i>  in which all undirected edges  , with associated costs  = c- . Then, we construct the augmented network V c . t  the vertex  o , and to E  W e will refer to  G  1  the directed edges <o,i>  1  1  1  = c(<j,i>)  = c~  derived from G by adding to  for all t G M , with  as the directed augmented network derived from  a m i n i m u m cost directed Steiner tree in • G  are replaced by two  c» = c(<i,j>)  G = (V ,E*)  G = (V, E)  which is rooted away from  c • = c(< o,i>)  =  G . Note that finding o and whose vertex set  contains D , is equivalent to solving the F C S F problem in G . Further, we need the following notation; for a directed edge / = <i,j> the tail and  j  as a head of / , and for a subset of vertices  directed edges having their heads, but not their tails, in S. admissible cut-set of G , if » ^ 5 C V 1  subgraphs  G '(5) and  We denote by A^,  G'(V\  1  S we denote by  we refer to 8(S)  i as  the set of all  A subset S , S C V , is said to be an 1  , S D D ^ 0 (D is the set of communities) and both  S) of G' induced by S and  V \ S , respectively, are connected.  the set of all admissible cut-sets of G . 1  It follows from Prodon et al. (1985) that if the directed augmented network  G  parallel graph, then the incidence vector of a minimum cost directed Steiner tree of  G  36  1  1  is a series , directed  away from vertex  o and whose vertex set contains  Q U {0} , for any  Q C D , is an optimal  solution of the linear programming problem, LP( Q) , defined as follows:  LP(Q) : min  lex:  x(6(S))  >l,SeA.,,SnQ^®,x>o\  (2.1)  In fact, in view of favorable computational results obtained by Prodon et al. (1985) with instances of the Directed Steiner Tree problem on more general graphs than two-trees, they were led to conjecture that the inequalities describing the polyhedron of the Directed Steiner Tree problem on two-trees (i.e. , the feasible region of  LP(D))  , while not sufficient to describe that polyhedron for  the Directed Steiner Tree problem on more general graphs than two-trees, are nevertheless important in the sense that they often produce optimal integer extreme points. However, notwithstanding this favorable computational experience,  LP(D) would fail to produce optimal directed Steiner trees  even for the very special case in which  is a partial two-tree. Indeed, let the underlying network  G  G be the simple cycle in Figure 2.2 and consider the directed augmented network G . A l l the edge weights in  are assumed to be  G  1  minimum cost directed Steiner tree in  G  1  , with root  E  0 , 1 , 2 ,3 , has a weight of 5 . However x* 6 R  +  X* - i (0,4) 2' _  i 2 •  *(*5,2)  x* (5,3) -  1  X* (6,1)  2 •  x* , = 0  defined as follows:  x* - i (0,6) ~~ 2 '  X* = (4,2)  derived from  0 and whose vertex set contains vertices  i 2 •  1  1  Then, it is easy to check that the  X* (0,5) -  X* = (4,1)  2'  1.  G  -  2  1  '  =  3'  X* ' i (6,3) 2'  otherwise ,  is feasible to LP(D) associated with  G'  and has a lower objective function value of 4.5 .  37  Nevertheless, LP(D)  Proposition 2.3.1  is still useful for the analysis of the F C S F game. Indeed,  If the incidence vector of a m i n i m u m cost directed Steiner tree in the directed  augmented network  G' , rooted away from  o and whose vertex set contains  D , is an optimal  solution to LP(D) , then the core of the associated F C S F game is not empty.  Proof: game  Let  c(Q)  (D;c)  with  formulation of  denote the optimal value of  LP(Q) , Q C D , and consider the cooperative  c(0) = 0 . Then, (2.1) provides us with a generalized linear production game  (D;c)  , see D . Granot (1986). Further, one can easily verify that the sufficient  conditions given therein for the nonemptiness of the core of a generalized linear production game are always satisfied for (£>;£), implying that the core of (D;c) each  Q C D , let c(Q)  is not empty. O n the other hand, for  denote the optimal value of the integer programming problem, IP(Q) ,  derived from  LP(Q)  Observe that  c( Q) coincides with the characteristic function value assigned to  F C S F game. Clearly, G  1  by restricting the nonnegative decision variables therein to  Q , Q C D , in the  c(D) = c(D) .  o and whose vertex set contains  D U {o} , solves  LP(D) , we  Thus, in this case the core of ( D ; c) is a subset of the core of (D; c)  and the nonemptiness of the core of the F C S F game then follows since the core of (D;c) empty.  values.  c(Q) < c(Q) , Q C D . Moreover, whenever a m i n i m u m cost Steiner Tree in  , directed away from vertex  have that  0 —1  is never  •  Moreover, when the underlying network has a series-parallel structure, we can test in polynomial time whether the sufficient condition for the nonemptiness of the core of the F C S F game, given by Proposition 2.3.1, is satisfied. Explicitly, we first find a m i n i m u m cost Steiner tree  38  T , using the algorithm developed in Section 2.2 . Then, we can apply the Prodon et al. (1985) to check if the incidence vector of will be true if and only if the  T-guided algorithm of  T is an optimal solution to  LP(D) . This  T-guided algorithm terminates with a dual feasible solution whose  corresponding objective function value is equal to the weight of T.  39  Chapter III ON SOME OPTIMIZATION PROBLEMS ON k-TREES AND PARTIAL k-TREES  The recursive definition of k-trees implies that a k-tree has at least two vertices, called leaves, of degree k , with completely connected neighbors. denoted by  Adj(v) , and we let  by removing a k-leaf  v  K  v  The neighborhood of a k-leaf  v  is  denote the k-clique induced by it. Clearly the graph obtained  and its incident edges from a k-tree is a k-tree itself.  This defines a  reduction process for k-trees, and such a reduction process is complete when it ends up with some kclique, R , the root of the reduction process. A reduction sequence can be thought of as giving an orientation to a k-tree (Arnborg and Proskurowski (1986)) where vertices are made descendants of kcliques. Namely, if i f is a k-clique, then v is a descendant of K in a given reduction sequence if and only if when  v  was removed, each vertex of  Adj(v)  was either a member of  K  or a  descendant of it. k-trees are also known to have the following separation property (Rose (1974)): every minimal separator of a k-tree consists of k completely connected vertices. In this chapter we will use the notion of the reduction process and the separation property to construct, for a fixed  k, efficient algorithms for several optimization problems on k-trees and  40  partial k-trees.  In particular, in Section 3.1 we follow the reduction process to construct a linear  time algorithm that finds shortest simple paths from a given vertex to all other vertices in a weighted k-tree having nonnegative edge weights, and in Section 3.2 we use a similar approach to compute the diameter (longest path) and the vertex center of a k-tree with equal edge lengths in linear time. Finally in Section 3.3 we construct an  0(n ) k+2  time algorithm for solving the Simple  Plant Location ( S P L ) problem in weighted partial k-tree graphs, which generalizes Hassin and Tamir's (1986)  0(n ) 4  time algorithm for solving the S P L problem on series parallel graphs (i.e.  partial two trees).  3.1 Single Source Shortest Paths Problem in k-trees  Let  G = ( V , E) be a weighted k-tree with | V | = n , such that each (directed) edge e in  E has a "length" (weight) w(e) > 0 .  For each pair of vertices u and  v in V define d(u,v) to  be the length of a shortest simple directed path from u to v . Given a vertex s in V,  we wish to  find the distances from s to all other vertices v in V, as well as distances from all v E V to s . This problem is recognized as the Single Source Shortest Path Problem (SSSP) problem, and we demonstrate below that it is solvable in linear time for k-trees with nonnegative edge weights. For simplicity of presentation, we will only be concerned with the shortest paths from vertices  v E Let  s to all other  V. v  obtained from  be a k-leaf of  G = (V,E) and denote by  G by removing v and its incident edges from  G  1  = (V ,E?) 1  the weighted graph  G and whose edge weights, w'(e) ,  e E E' , have been modified as follows :  min { w((i,j)) , w((i,v)) + w((v,j)) } for i,j E Adj(v) (3.1) w((i,f))  otherwise 41  Further, let d(i,j) denote the length of a shortest simple directed path from node i to j in G .  d'(i,j) =  L e m m a 3.1.1  Let i, j £ V  Proof: where and  d(i,j)  for all  i,j€  V. 1  d'(i,j) = w\p[j ) < d(i,j) = w(p -),  and assume, on the contrary, that  1  i  » to j in G  p ~ and p - are shortest directed simple paths from 1  $J  w'(p' ••) and y  w(p--) are their corresponding lengths. Let y  w((u,w)) }. Clearly |^41 > 1 . If \A\ = 1 then replacing (u,w) in p'^- by (u,v) and which  =  have that  |^4| > 2 .  < Let  1  A = { (u,w) £ p •• : w'((u,w)) < ' 1  A = {(u,w)} for some u,w G Adj(v) .  Then, by  p" -  in G for  we obtain the simple directed path  (Pij) i contradicting the optimality of  w  ( t t j , a n d  (u «w ) 2  G , respectively,  and  2  p^-  in  A , such that  be in  G . So, we must and  K  2  are not  necessarily distinct. Then, upon replacing (MI,WI) and (« , iu ) by («i,v) , (f, Wi) and (« , a) , 2  (t), w ) in p' -j , we obtain a directed path (not simple) 2  Clearly,  pj'-  2  2  p"- in G such that  contains a cycle, C, in G which contains node  w(p" ) < w(p-j) .  v . Since we assumed that  nonnegative edge weights, upon the removal of C from p"- we will obtain a simple path G  satisfying  complete.  wCp ••) < y  u> (?,•„•) y  This contradicts the optimality of  p.- , y  G has p-  in  and the proof is  •  Lemma 3.1.1 can be used to construct a linear time algorithm to find shortest paths from some designated source node s , in a k-tree G = (V, E) , to all other vertices in G .  An algorithm for solving the SSSP problem in k-trees The algorithm has two phases. Phase 1  W e successively eliminate k-leaves and their incident edges from  weights of the remaining edges using (3.1).  G while modifying the  Since a k-tree has at least two leaves, we can always  42  avoid the elimination of the source node s . obtain a subgraph  G  = (V ,E )  k  k  simplicity, we will assume that  The elimination of the k-leaves is continued until we  of G , whose number of vertices is just a function of k.  k  | V * | = k, which can be achieved by letting G  k  For  be a k-complete  graph containing node s . Next, we solve the SSSP problem in  G , whose edge weights were derived by successively k  modifying the edge weights using (3.1). This can be done in 0(k )  elementary operations, which is  2  constant for a fixed G. k  k.  Let  B y Lemma 3.1,  d(s,u) , u G V*, be the weight of a shortest path from  d(s,u) = d(s,u) for all M G V*, where  s to  u in  d(s,u) is the weight of a shortest  path from s to u in G .  Phase 2  Let v be the last k-leaf to be eliminated at Phase 1, and consider the k-tree graph  obtained by adding  v and all its incident edges  same edge weights,  w(i,j) , as it had in Phase 1. Now, if d(s,v)  from  s  to  v  in  G  k  then  d(s,v) =  Lemma 3.1.1, d(s,v) = d(s,v) and  (v,u) , u G Adj(v) , to  G*. Let  G  k  G  k  have the  is the weight of a shortest path  min { d(s,u) + w(u,v) , u G Adj(v) } .  Moreover, by  d(s,u) = d(s,u) for u G Adj(v) , which implies  d(s,v) = min {d(s,u) + w(u,v), u G Adj(v) }.  (3-2)  Thus, by successively adding k-leaves in the reverse order to which they were eliminated in Phase 1, and by calculating the weights of shortest paths using (3.2) we solve the SSSP problem in G.  •  The linear complexity of the above algorithm follows from the fact that in Phase 1 we have at most  n — k  steps and that each recursive equation used either in Phase 1, to modify the  weights, or in Phase 2, to calculate weights of shortest paths, can be computed in constant time.  43  3.2 Diameter of a k-Tree  Let  G = (V, E)  max{d(u,v)  be an undirected graph.  : v £ 7 } . The diameter of  will compute the diameter of a k-tree  G is D = mar { ecc(«) : u £ V } . In this section we  G — (V,E)  The algorithm consists of two phases. of the k-tree.  Initially, we set  The eccentricity of u , u £ V, is ecc («) =  with equal edge lengths in linear time.  In the first phase we will follow a reduction process  ecc (a) = 1 for all u £ V(K) K  and  family of all k-cliques in G (|3G| = (n — k) k + 1 , n > k) , V(K) K  and  ecc («) is the eccentricity of u £ V(K) K  K £ 3G , where  3G is the  is the vertex set of the k-clique  in the subgraph of G induced by  V(K) and all  the descendant vertices of K in the reduction process followed by the algorithm. Let  K , where  V(K )  v  neighbors of a k-leaf  V  = Adj(v) =  t>, and for each  {%,•••,%},  £ Adj(v)  let  K j  denote the k-clique induced by the designate the side k-clique induced by  {v} U Adj(v) \ {uj} . Before a k-leaf node is being eliminated by the reduction process we store, for K  later purposes, the current eccentricities, ecc (u) = ecc (u) , of all vertices v  v  u £ Adj(v) .  After  the elimination of o , we compute the eccentricities of vertices Uj , Uj £ Adj (u) , restricted to the subgraph of the k-tree  G induced by Adj (v) U {v} and the descendant vertices of all side k-cliques  K j as follows : ecc (uA v  = max { max ifr  3  and we update ecc (u) Kv  K.  ecc '(«,-) ,  K-  min  J  i£V(X.)  3  ecc (x) + 1 }  (3-3)  , for all u £ V(K ) , V  ecc {u) Kv  = max { ecc (u) , ecc (u) v  44  I<v  }  (3.4)  Clearly, in the last step of the first phase we have  ecc (u) R  = ecc ( « ) , « €  V(R) , where  R is the k-clique which is the root of the reduction process. Next, for u G V(K) , K G 3G , we denote by ecc^(u) of the k-tree  G induced by  in the reduction process. ecc^(w) = 0 , for all order.  V(K)  and the complement of the set of the descendant vertices of K  In the second phase we initially set u G V(K)  the eccentricity of u in the subgraph  and  A t each step we add a vertex  D — max {ecc(u) : M G V(R) } and  K G 96 , and follow the reduction process in the reverse  v, compute the exact eccentricity of v in  G, ecc(v) , and  update D as follows :  ecc(u) =  max {  max  ecc  (v)  ,  3  min  ueAdj(v)  (3.5)  ecc (u) + 1 , v  and (3.6)  D = max { D , ecc(u) }.  We further update other eccentricities in the following manner:  min  ecc *(x) + 1 } ,  (3.7)  and for j = 1 , ..., k ,  ecc \v) J  = max {  min  uCAdj(v)  ecc (u) + 1 , v  and finally  45  (3.8)  ecc (u) = max { ecc^(u) v  , ecc"(«) , u G Adj(v) } .  (3.9)  Clearly, at the end of the second phase we have computed the diameter, D , of the k-tree G . Since the reduction process has ( n — k) time required to compute Remark  steps and each step requires a constant time, the total  D is 0(n) .  Since we compute in the above algorithm the eccentricities of all vertices in  V,  it follows that we can also find in linear time a vertex with the smallest eccentricity. Such a vertex is called a vertex center of G .  46  3.3 Simple Plant Location (SPL) Problem on Partial k-Trees  Let  G = (V, E) be an undirected weighted graph, with \V\ = n , in which each edge e, e  £ E, is assumed to have a length w(e) > 0 . Further, each vertex D in fixed cost, c , to open a facility at v  v , and a transportation cost function gv(d(v , . )) which is a  nondecreasing function of the distance,  d(v, . ) , from node  potential facility site as well as a customer. defined with respect to  V is associated with a  v. Each vertex is viewed as both a  The Simple Plant Location (SPL) problem problem,  G , is concerned with the location of facilities at vertices in  G so as to  minimize the sum of the set up costs and the transportation costs. Formally, the S P L problem seeks a subset of vertices F , F C V , that minimizes + X)  veV  9v(d(v,F))  , where  d(v,F)  = min  d(v,f) .  «  For general graphs, the S P L problem is  known to be NP-hard. However, Kolen and T a m i r (1986) developed an  0(n ) 2  time algorithm to  solve the S P L problem on tree networks and Hassin and T a m i r (1986) constructed an algorithm to solve this problem on series-parallel graphs.  c  veF  0(n )  time  4  The purpose of this section is to develop  an algorithm that solves the S P L problem on a partial k-tree graph in  0(n* ) +2  elementary  operations. Thus, for a fixed k our algorithm is polynomial in the number of vertices, n , of G . Observe that the embedding of a partial k-tree into a k-tree, for a fixed 0(n ) k+2  k , can be done in  time, as shown by Arnborg et al. (1987). Therefore, since the addition of edges with infinite  length would not affect the solution to the S P L problem, we will assume in the sequel that the partial k-tree graph has been completed into a k-tree. Our algorithm follows a reduction process of a k-tree  G . Accordingly, let K be some k-clique with a vertex set  will denote by h(K, f , f ,• • •, f ) x  G(D(K) U V(Kj)  of  2  k  V(K) = { «j , u ,• • •, u } . 2  k  We  the optimal value of the S P L problem restricted to the subgraph  G, induced by  V(K)  and all the descendants of the k-clique K  reduction process followed by the algorithm, with the stipulation that  47  in the  « . is served by /,• for i = f  1 , 2 , • • •, k , and where /,• can be any node in G . Thus, the optimal value of the S P L problem on G  is given by  min { h(R , / , f t  2  ,• • •, f  ) : A € V, i = 1 , 2  k  k } , where  .R is the root of  the reduction process followed by our algorithm.  An algorithm for solving the SPL problem on a k-tree  Suppose that  v  is the k-leaf which is currently being eliminated in the reduction process  followed by the algorithm.  Let  whose vertex set is  = Adj(v) U {v} \ {uj} , j = 1  V(Kj)  Adj(v) — { « ! , • • • ) « * }  and denote by k.  Kj  Let K  v  the 'side' k-clique  be the k-clique whose  node set is Adj(v) . For  any side k-clique  the optimal values { h r'h } 1  t  n  e  n  °d  h(Kj e  s e t  K j , which was not previously considered, the algorithm first finds  , fa ,-••,/*) °f  V(K j) >  t  for all n  V,  ii = 1 ,• • •, k .  it is easy to verify that for all (/j ,• • •, f ) , /,• 6 V , « =  n  k  ;  i f e  j  f  {  ,A  f) k  is the facility serving  (A > A? >'••)/*)  k  k'  =«=iE /, + «E=i 9 WiJi)) c  j , { // ,• • •, f' , } t  k  E i=i  -  Si  r'.(^') - !) '  is the set of all distinct  v  h(Kj  ,  fa  h(K  v  , f\ >•, AO »  c  a  n  /,'s  ;  (Ai'iA)  We will say that  48  r  10  appearing in  , / ,• • •, /j.) . 2  . A s it will be shown, the  expressed in terms of the optimal  D e  A) i associated with the side k-cliques K - , j = 1  introduce some notation.  3  '  > and <(//) denotes the number of instances that / / appears in (f  optimal value of the S P L problem,  (- )  c  Next, we solve the S P L problem associated with the k-clique K  values,  In fact, if we denote by  k , and side k-clique, K - , not previously considered  h(K  where  e  /,• €  is  a  k.  First, we need to  facility assigment for vertices  { ' i >•••> k } if node  lj receives the service from facility f.,j=  be a facility assignment for 1  fc.  Adj(v) = { « ! , - • • ,  Then, the facility assignment  F to  1  } , and let  Adj(v)  r.  Let F = (A  A)  V(K •) fl .Adj(i>) , j  V• =  Fj  induces a facility assignment  to  =  Vj ,  specifying for each node in V(K j) , except node i>, the facility providing service to it.  F =  Then, one can verify that for any facility assignment { "1  (A »"••»/*)  to  Adj(v)  =  «* } ,  ,  / ) = min j  A(/f, , A  t  h(K  v  ,A  t  f)  + £  k  j  , (*i - «)) ~  j=i  (k-1)  g (d(v,s))  -  v  dS^k-l)  j=i  + 6) 2  -  «=i A' (3.11)  + (l-«,,-)(*-2))] - ( l - * ) [ E (*-l) 4  3  i=i  M («../.)) + E /;- (*4,i * + rf  c  i=i  '  (*-!))]:« e (jDiKA U { « } U { /  1  ,-,/*}},  i=i  where 6 = 1 if s ^ { A' >'"•> X  and  <(/,') =  } and  1 and zero otherwise;  6  z e r o  3  otherwise and  = 1  if  f5 = 1 if s = / ' G { / / , • • •, f i } 2  A(if« , A i " " » / * ) = 0  previously encountered by the algorithm) and zero otherwise , 6 otherwise,  i G {1  , k' } .  Further,  ( F - , s)  49  k  4 i  (i.e . if,,  was not  = 1 if <(// ) > 1 and zero  is the facility assignment to  V(Kj)  which  consists of the facility assignment and  v is supplied from  Fj to  s . The set  V • , induced by the facility assignment  { {[ , •• •, f^, } and  F to Adj(v) ,  <(/' ) , i = 1 , • • •, k  have the same  f  meaning as in (3.10), and D(K) denotes the set of descendant vertices of the k-clique The algorithm will terminate after h(R) , given by h(R) — min { h(R , f\  K.  n — k steps with an optimal value to the S P L problem, , fa) fa € V, i = 1 , • • •, k } , where  R is the root of  the reduction process followed by the algorithm.  Proposition 3.3.1  The above algorithm solves the S P L problem on a partial k-tree graph in  0(n )  elementary operations.  Proof:  The embedding of a partial k-tree into a k-tree requires  k+2  of distances between all pairs of vertices requires  0(n ) 2  0(n )  time. The computation  k+2  time, using the algorithm developed in  Section 3.1. W e assume that the computation of g (d(v,x)) , for a given x , requires constant time. v  Further, in each step of the algorithm we need, in the worst case, h(Kj,---  0(n ) k+1  time to compute  h(K  v  time to compute  ) using (3.11). Hence, the total time to  solve the S P L problem on a partial k-tree is bounded by 0(n ) k+2  k+l  k  ) , using (3.10), for all side k-cliques that were not previously considered by the  algorithm. It takes  0{n ))  0(kn )  = 0(n ) k+2  .  •  50  + 0(n ) 2  + (n — k) (0(kn ) k  +  Chapter IV k-CABLES AND k-PATHS IN k-TREES  In this chapter we study the notion of k-path and k-cable in a k-tree. In Section 4.1 we present a new characterization of a k-path in k-trees and develop an 0 ( n ) 2  algorithm for solving an  R k-cable decomposition problem of a k-tree. In Section 4.2 we construct a linear time algorithm for finding the k-cable diameter (i.e. length of a longest k-cable) in a k-tree having equal edge weights.  4.1 An R k-cable Distance Decomposition Problem  Let  G = (V, E)  be a k-tree and  R  a positive integer,  R > 2 k — 1 . We are seeking in  this section a decomposition of  V to a minimum number of components,  that for any pair of vertices  and  defined below, between  i  i and  ;  j ,  i, j € V* and  does not exceed  1  V , •••, V ' , such 2  t = 1 , • • • , / , the cable distance, to be  R . W e will refer to this problem as the R k-  cable distance decomposition problem. We develop in this section an  51  V,  0(n ) 2  time algorithm for  finding such a decomposition in the special case when  G is a k-tree in which a l l the edge weights  are equal to one. First, we need to introduce some new definitions and notation. The k-cable, denotes a collection of k vertex-disjoint paths between vertices The length  1  of the k-cable  C(u,v) , W(C(u,v))  C(u,v) . The k-cable distance,  c  c  C(«,D) is the collection of all k-cables between  « and v i n a k-connected graph.  , is the sum of the distances of the k paths in  d (u,v) , between vertices  cable between these two vertices. That is, d (u,v)  C(u,v) ,  u and v is the length of a shortest k-  = min { W(C(u, v)) : C(u,v) G C(u,u) } , where  u and v .  Apparently, the notion of a k-path, introduced and studied by Proskurowski (1984), plays a major role i n the analysis of our decomposition problem.  Definition 4.1.1 and  (Proskurowski (1984)).  k + 1 complete subgraphs  with a k-clique and such that and  A k-path is an alternating sequence,  KP = < Q , T , Q , T , • • •, T r  T  {  2  2  3  n  KP , of distinct k  , Q > , starting and ending n  contains exactly two of the distinct k-complete subgraphs  Q  i l  Q . {  It was shown by Proskurowski (1984) that i n a k-tree  G , the vertices of the minimal  subgraphs separating two nonadjacent vertices induce a k-path.  Proposition 4.1.1  1  The k-cable distance between two nonadjacent vertices  Proskurowski (1984) defined the length of a k-cable,  u and v i n a k-tree G  C(u,v) , to be the length of a longest  path i n C(u,v) . He also suggested therein other plausible definitions for the length of a k-cable, one of which is the definition of the length of a k-cable used i n this thesis.  52  with edge lengths equal to one is equal to the length,  W(C(u,v)) , of the k-cable C(u,v) induced by  the vertices of the unique minimal k-path separating adjacent then  d (u,v) = 2 k + t where u and  v in  v . Moreover, if u and  v are not  t is the number of (k+l)-cliques appearing in the unique  c  k-path between  w and  G . (Observe that the number of (k+l)-cliques in  C(u,v)  may be  zero.)  Proof:  Let  C(u,v)  < Qi , T , Q , •• > T 2  u and  2  n  be the  k-cable induced by the  , Qn > , between  u and v , and let  k-path C'(u,v)  KP(u,v)  , KP(u,v)  =  be any other k-cable between  v . B y Theorem 3.2 in Proskurowski (1984), each path p' of C ' contains all the vertices of  some path  p in  C(u,v) , implying the minimality of  implies that each one of the (fc-f l)-cliques to the k-cable  T  in  t  C(u,v) . The remaining edges in  The proof follows since Q  and  x  Q  n  W(C(u,v)) . The construction of the k-path  KP(u,v) C(u,v)  are k-cliques.  contains exactly one edge that belongs  are  (u,i) , i £ Q , and  (j,v) , j £ Q  1  n  .  •  Next, we will present an alternative characterization of a k-path which will be used in the sequel. First, we need to introduce some additional notation. Let  G = (V, E)  3G (resp. , %') denote the collection of all k-cliques (resp., (k+l)-cliques) in G. V, Q £ % , Q £ %' we let S (U) = max  „,„.d Cv  1  0  where  V(A)  v  a n (  2  ^  vCV(Q)  Definition  and  6'Cv)  '  v  = max  Q'  ,  U £  ,d Cv,v), c  vCV(Q')  '  y  t  as follows : for  ^(^j)  — ^Q ^ 3^ > V  2  Q  f  1  u r t n e r  and  i  Q  in  2  <»i;.)  4.1.2  {  for all pairs v , {  The extended  Vj  3G ,  Qi <v v- Q-x i  two inequalities is satisfied as a strict inequality. orders (3G' ,  , v)  e  For a vertex  denotes the vertex set of A . For each pair v , vj £ V we define a partial order on  3G , (3G , < „ . „ . ) &Q ( i)  '  V  be a k-tree and let  Q if  l  <..  Q  v v  2  if and only if 6  Q  (v ) {  <  Q i <v vj Qi and at least one of the  Similarly, using  f  6Q(*0 , we define the partial  £ V.  k-path  between  53  vertices  v  t  and  «• , KP(v , t  v •)  =  < T , Q , T x  x  2  , Q , •••, T 2  (k-t-l)-cliques 7\ and  T  Proposition 4.1.2 vertices  , Qn , T  n  , where  n+1  > , is the k-path  n + 1  and  X  in the k-tree graph  KP{v ,vf)  =  i  extended with the two  {  V ^ ) = { » J U V(Q )  The extended k-path  and  KP(v ,Vj) V(T )  = {}  n+1  < T , Q , •••, Q x  U V(Q )  Vj  x  , T  n  .  n  >  n + 1  between  G = (V, E) consists of all minimal k and (k+l)-cliques of  G with respect to the partial orders (9G , <«,.«.) and (96' , <«,-«.) . respectively.  Proof  W e first show that any (k-f-l)-clique that is not contained in  with respect to  (3G' , <«,.«.) •  be a vertex in M such that (k+l)-clique in KP(v ,Vj)  Let  7\  f  with the highest index such that p  <v Vj t  M.  <v Vj  T  Otherwise, let .  contrary, that there exists a (k+l)-clique cannot be in KP^v^Vj)  such that  T  p  <v Vj t  M.  , and let  t  x  T  be the (k+l)-clique in  p  Then,  d (vj,x)  >  c  v(T  m a x v e  KP(v ,Vj) i  ) ^ ( ji ) c  v  '  v  M .  Next, we will show that every (k+l)-clique  M  KP(v ,Vj)  have no (k+l)-cliques in common  {  is in KP^v^x)  p  is not minimal  Observe that x is not a vertex of any  and KP(v ,x)  f  then it is easy to see that  T  = max^^. y^jd^v^v).  i  . Now, if KP(v ,Vj)  i  implying that  M be a (k+l)-clique which is not in  d (v ,x) c  KP^v^vf)  T  in KP(v ,Vj)  is minimal. Assume, on the  {  M such that  M <v Vj  T. B y definition, it follows that  t  . Moreover, by the above there exists a (k+l)-clique Since (3G' , <v Vj)  is transitive, that would imply  t  T  p  T  p  £  <«,« J  KP(v ,Vj) i  T,  which  is impossible. Next, we will show that every k-clique which is not in KP(v , {  be a k-clique not contained in dcK,Zi) KP^v^Vj)  = ™<M ) veV(M  dc(v ,v) {  KP(v , t  and  vfj , and let vertices  d {vj,x ) c  = max  2  have no k-cliques in common then  between two subcases.  54  Q  x  veV(M)  d (v ,x) c  j  <« v - M. i  J  x  x  w •) is not minimal. and  x  2  in  M  So, let  be such that  . Now, if KP^v^x^)  and  Otherwise, we need to distinguish  In subcase 1, clique, T  Q  Q <v P  KP(v ,  , such that  Vj)  t  <v  x v  {Vj  x±  and, in fact, all vertices of  £  y ( T  M,  rfc(»,-,t;)  j  where  Q  and  = T  p  p  —  d (vj,x ) c  2  m a x  Vj  —  x  2  separator.  Then,  Q  By the above, there exists a k-clique transitivity of (3G , <«,-«•) implies that  Let  G = (V, E)  V : ddv^v)  < q}.  be a k-tree,  v ( T ) ^ ( j^ )  The subgraphs  Proof  1) € V  unique k-path  KP (v ,v) t  in  KP(v ,Vj)  Q Q  p  M <«,-« - Q-  in  p  contained in  Clearly,  J  t  Q  <v^j  p  <«,-« - Q , which is impossible.  i  u? (fe,«,) < m c  v  is a k-leaf in  .  M.  Then,  V. — { v €  t  {  d^v^v)  v£V  = m.  Then, there exists a rf  and ¥  Let Q, be the k-clique adjacent to ¥  in the  x  x  for all  t  t  V .  = < Q , T , Q , T , • •, T, , Q, > , between 0  W  v G V, are sub-k-trees of G .  max  dc^jTT) =  U|  •  J  2  v£  Q,  e  V . It is easy to see that any other vertex  > m . Thus, node  p  M is not in KP(v ,Vj)  such that  KP(v ,Vj)  G ( V , ) = ( V^E^,  , KP(v ,'v)  . Clearly,  {  Q  (3G,< . .) .  q — a positive integer, and for any u , - G V let  such that  t  d^v^x^  • Then, it is easy to see that  v  is minimal with respect to  {  which determines a k-cable (7(1^,¥) of length m. KP(v ,U)  v  . Moreover,  Further, denote by G(V^) the subgraph of G induced by  Proposition 4.1.3  Choose  are vertices of some k-cliques in  , in KP^^Vj)  p  e  v £  Assume that there exists a k-clique M such that  dc(vi,v)  Then, there exists a k-  \ {rj .  Finally, we show that every  k-path  M  . Then, M is a k-clique of some (k+l)-clique, T  {  a  is both a u,- — x± separator and  p  .  {  M.  i V j  KP(v ,Vj) m  Q  KP(v ,Vj)  but which is a k-clique of some (k-f-l)-clique,  Vj)  {  In subcase 2,  =  is not a vertex of any k-clique in  x  , not necessarily contained in KP(v ,  p  , of  p  x  v  v  and thus the vertex set of  adjacent to  Q,  is  v , if exist, would have  G(V ) . B y eliminating 17 and repeating the above {  55  procedure we construct a reduction process for G(V ) , implying that it is a k-tree.  •  {  Recall that a reduction process in a k-tree with respect to k-cliques in G.  and  t  G , then  K  t  induces a descendancy relation of vertices  Such a relation can be extended to a descendancy relation among k-  cliques and (k+l)-cliques in G. In general, if K in  G  Kj are two k-cliques (resp. (k+l)-cliques)  is said to be a descendant of Kj if every node that is either contained in K  or  i  is a descendant of  K  {  (resp., some k-clique in  K) {  is also either contained in  Kj  or is a  descendant of Kj (resp., descendant of some k-clique in Kj) with respect to the reduction process. This descendancy relation in  can be used to index all  G  k(n — k) + 1  (k-f-l)-cliques) in G , such that the index of a k-clique (resp., (k-f-l)-clique) index of a k-clique (resp., (k+l)-clique) Now, let  G(V ) and  is a descendant of  K  {  t  and  %j  (resp., %[ and  Kj.  ) , respectively. Further, let  and 3G- (resp., 9G' - and %'j ) , respectively, and assume that that  t  Krj be the k-cliques (resp., (k+l)-cliques) having the highest indices, ;  is smaller than the  K  G(Vj) be two sub k-trees of G with a corresponding collection of k-  {  cliques (resp., (k+l)-cliques) % and  Kj if  ^-cliques (resp. n — k  r <  t  9G,- n %j ^ 0 (resp., 9&J D %'j ^ 0) if and only if K  i  r - and t  {  r- , in 3G,-  Tj . Then, it is easy to verify  € %j (resp., K  I  T{  Kr  T{  G 3G'- ) . This  result can be used to establish the Helly property of a set of collections of k-cliques (resp., (k+1)cliques) of sub k-trees of a given k-tree, as follows :  Proposition 4.1.4  Let  G  x  G  m  be a collection of sub k-trees of  collections of k-cliques (resp., (k-fl)-cliques)  3G ,---,3G 1  m  (resp., %  I 1  G  with an associated  , •••, % ,) . Let f  3G =  {%!,•••, 3G } and 3G' = { 3G' , • • •, %' } . Then, 3G and 3G' have the Helly property. That is, m  m  if 3G n 9G. ^ 0 (resp., %' D 9Gj # 0) for all i and j, then ;  ;  {  # 0).  56  3G # 0 4  (resp. n™ 5&( ;  Proof:  Let K  r{  (resp., K  ) be the k-clique (resp., (k-fl)-clique) with the highest index in 3G,-  T{  (resp. , 3G' ) and assume, without loss of generality, that (resp., 3C[ n %'j ^ 0) for a l l j we have  Theorem 4.1.1  K  r <  r • for all j . S  x  £ %j (resp. , K  fl  Let G = (V, E) be a k-tree,  l rj  £ %'j ) for all j .  •  V = { v , v ,• • •, v } , n > k +1 , and let x  2  be  n  an even integer, R > 2k. For each v £ V let G ( K , ) be the sub k-tree of G induced by V = {  {  { v € V : <f (",f,-) < j + k — 1 } , with an associated collection,  9G,- , of ^-cliques.  e  Then,  D - %>i 7^ 0 > I Q { 1 > 2 , • • •, n } , if and only i f d (v , Vj) < R for all pairs t, j £ I. eI  c  Proof:  Suppose that ^- j^i  G(VA  we have that  Q  ,  4.1.1 it follows that V  v  and C  W(C ^ )  < f  Q  V  and  KP(v ,Vj) {  satisfying  m a z ^ ^ dc(v ,v) t  all k-cliques i n KP(v and  v  W(C  paths in C(v;, vA which are in the component C Next, assume that for any pair  t  ,Vj)  i, j £ I,  y  ;  Proposition 4.1.1, d (vj, c  ;  =  § •  v) < § +  t  and Vj , respectively.  t  Q  )  < §  , into two  From Proposition  , implying that  de(v ,Vj) {  =  W(C Q^} denotes the total length of the V  .  n  d (v ,Vj) c  t  < R . Then, let Q  t  be a k-clique i n  {  If KP(v ,Vj) does not contain a k-clique then {  Vj are adjacent and the k-clique containing U  < 4 + k — 1.  ' — 2  1  = d(v ,x{) = ^ + k — 1 . If no such k-clique exist then  are in 3G,- PI 3C- .  Proposition 4.1.1, W(C . Q )  v  {  Q ) < R , where, for example,  Q) + W(C  dJv^v)  C(v , vf) , induced by KP(v ,Vj)  , containing  v  , l  l  v  ;  v£V(Q )  Q separates the cable  ^  which is in 3G D %j . B y definition of  Vj)  {  *' ' — *  v  t  components (sides) C  KP(v ,  , dciv^.v) < § + k — 1 and max  v£V(Q )  Now, the k-clique  W(C  in the k-path  l  max  "  v  ¥^ 0 • Then, it follows from Proposition 4.1.2 that for any pair i, j  £  £ I there exists a k-clique  t  v  {  implying that  and Vj is in 3G^ n %j . W(C  V  57  7^ 0-  t  Otherwise, by  Q), < § • Therefore, again by  k - 1 for all v £ Q, . Thus,  Helly property of the collections 96^ we have that D -g.  v  E  Q, £ % CI %j , and by the {  Theorem 4.1.2  Let G = (V,E) be a k-tree,  V—{ v ,v t  R > 2k — 1 . For each  be an odd positive integer,  v } , n > A + 1 , and let R  2  n  v G V let G(V ) be the sub k-tree of G t  i  induced by V — { v £ V: d (v, v ) < L f J + A- } , where ["J is the largest integer smaller than t  e  {  n  a , and let 3G- be the collection of (k+1 )-cliques i n G(Vj) . Then,  9Gj ^ 0 , I C { l , - - , n },  if and only i f d (v ,Vj) < R for all pairs i , j € I. c  Proof:  {  Suppose that  f~1 .^3Gj ^ 0 . Then, it follows from Proposition 4.1.2 that for any pair 1£  G I there exists a (k-fl)-clique be the k-cliques in KP(v ,Vj)  that induce  {  and thus,  < Lf J • Similarly,  W(C ^ ) V  Q  implies that W f C ^ J Lf J +  T, i n KP^^Vj)  < Lf J .  Thus,  T , . Clearly, dc(v ,v) f  <f«;(V , v) < [§ J + k c  t  „,) = ^ ( C „ .  l+1  < [§ \ + k — I for all v G Qi  1  d (v ,  Q  Q (  1  uG Q  for all  , which  1+1  ^(^.Q^^ + !<[§] +  ) +  i = RNext, assume that for every pair  KP^^vA  satisfying  t  clique then  t, j G I, d^v^Vj)  = max  d^v^x^  then a l l (k+1 )-cliques in KP(v  < R. Let T, be a (k-f-l)-clique in  = Lfj +  k.  If no such (k+1)-clique exist  ,Vj) are i n 3G' f l 36'- . If KP(v ,Vj)  does not contain a (k+1)-  dc(v ,v) t  {  v and i> • is i n 3G' f l 3G'-.  v and Vj are adjacent and the (k-t-l)-clique containing f  Otherwise, T G 3Gj- . Suppose that l  Q ) =  Then, =  T, G 3G' n 3G^. . Let Q, and  such that  i, j  T  l  Lf J + 1 • Therefore,  [ f J > which implies that  d (vj,v) c  [ f J + k for all v G T, , implying that conclude that  f~l  is induced by the k-cliques  3G{ ^ 0 .  <  W(C  Q and Q i l  ) = R -  V Q  [f J + k —  f  1  for all t E  l+  Lf J ~ 1 =  i n KP(v , {  Lf J  • Further,  «•) .  + 1 - 1 d (v-, c  v) <  T, G 3G'- . By the Helly property of the collections 3G' we  •  Observe that in Theorem 4.1.1 and 4.1.2 we restrict  58  R to be at least 2 A — 1 . It can be  easily shown that if R < 2 k — 1 then the only decomposition of decomposition problem coincides with the vertex set  V for our R k-cable distance  V. In general, we solve our R k-cable distance  decomposition problem by using the properties of two clique-intersection graphs associated with G , which are constructed as follows. If (resp., 1}  G (Vi)  denote the sub k-tree of G induced by  k+1  V  (resp.,  =  {  G V: d (v,  { v  c  v)  =  k  (V,E ) k  G (Vi)) k+1  G  (resp.,  , v G V, where {  G (V ) k  {  {  V = { v G V: d (v, u.) < f + k {  c  t  G (V ) k  t  =  k+1  v G V let  |_§J + k } ) . Let % (resp., 3G[) designate the collection of  <  t  k-cliques (resp., (k-f-l)-cliques) in G  is even (resp., odd) then for each  R  (V,E ) k+1  V= { v : {  G (V^)) , and consider the intersection graph k+1  (resp.,  ,  induced by the sub k-trees  G V}  and (S.-.w^) G  G (V ) k  (resp.,  {  (resp., (B.-.S^) G E )  if  k+1  3Gi n 3G- ^ 0 (resp., 3G' D 3C'- ^ 0) . Then, following the lead of, for example, Kolen and Tamir ;  (forthcoming), one can use Proposition 4.1.4 to demonstrate that both G and k  G  k + 1  are chordal  graphs. By combining Theorem 4.1.1 , 4.1.2 and the fact that we can construct an  0(n ) 2  G  k  and G  k + 1  are chordal graphs  time algorithm for generating an R k-cable distance decomposition of  the vertex set of a k-tree. Indeed,  Theorem 4.1.3 (V,E)  Proof  The R-cable distance decomposition problem can be found in a k-tree  in 0(n ) 2  G =  time .  If R is even (resp., odd) we construct the clique-intersection graph G  k  By Theorems 4.1.1 and 4.1.2 , a minimum clique cover in  G  k  or  G  k + 1  (resp.,  G*  + 1  ).  provides us with a  solution to the decomposition problem. The overall complexity of an algorithm which generates the decomposition can be established as follows. From Theorem 4.1.1 (resp., 4.1.2) it follows that for an even (resp., odd)  R  ,  (v , v t  •) G G*  Thus, the clique-intersection graphs  (resp.,  G  k  (v , {  (resp.,  59  Vj)  G*  + 1  G G*  + 1  ) if and only if  d (v , c  {  )  Vj  <  R .  ) will be at hand after all cable distances,  d (v , Vj) , for a l l v , Vj i n e  i  V have been found.  t  other vertices  The k-cable distances from a vertex  t> to a l l 4  v, v £ V, can easily be computed i n linear time. Indeed, we initially set dciy^v) —  2k — 1 for all u £ A«y'(«,-) . Then, we simply successively build up the k-tree G so that whenever a vertex  v, v £ V , is added to a current sub-k-tree,  the construction of G  d (u,-,u)  =  e Adj(v)^ ( ' )  m a x  c  c  u  (resp., G * ) takes 0 ( n ) time. Since G  f c  + 1  2  graph, its minimum clique cover can be found in  Vi  ^ ' Thus,  u  (resp., G *  k  + 1  ) is a chordal  0(n) time, see, for example, Gavril (1972) .  Therefore, the complexity of the algorithm is dominated by the construction of G * (resp. G * which takes 0(n ) time.  )  •  2  4.2  + 1  k-Cable Diameter of a k-Tree  Let  G = (V, E)  denote by D  ,D  c  =  c  be a k-tree, \ V\ = n , in which a l l edge weights are equal to one, and  ^(^21^3)  —  m  a  x v  . .£V  ^(i c  V  v  i j) » ^ v  k-cable diameter of G . In this  n e  section we develop a linear time alogrithm for finding a longest k-cable, d (v ,v ) c  diameter,  D , of a k-tree.  2  3  , and the k-cable  Our algorithm is similar to Handler's (1973) algorithm for finding a  c  longest path in a weighted tree. Before introducing the algorithm, we need to recall some notation introduced in Section 4.1. For any non adjacent pair of vertices shortest k-cable KP(v ,  Vj)  t  v  it  v  p  {  a  n  d  C  t  . Further, any (k+l)-clique  i  separates C(v , Vj)  v T (. i> j)  C  C(v ,Vj)  «- , «• £ V, the extended k-path,  v T,( i> j) v  v  jt  T  KP(Vi,Vj)  (resp., k-clique  p  , induces a  Q ) contained in p  into two sides (components), one of which could be possibly empty, ( ?-' vt,Q ( i> i) res  C  v  r  v  a  n  d  C  Vj,Q ( i> j)) v  p  v  ' not containing  V j  and V{ , respectively .  Theorem 4.2.1  Let v  1  be any k-leaf of a k-tree G = (V,E) , and let v  2  60  be any vertex i n G  such that m  a  Proof: Let  .  v) . Then, D = d (v ,v )  .  x  2  v  c  2  £  — max^^ dc(v ,v)  c  ydc(v ,  x v  d (v , v )  Let v , v 4  T  p  and  KP^jV^)  2  c  2  3  Further, let  be any pair of vertices in  5  V.  lt  T , is in KP[y^,v^)  T^,  T  and  p  G V  be such that  d (v ,v ) c  2  d (v , v ) < c  4  d (v ,v ).  5  with the lowest index such that  2  T^, exist since  v± is a k-leaf and  =  3  c  T  . We will assume, without loss of generality, that 1  3  3  with the highest indices such that  2  be the (k+l)-clique in KP(v ,v )  v ) . Note that  v  We will show that  be the (k + l)-cliques in KP(v v )  and  Further, let KP(y ,  T,  1  P  2  3  is in  p < p' . T^„ is in  T^,, exists since v  2  is a k-  leaf. Now, we need to consider two cases.  Case 1:  p" > p .  B y definition of T , and T^,, and since p " > p', we have that  f  is contained in KP(v ,  v ) . Thus, by the construction of v  2  4  3  ^(^,T>2^ ))>  W(C  3  and by the construction of v  2  1=  W(C  V  T  (v v ))n lt  x  W(C  2  rfe(» ,t;3) 2  2  (4.1)  4  we have that :  W(C.  Let  we have :  (v ,v ))  T  T ,,  v  =  ( " i ' "2)) >  W(C  ^  (v ,v ))  T  d>  2  p''  (4.2)  5  Then, by (4.1) and (4.2)  K.Dj)).  T  > , , v )).  T  ^ . . T . K . ^ ) )  3  +  +  W(C  W(C  K,* )) - / 2  T  (4.3)  2' p'  T  Jv ,v )) 2  4  -  I.  We further claim that  W(C  T^V^V,)) +  W(C  61  T  (v ,v ))  n  2  4  - I > d (v ,v ) c  4  5  .  (4.4)  Indeed, if p < p ' then  T , is in KP(y , ^4) and (4.4) is satisfied as equality. Otherwise, p = p ' . 2  Then, i f T , is not i n KP{v ,  v)  4  (4.4) clearly holds, while i f T , is i n KP(v ,  5  contained i n at least one of the two k-paths generality, we can assume that  KP(v ,v ) 2  T , is i n KP(v ,  and  4  Q^, is in KP(v ,  .  5  Without loss of  d (v , v ) > d (v , v ) . c  2  3  c  4  5  T , is i n KP(v , 2  v ) . Let Q^, be 3  u ) and having the highest index among all such  x  k-cliques. B y the construction of v  2  4  p " < p ' . In this case we clearly have that  the k-clique i n T , such that  KP(v ,v )  T^, is  5  v ) , which was shown above to imply (4.4) . W e  2  conclude therefore by (4.3) and (4.4) that i f p " > p ' then  Case 2  r; ) then  4  2  we have that :  3  ( v„Q  W C  , ( « 2 . » 3 ) )  W  >  ( C  v  n  (  («2,«4))  •  (4-5)  Further, by the construction of v , (4.2) holds. Now, by (4.2) and (4.5) , 2  dc(v ,v ) 2  =  3  W(C  Q  (v ,v )) 2  + W(C  3  T  ( ,v ))) Vl  2  (4.6) ^  >2^4)) +  p  4  ^  r  ( ^ , 4  o p  We claim that  ^ , ,0 ( C  4  Indeed, i f p < p ' , not in KP(v  4  f  W  2,»4))  T , is i n KP(v , 2  +  mC^r  ( « ! , ! % ) ) >  (4-7)  rfe(«4,»6)-  t> ) and (4.7) is satisfied as equality. If p = p ' and T^, is 4  , « ) , then (4.7) is clearly satisfied. Otherwise, p = p ' and T , is i n KP(v , 5  4  In this event, similar to the proof in Case 1, we can assume without loss of generality that  62  v) . 5  T , is in  KP(v ,v ) 2  , which was shown above to imply (4.7). We conclude that (4.7) holds, which completes  4  the proof.  •  Now, as explained in the proof of Theorem 4.1.3, computed in linear time which implies, by Theorem 4.2.1, that in linear time.  63  d^t^,^) D  c  and  = d (v ,v ) c  2  3  d (v ,v ) c  2  3  can be  can be computed  Chapter V NC ALGORITHMS FOR RECOGNIZING PARTIAL 2-TREES AND 3-TREES  In this chapter we introduce the notion of a k-separator (k > 2) of an n-vertex graph G = ( V, E) . Formally, a k-separator is a set of vertices S, \S\ = k , which induces a partition of V \ S into sets  V\  and  V  2  connects a vertex in  satisfying  (i)  with a vertex in  j Vj| < (k/k+\)n  , i = 1,2,  and  (ii)  no edge in  E  V • We prove the existence of a k-separator for partial 2  k-trees and construct, a linear time algorithm for generating such a separator in k-trees. This algorithm can be used to construct a balanced binary decomposition tree of a k-tree in  0(n logn)  time. W e further derive other separation properties of partial k-trees which are used to construct a balanced decomposition of an embedding of a k-connected partial k-tree into a k-tree when 2,3.  Finally, we develop parallel algorithms for the recognition of partial k-trees when k = 2 , 3 .  These algorithms require k =  k =  0(log n) 2  time and use, respectively,  0(n ) 3  and 0(n ) 4  processors. For  2 and 3 our algorithms improve considerably the processor bound of Bodlaender's (1988)  64  general algorithm for the recognition of partial k-trees, which would require, respectively, and  0(n  )  0(n ) processors for these cases. 13  The chapter is organized as follows. In Section 5.1 we study k-separators of partial k-trees and describe an trees.  O(nlogn) algorithm for constructing a balanced binary decomposition tree for k-  In Section 5.2 we obtain additional separation properties of partial k-trees, and show that  they can be used to construct a binary balanced decomposition of an embedding of a k-connected partial k-tree when k = 2 and 3 . In Section 5.3 we develop N C algorithms for the recognition and embedding of a 2-connected (resp., 3-connected) partial 2-trees (resp., 3-trees), and in Section 5.4 we develop an algorithm for recognizing partial 3-trees which are not necessarily 3-connected.  5.1 k-SEPARATORS  Let  G = (V, E)  set of vertices  S,  be a partial k-tree (k > 2) with  of cardinality  |5| =  | V\ = n . A k-separator of G is a  k , which induces a partition  { V^, V } 2  of  V \ S  satisfying  \V \ t  <  n,  i = 1,2,  (5.1)  and no edge in E connects a vertex in V  x  with a vertex in V  2  (5-2)  Observe that a k-separator extends the notion of a 2-separator defined for series parallel graphs (i.e. partial two trees), see, e.g., Hassin and T a m i r (1986) .  65  Theorem 5.1.1  Every partial k-tree contains a k-separator. Moreover, for a k-tree a k-separator  can be constructed in linear time.  Proof: of  Since any k-separator of a k-tree  G — (V, E)  is also a k-separator of every partial graph  G, it is sufficient to prove the existence of a k-separator for k-trees. For that purpose, we  construct below a linear time algorithm for finding a k-separator of a k-tree G . The algorithm follows a reduction process until reaching, for the first time, a k-leaf vertex corresponding set of descendant vertices, D(K ) V  , of the k-clique K  v  for which the  induced by Adj(v) , contains  v  at least | n distinct vertices.  Formally, the algorithm has two steps.  Step 1  We initially set  D(A) = 0 for all k-cliques  A  of  G.  In general, let  v  be a k-leaf  which is currently being considered for elimination in the reduction process. Let Adj(v) = { «  1(  u  k  } and  V(Kj)  denotes the vertex set of a graph A. K  v  , and  = Adj (v) U {v} \ {«,}, Then, update  D(K ) V  j =  V(K )  where  V  = V(A)  , the set of descendant nodes of  |D(i(\,)| as follows:  D(K ) V  \D(K )\ V  =  k (U  k = £  IKKJ)) U D(K ) U V  |Z)(tf,.)l + \D{K )\ V  i=l  66  W  + 1.  (5.3)  (5.4)  If  I Z > ( ) | < | n , we continue with the reduction process; otherwise, we go to Step 2 where  the k-separator is produced. Observe that Step 1 will terminate whenever  n > 3k . If n <  3 k every minimal separator of G is a k-separator.  Step 2  We need to distinguish between two cases.  J2\ ( j)\ D  Case 1  K  + 1 > g»-  j=l  Let  Vj = D(Kj)  7,  be such that  and let  , j = I , - ,  *, and  V  = V \ {(U*  k+1  | V. j = max. , , JK,-|. J = l , • ••,k+l  = 1  VA U Adj(v) U > } } ,  We will prove that the set of vertices  J  s,  S=  is the required k-separator. Further,  ( Adj(v) \ _ [_ V(K,)  if 1=  {V  where  V}  lt  2  k+l  otherwise  V\ =  V, and  V  = V \ (V  2  t  U 5)  is the required partition of V \ S satisfying (5.1) - (5.2) .  Indeed, by assumption,  Y<)  \ j\ V  =1  =  Y?l \ (K j)\ D  =1  > i»  ~  !>  w  h  i  c  h  coupled with  £+1  E y - i I^jl  =  n  —  (^+1)  implies that  V \ k+1  < n -  ( i + 1) -  (§n -  1) <  \n.  Moreover, since v is the first node encountered by the reduction process for which  67  (5.5)  l-D^u)!  >  I n , we have that  1101  < h , j=  k.  3  (5.6)  Thus, by (5.5) and (5.6)  \V,\ =  Furthermore,  j t?" | = | K , | > -  —  x  \ V  <§»<E£I > * > 2 .  ^ , which implies that  \ < n - k -  2  By the definition of  , V  S , and there is no edge in E  2  (5-7)  n  —  ^  I  < j  ^  and 5 we also have that  with endpoints i n  V  1  n  .  V nV 1  and  V  2  2  (5.8)  =  • Thus, 5  <D,V \JV =V\ 1  2  is the required It-  separator.  Case 2  J  \D(Kj)\  + 1 < | n.  i=i  We will prove that i f Case 2 holds then D(K )  is the required k-separator.  Let  denote the set of descendant nodes of K„ just before it was updated by (5.3), which  V  resulted with D(K ) . V  |D(iir„)| > | n , and construct the new sets  B y assumption,  1  V = li'j-x D(Kj) U {v} and V = x  2  \V \ < | n . Further, \V \ < | n , since otherwise Step 1 would have 1  terminated earlier. Now, let V V\ (V  S = Adj(v)  2  x  = V± if | ^ | > | V 1 and V 2  l  = V  2  otherwise, and let V —  U S) , where 5 = Adj(v) . Since | V \ < § n, i = 1,2, we have that {  68  2  Moreover, by (5.4)  1^1  +  2  mar ( | V \, | V | ) > \ n . Since |  | V "  V  I^J  =  + \ V \ = n — k we derive  2  x  \D(K )\ > § n , which implies that  \V \ = 2  2  | < n - J t - i n < j|-jn, k> 2 .  Again, by the definition of V\ , V  2  and 5 we also have that  0 and there is no edge with endpoints in V\ and  ^  U V  2  =  V \ S , V \ fl V" = 2  V . 2  The above algorithm will produce a k-separator for a k-tree in linear time since Step 1 will be executed at most  n — k times, (5.3) and (5.4) require constant time for each iteration and Step  2 requires constant time.  Let S  into  •  G = ( V, E) be a k-tree and S a k-separator of G which induces a partition of  {Ki,^}  that satisfies (1) and (2) .  induced, respectively, by  V\ U S and  Then, the subgraphs G ^ U 5 )  G recursively until we end up with k-cliques. That  rooted binary tree in which the root  v represents the graph  of  q  2  in T then  q  x  and  2  2  entire decomposition can be represented by a balanced binary decomposition tree,  q  G(V Uff)  V U 5 are also k-trees which can be similarly decomposed.  We can proceed in this manner to decompose  ?! and  and  V\  2  T, which is a  G , and if some vertex q is a parent  are sub-k-trees of q obtained by the above decomposition  of q .  Corollary 5.1.1 G  Let G = (V,E) b e a k - t r e e .  Then, a balanced binary decomposition tree, T, of  can be constructed i n O(nlogn) time.  69  Proof:  Let L denote the subset of vertices in  vertex in L  has  / edges. The leaves of T are  T such that the path from the root of T to a k+l  cliques and there are at most  n — k of  them. Thus the number of vertices in all subgraphs of G represented by elements in L is bounded by  TI + k(n-k) . That implies that, the construction of k-separators of subgraphs of G represented  by vertices in L takes  0(n)  time. The proof then follows since T is, by (5.1), at most  deep, i.e. the path from the root of T to any of its leafs contains at most  5.2  0(log n)  0(log n) edges.  SOME SEPARATION PROPERTIES OF PARTIAL k-TREES  We derive in this section some separation properties of partial k-trees into k-trees which will be used later to develop N C algorithms for the recognition and embedding of partial k-trees into ktrees when k = 2 and 3 .  Lemma 5.2.1 V\S  Let G = (V, E) be a graph and S a separator of G which induces a partition of  into {V , 1  V}  such that  2  0 < \S\ = I < k , \ V U S\ > k , i = 1,2, and the subgraph {  of G induced by S, G(S), is an /-clique. Then G is a partial k-tree if and only if the subgraphs Gj =  G(V  1  Li S) and  G  2  =  G( V U S)  induced, respectively, by  2  V  U S  x  and  V  2  U S  are  partial k-trees.  Proof:  If G is a partial k-tree then since G± and  k-trees.  O n the other hand, assume that  E-i) and  G  subgraph of  2  = (V  2  G  t  and  U S , E ), 2  G  x  and  G  G 2  2  are subgraphs of G they are also partial  are partial k-trees and let  G  x  = (V  1  U S ,  respectively, be their embeddings into k-trees. Clearly, G(S) is a  G . Therefore, there exist fc-cliques K 2  x  70  and  K  2  contained, respectively,  in  G  and  l  G  and such that both  2  i • • •)  and  since  and  x  denote the nodes in  consider the graph i = / + 1  K  G obtained from  K  contain the  2  l ^ i ^ ) and  G = (V, E  / = 0, we simply choose for  are contained in  Then, it is easy to see that  G  and  x  K  x  and  K  such that  G .)  •  2  S  C S  x  C V we will denote by  2  G(S  For a graph  ; K^S^)  2  which is augmented with all arcs between pairs of nodes of S  Lemma 5.2.2  Let  G = (V, E)  i = 1,2. G  2  Then, = G(V  2  Proof:  U S; K({s ,s }))  1  v{ \i i) v  s  x  2  joining and  2  2  V ^ 0 and  2  {  | V U 5 | > k, {  ^({^I,* })) , i 2  with  x  p(^i,s ) 2  Thus, suppose that  Sj and  s, 2  v  x  6 V  x  G is a partial k-tree.  2  contracting the edges along  p(si,  Thus,  G(V  2  s) 2  U S;  respectively, in the subgraph s  x  and  G( 5  2  U S). in  would yield a 2-clique with a vertex set ,s »)," 2  71  Since  V ^ x  and two disjoint paths, p(*>i,Si)  form a simple path, p(si,S2)' between  G is contractible to  x  = 1,2, are partial k-trees then, by using Lemma 5.2.1 we  G is a partial k-tree.  v  x  are partial k-trees.  2  is two-connected, there exists a vertex  p(v ,s ) ,  S  S , S — { s j , s } , a separator of  x  If G(Kj U 5 ;  G  x  if they are missing in G .  x  V \ S into { V , V } such that x  S,  G is a partial k-tree if and only if the subgraphs G = G( V U S ; K({ s , s }))  can conclude that and  G — (V, E) and subsets  the subgraph of G induced by  be a two-connected graph and  G which induces the partition of  and  G is a k-tree, and  in the above proof any two k-cliques which  2  We will use in the sequel the following notation. 2  after the addition of the edges («,-,«•) ,  G is a partial graph of G , it follows that G is a partial k-tree. (Note that in the degenerate  case, when  S  k  2  2  Jfc , j — I + 1 , •••, k and j > i.  v  l+l  K(iif ), respectively, that are not in S, and  \J E )  1  /-clique G(S) . Let v ,  which implies that  G(V  2  and  Therefore, 1  U S),  S =  G ( K U S;  0  and  {si,^}-  ^({sj,s })) 2  is a partial k-tree. well.  Analogously, we obtain that  G(V  U S; K({si,s }))  1  is a partial k-tree as  2  •  Lemma 5.2.3 separator of and  Let  G = (V,E)  be a triconnected simple graph and  G inducing a partition of  | Vj U 5| > Jfc, « =  1,2 .  V \ S into  Then,  G  { V , V} 1  S,  S = { u , « , u }, a x  such that  2  2  3  | Vj \ > 2 , i = 1 , 2 ,  is a partial k-tree if and only if the  subgraphs  G( V,- U S; iT(5)) , i = 1 , 2 , are partial k-trees.  Proof:  If G( Vj U 5 ;  are partial k-trees then, by using Lemma 5.2.1 we can conclude that  so is G . So, assume that of  v , v 1  G , there exist at least three vertex disjoint paths between  separator and G  G is a partial k-tree and let  be in  2  v  x  x  and  v  2  in G , and since 5 is a  | S\ = 3 , at least two of these paths are contained in G( V U S) . Therefore, since x  is assumed to be a simple graph, these two paths form a cycle C in G( V U S) with at least 3 1  vertices. B y the triconnectivity of G there exist 3 vertices, say ~s , S 1  disjoint paths in  V . B y the triconnectivity  G(V  , "sO , ?2( 2 > "* 2) > Ps( 3 > ^3) ( s  U S) , such that  1  1 . 2 , '.\ , respectively. identify  s  t  with  s  p,(Sj ,Tj)  i =  1,2,3,  s o m e  t  for i =  1,2 ,3 ,  3  , in C and vertex  possibly degenerated to a single vertex)  intersect with  Clearly, if we contract edges in the paths "s ,  and T  2  C only i n nodes T j , i  Pi(s , T ) t  f  respectively, we create a cycle  , i — 1 , 2 , 3, C'  that contains  s , s , s . Again, appropriate contractions of edges in C ' will create a 3-clique K(S) . Thus, 1  2  3  is contractible to  G( V U S ; #(5))  and we conclude that  2  Analogously, we can show that  G(V  1  U S ; K(S))  G( V U S ; if(5)) 2  is a partial k-tree.  and  G  is a partial k-tree.  •  We note that the above separation properties of partial k-tree imply the existence of a balanced decomposition tree, T , of an embedding of a biconnected (resp., triconnected) partial 2-  72  tree (resp., 3-tree) and  q  G into a 2-tree (resp., 3-tree). The root, r , of T is the graph G, and i f q  x  are sons of  2  r  G ( l ^ U S; i^(5))) , where  in  T  5  then  q  x  (resp., g )  is the graph  2  is a two-separator (resp. 3-separator of  G(V  1  U 5 ; K(S)) (resp.,  G) satisfying (5.1) and  (5.2), and whose existence follows from Theorem 5.1.1. The biconnectivity (resp., triconnectivity) of  G  implies that  G(V  r  U S; K(S))  and  G(V  2  U S; K(S))  are biconnected (resp.,  triconnected). Thus, i f they have sufficient number of nodes, they can be decomposed in a similar manner. In general, the leaves of the decomposition tree T are biconnected (resp., triconnected) 2trees (resp., 3-trees) which are not necessarily further decomposable in the same manner since they have less than 9 (resp., 20) nodes.  5.3 NC ALGORITHMS FOR RECOGNITION OF PARTIAL k-TREES FOR k = 2 AND 3  In this section we present NC-algorithms for recognizing a partial 2-tree (resp., connected partial 3-tree) graphs  three-  G and finding its embedding into a 2-tree (resp., 3-tree). Without  loss of generality, we assume here and in Section 5.4 that  G is a simple graph.  Algorithm 5.1 Procedure  BBD(G,a,L)  Input  A two-connected (resp., three-connected) simple graph G = ( V, E) .  Output  a = 1 if G is a partial 2-tree (resp., 3-tree), and a = 0  73  otherwise. Further, i f a = 1  then the output L contains an embedding of G into a 2-tree (resp., 3-tree).  Step 0  Set a = 1 and 1 = 0.  Step 1 (1.1)  If \E\ > 2n - 3 (resp., 3n - 6) set a = 0 and exit .  (1.2)  Else, i f | Vj < 9 (resp., 20) check i n constant time whether  (resp., 3-tree).  If yes, find an embedding,  G is a partial 2-tree  G, of G into a 2-tree (resp., 3-tree), let  L = L U {G} . Else, set a = 0 and exit .  Step 2  Else, for each pair (resp., triple) of distinct vertices S  =  {siiS } 2  (resp., S =  {s\,s ,s }) 2  3  of  V, i n parallel, find a l l the connected components of G (V \ S) and denote their vertex sets  by  Vj : j = 1, ••• , r  (2.1)  If \ Vf\  for some r^ > 1.  g  > l\V\ (resp., |V/| > ||V|) for some  ; = 1, ••• , r  reject  s  5. If  all the pairs (resp., triples) S were rejected set a = 0 and exit.  (2.2)  Else, i f  l\V\ < \Vf\ < \\V\  and for some j,  (2.3)  1< j < r  M = Vf U S and x  Else, for an unrejected S compute q, =  a binary search to find Set M = u j x  (2.4)  , set  g  (resp., \\V\ < \Vf\ < \\V\) for some  =  1  x  = 0 or a  n  BBD(G(M  l  ; K(S)),a  x  \\V\  2  > '  =  ^»  (resp.,  Vf).  ' s • r  a  n  d  \\V\ < q < n  , L) t  and BBD(G(M ;  K(S)),a ,L ).  2  2  2  = 0 set a = 0 and exit. Else, set L = L U L . E x i t . x  74  a  PP^  v  \\V\).  U S.  2  2  l^/l  n for which \\V\ < q <  Vf U S and M = (V\Mj)  C a l l i n parallel  either a  Ylj<i  M = (V \  2  If  5  Theorem 5.3.1 graph  Algorithm 5.1 recognizes whether a two-connected (resp., three-connected) simple  G= (V, E) with | V\ = n is a partial 2-tree (resp., 3-tree) and produces an embedding of G  into a 2-tree (resp., 3-tree) in 0(hg n)  time using 0(n )  2  Proof:  3  (resp., 0 ( n ) ) processors. 4  We first show that the steps of Algorithm 5.1 are valid.  If (1.1) in Step 1 is valid then,  since every 2-tree (resp., 3-tree) has exactly 2n — 3 (resp., 2n — 6) edges, it follows from Lemma 5.2.2  (resp., Lemma 5.2.3)  that  G  is not a partial 2-tree (resp., 3-tree). If all pairs (resp.,  triples) in Step 2 were rejected, G does not contain a 2-separator (resp., 3-separator) and then, by Theorem 5.1.1, G is not a partial 2-tree (resp., 3-tree). 5.2.3) we can conclude that triconnectivity)  of  G  G  Thus, by Lemma 5.2.2 (resp., Lemma  is not a partial 2-tree (resp., 3-tree). The biconnectivity (resp.,  implies  the  biconnectivity  (resp.,  triconnectivity) of the  minors  G(M ; K(S>)), i = 1,2, created in (2.2) and (2.3) of Step 2 respectively. Therefore, by Lemma {  5.2.2  (resp., Lemma 5.2.3), G  G(M ; K(S)), i  i=l,2,  is a partial 2-tree (resp., 3-tree) if and only if all the minors  created in Step 2 are partial 2-trees (resp., 3-trees).  Next, we will show that Algorithm 5.1 requires processors.  0(log n) 2  time and  0(n ) 3  (resp.,  0(n )) 4  In Step 1, (1.2) can be performed in constant time using, for example, the sequential  algorithm for the recognition and embedding of partial 2-trees (resp., 3-trees) into 2-trees (resp., 3trees) of W a l d and Colbourn (1983) (resp., Arnborg and Proskurowski (1986)). components of G(V\  S) can be found, by the parallel algorithm of Shiloach and Vishkin (1982), in  O(logn) time and using  0(n + m)  0(n) . Since there are  2  Step 2 requires 0(n ) 3  A l l connected  0(n )  processors, where  (resp., 0(n )) 3  m = \E\ . Note that in our case  m =  pairs (resp., triples) to be considered simultaneously,  (resp., 0 ( n ) ) processors. Further, in Step 2, (2.3) takes 4  75  O(logn) time using  0(n ) processors in order to compute partial sums, q ,  and to perform a binary search on them.  t  Since in (2.2) and (2.3),  \M \  < §|V|  {  terminate after performing at most  (resp., \M \ {  O(logn)  <  \\V\),  i = 1,2,  nested calls of Procedure  BBD(G,a,  algorithm recognizes whether a two-connected (resp., three-connected) graph G (resp., 3-tree) and delivers in  L  time using 0(.n ) (resp., 0(n )) 3  an embedding of processors.  4  G  Algorithm 5.1 will L).  Thus, our  is a partial 2-tree  into a 2-tree (resp., 3-tree) in  0(log n) 2  •  Note that in Algorithm 5.1 we have restricted  G to be biconnected (resp., triconnected).  However, the recognition of partial 2-trees which are not necessarily biconnected can be easily carried out  by a slight modification of Algorithm 5.1. Indeed, we can find all biconnected  components of G using the parallel algorithm of Tarjan and Vishkin (1985) in O(logn) 0(n)  processors.  time with  If G does not have biconnected components, then it can be decomposed by zero  or one separators into subgraphs of cardinality less than or equal to 3. Then, since every graph on 3 vertices is a partial 2-tree, Lemma 5.2.1 implies that  G is a partial 2-tree. Otherwise, we perform  Algorithm 5.1 on all biconnected components of G. B y Lemma 5.2.1, only if all biconnected components of requires  0(log n) 2  time and 0(n ) 3  G  are partial 2-trees.  G is a partial 2-tree i f and  Clearly, the modified algorithm  processors.  The recognition of partial 3-trees which are not necessarily three-connected requires a major modification of Algorithm 5.1, which is developed in the next section.  5.4 NC-Algorithm for Recognizing Partial 3-Trees 76  We develop in this section an NC-algorithm for recognizing a partial 3-tree which is not necessarily 3-connected. The performance of this algorithm is identical to that developed in Section 5 for recognizing and embedding 3-connected partial 3-trees. That is, it requires <3(n ) processors. 4  0(log n)  time and  2  However, its description is somewhat more involved and it depends on some new  separation properties which are developed below. First, we need to introduce a new definition. For two disjoint paths p  = Pi( , i)  and  v s  x  Vi — P ( > ) u  2  s  G = (V,E),  m  2  having only  the vertex v in common, the path p = p(k, 1) will be called a bridge path between p± and p  2  p originates at some node k in py, otherwise vertex disjoint with p  Lemma 5.4.1 of  v  {  and terminates  there exists a vertex  with  Sj, j = 1 , 2 , 3 .  among the paths p(v ,Sj), t  If for j=  G  1,2,3,  implies that if tree.  K  x  with a vertex of  and three disjoint paths  V . Assume that for 2  p(t) ,s ) , i  J  j = 1,2,3,  which is contained in G ( V , U 5 ) , then  and G( V U S ; K(S)) 2  joining  G is contractible to  G( V U S; K(S)) x  G ( ^ U 5 ; ^(5)) , i = 1 , 2 .  and  p(v ,s ) , i  J  j= 1 , 2 , 3 , for i  G( V U S ; #(5)) . Thus, if 2  O n the other hand, L e m m a 5.2.1  G( V U S ; K(S)) , i — 1,2, are partial k-trees then t  G is a partial k-  are partial k-trees.  The existence of a bridge path between some pair of the paths  is a partial k-tree, so are  but p is  i = 1 and 2 there exists a bridge path between a pair of paths  r  = 1 and 2 imply that  v,  2  t  tree if and only if G( V U 5 ; K(S))  Proof:  2  be a separator of G = ( V , E) inducing a partition { Vy, V )  6 V  t  I in p , I ^  2  3  v  at vertex  p .  s}  2  v,  V \ S such that no edge in E connects a vertex in = 1,2  i  and  t  Let S = {s ,s , 1  k ^  if  G must also be a partial k-  0  Lemma 5.4.2  Let S = { s , s , s :  2  3  } be a 3-separator of a 2-connected simple graph  77  G = ( V, E)  which induces a partition {V , V } of x  edge in E connects a vertex i n vertices  v  {  V \ 5 such that 2 < |  2  | < | | V | , t = 1 , 2 , and no  Vy with a vertex i n V . Assume that for i = 1,2 there exist 2  G V,- and three disjoint paths  p(v ,Sj)  , j =  t  1,2,3,  joining  v  t  with vertices in 5 .  If for « = 1 or 2 there exists no bridge path between any pair of paths among the paths p(v ,Sj) , {  j =  1,2,3,  which is contained i n  {1,2} , {v , Sj}  G(V U S) i  then for some  is a separator of G which induces a partition  t  j G {1,2,3}  {V[, V } of 2  and i G  V\{vf,Sj}  such  that j L | y | - 2 < | V / | < l\V\.  Proof:  Assume, without loss of generality, that there is no bridge path between any pair of paths  among the paths s(v),  s(v)  in S \ G(V\  1  G S, and a path from Now, any node  {s(v)}.  {«(*>), %})  p(v,~s(v)), or  to  v  v,  v  Since G is connected, for any s(v),  x  and  p(v,s(v))  and p(v ,~s(v)),  x  E V there exists a node x  ^ v , must be in some connected component of  {s(v)}.  x  Indeed, otherwise there must exist a path,  v to a node ~s(v) , ~s(v) G S \ {«(*>)} , which does not pass through either  But, the paths  p(v ,s(v))  S\  v  v  i n G which does not pass through nodes  p(v,s(v)),  € V and  which does not contain  i n G from  s(v) .  between  1,2,3.  p(v ,Sj),j=  p(v,J(v))  i n G induce a bridge path i n G(V U S) 1  which is a contradiction.  x  Next, for < = 1 , 2 , 3 let C denote, respectively, the union of all connected components of i  G(V\  {*>i,S(})  which do not contain any node i n S\  {s } t  .  We claim that the sets  C ,t G t  { 1 , 2 , 3 } , are mutually exclusive. Indeed, from the 2-connectivity of G and the definition of the sets  C  it follows that i f v G C,- , i G { 1 , 2 , 3 } ,  t  s^) , s G 5 , which does not pass through t  {1,2,3}  and i ^  p(fli,S;)  and  where  j,  p(v!,Sj),  the paths  p(v,s ) {  and  and v 9^ v , then there exists a path x  {v^} U S \ {s,} . Thus, i f v G C,- D Cj , ij G p(v,Sj)  i n G would induce a bridge path between  which is a contradiction. Thus, we have that  V(C ) denotes the set of nodes in C . Let \V(Cj)\ t  t  78  ^ ^ 1 V^C*)! = = 1  1^1-1,  = max{ \ V(C )\ : t = 1 , 2 , 3 } , and t  set  V[ =  V(Cj)  and  and thus, \V[\ >  V' =  V\  -  Clearly,  2  2.  ( F U { t ) , sA) . Since 5 ,  1  1  V(C ) C ^  is a 3-separator, | V \ | > \\V\  , t = 1 , 2 , 3 , and thus \V[\ <  t  -  3  •  We use the above separation results to construct an NC-algorithm for recognizing a partial 3-tree.  Algorithm 5.2 Procedure  Input  REC{ G,  A simple graph  Output  a — 1 if  Step 1  a)  G = (V,  E).  G is a partial 3-tree and a = O otherwise .  Find all biconnected components of G . If G has no biconnected components, set and exit. Otherwise, perform in parallel procedure components  Procedure  G^ = ( V ^ , ^ )  REC\(G,  of G . If any a  t  RECl(G ,  Input  A simple biconnected graph  (V,E).  Output  a = 1 if G is a partial 3-tree and a = 0 otherwise .  Step 0  a = 1.  Step 1  79  a,)  for all biconnected  = 0 set a = 0 and exit.  a)  G =  i  a = 1  (1.1)  If IJE7| > 3n - 6 , set a = 0 and exit  (1.2)  Else, if | V\ < 36 check, in constant time, whether G is a partial 3-tree. If G is  not a partial 3-tree set a = 0. Exit .  Step 2  S — {si,s ,«3}  Else, for each triple of distinct vertices  °f  2  V, in parallel, find all  connected components of G(V \ S) and denote their vertex sets by for some r  ,r , s  > 1.  g  (2.1)  Vf, j =  If\Vf\>  l\V\  for some j =!,••• , r , reject 5. If all triples S are g  rejected, set a = 0 and exit.  (2.2)  Else, if  set Mi = (2.3)  \\V\ < \Vf\ < f | V | for some  ^' '  ^' " ' 5 '  =  r  1  =  5 U  a  n  and for all  S d  a  PPi  v  for  t = 1,2,  z ^  j =  1, • • • , r  s  ( U Vf :j< n) and M  G(M  t  j , z , j € {1,2,3} .  2  G(M  2  (3.2)  C  1 ) 2  #  0 , C  2 ) 3  #  q  t  =  x  \ {*,-,*j})  which do not contain  Denote by  C] j  2  If  , compute  = (V \ M ) U 5 .  connected components, and let C^j = C)^ U C ^ for all {i,j}  (3.1)  $  binary search to find an n for which \ \ V\ <  a  Find, in parallel, connected components of {SJ,SJ}  1 < j < r ,  2  817 < II V| . Set ¥  Step 3  j,  Vf U S a n d Af = ( V \ V ? ) .  Else, for an unrejected  ^><jl  S and for some  0 and  C  0 let  the union of all such  € {1,2,3} , i ^ j •  =  G(M  ; #(5)) and G  two distinct pairs  {i,j}  and  1 ) 3  ^  S\  G  t  X  2  =  ; K(S)).  Else,  if there exist at  U {Pi ?} = {1)2,3} such that  least Cj t  80  = 0 and C ,  P q  {p,q  ^ 0 proceed as follows:  },{i,j}  (a)  inCi, )| +  If  2  \ V(C , )\ \ 5"|,  1^(^1,3)1 <  (b) find U  (3.3)  V\C\j) 2  c  )  S  ,}  ;  t G { 1 , 2 } , | V ( C * ) | + |V(C2,s)l + I K ^ s ) !  components of  1 ) 2  =  3  G  2 ) 3  =  0  and  C  1  3  =  0  find,  t  Vj(v,  s)  , j — 1,  t  m(u,s )  >  t  ••• , m ( u , s ) } , reject the pair t  If all pairs {f,St }, t G { 1,2,3} and  ,,})).  v G K , and denote their  (  ;  G(7(C£,,)  x  in parallel, connected  ••• , m ( u , s ) , for some  |V -(«,Sj)| > Q\V\ for some j, j € {I,  l ^ t \ S\  G = k  G( K \ {s , «}), for all t € { 1 , 2 , 3 } and  vertex sets by  (o)  ) | } and let  k>l  2  0 ,  J ) 3  V(C )) U K , s , } ; K({s ,  and G = G{{V\  t S  C  =  1>a  tf({s , ,}))  Else, if  G ^ - , then  2  2  f  >3  2  is the vertex set of component  I V(C*,i)l = m a * { | V ( C * , ) | , | K ( C i , ) | , | V ( C  {5  | K ( C ? , ) | + |KCS )I +  and G = G(M ; Jf(S)) .  1  Else, if for some  \MAS\ and  3  where  let G = G(M ; K{S)) x  inCi, )l <  +  2 3  1.  If  {f,s }. t  v G V , were rejected let G = G ( M j ; x  K(S)) and G = G(Af ; K(S)) . 2  (6)  2  Else, if =  -  Vj (v,s ) t  G(Af' ; 1  (c)  2 < | 1^ ( v , s ) | for some  U { v,  tf({t;,sj))  G { 1 , ••• , m(v,  t  s  }  t  and  M  and G =  ;  2  Else, for an unrejected pair  =  > 2  V \  compute  t  s) t  set Af^  t  and let  G  q, = ^  t < J  | V , - (v,  s )\,  <||V|.  t  M ! = {*;,«,} U ( U l A 1  GiM , 1  (3.4) =  (»,*,) : j <  ; /£-({!),«,})) and G = G(M  C a l l in parallel  2  RECl^,  a) x  0 set a = 0. Exit.  81  I 2  1;)  M  ,  ;K({v,s }))  and  = (V  l 2  VH\)  I =  t  l , - - - , m(v,s ) , and apply a binary search to find n for which ^ | V\ -2 < Set  =  x  .  tf({i/,6-,}))  {v,s }  Vj (v,  s ))},  U {v,s } t  , G  =  x  .  t  REC1(G , 2  a ). 2  If either  a  x  = 0 or  a  2  Theorem 5.4.1  Algorithm 5.2 recognizes whether a simple graph  G = (V ,E)  with  | V | = n is  a partial 3-tree i n 0(log n) time using 0 ( n ) processes. 2  Proof:  4  W e will first prove the validity of Algorithm 6.1. If, i n Procedure  G is  REC(G,a),  found not to contain biconnected components, then it could be decomposed by zero or one separators into subgraphs of cardinality at most 4 . 5.2.1 implies that  Since every graph on 4 nodes is a partial 3-tree, Lemma  G is a partial 3-tree. The validity of Step 1 i n  in Algorithm 5.1. If all triples were rejected i n Step 2 , Theorem 3.1, G is not a partial 3-tree. In Step 3, i f C j ^ t  biconnectivity of  0 for some  G  t  a)  was explained  does not contain a 3-separator and by  Otherwise, i n Step 2 algorithm 5.2 finds a 3-separator. i ^ j, then  {SJ,SJ}  G and Lemma 5.2.2 it follows that  augmented with edge (s ,Sj)  REC1(G,  is a separator of G, and by the  G is a partial 3-tree i f and only i f G  is a partial 3-tree. T h u s , by L e m m a 5.2.3, i f (3.1) holds, then G  is a partial 3-tree i f and only i f G{M ; K(S)) and G(M ; K(S)) are partial 3-trees. If (3.2) holds X  then, by L e m m a 5.2.2, we can augment must exist vertices G(M ) i  , i=l,2.  G(M ),  v, t  2  G with edge  (p,q).  v G M \ S , i = l , 2 , and three disjoint paths from t  t  Thus, by Lemma 5.4.1, since  (p,q )  v to a l l s G S in {  is a bridge path both i n  G(M ) 1  and  G is a partial 3-tree i f and only i f G(M ; K(S)) and G(M ; K(S)) are partial 3-trees.  2  1  2  On the other hand, i f 3.2b) holds then, by Lemma 5.2.2, G(V(Ci,,)  U{  s , s, k  } ; A'({ s , s,})) and G((V\ k  trees. If (3.3) holds, then for each in  Therefore, i f 3.2a) is valid, there  G(M ) from {  i = 1,2  G  is a partial 3-tree i f and only i f  1^,,)) U  and for each  ; K({s ,s,})) k  v GM  {  are partial 3-  there exist three disjoint paths  v to all nodes i n S . Therefore, by Lemma 5.4.2, i f all pairs are rejected i n 3.3a),  there must exist a bridge path both in GiMy)  and G(M ) 2  82  satisfying the stipulations i n Lemma  5.4.2 . Then, by G(M  2  G(M  1  I  Lemma 5.4.1,  G  is a partial 3-tree if and only if  G(M ; K(S)) X  and  ; K(S)) are partial 3-trees. Otherwise, by Lemma 5.2.2, G is a partial 3-tree if and only if ; K({ v, s })) and G(Af* 5 ^({v,s })) t  2  a  r  partial 3-trees.  e  t  Next, we will show that algorithm 5.2 requires  0(log n)  time using 0 ( n ) processors. A l l  2  4  biconnected components can be found in Step 0, using the parallel algorithm of Tarjan and Vishkin (1985), in O(logn)  time using 0(n)  processors. In Step 1, (1.2) can be carried out in constant  time using, for example, the sequential algorithm for recognizing partial 3-trees of Arnborg and Proskurowski (1986). The connected components in Step 2 can be found by the parallel algorithm of Shiloach and Vishkin (1982) in 0(n ) 3  triples  S  1  O(logn)  time using 0(n )  which do not contain  5\{s,-,s^}  processors, and since there are O(logn)  time and  G (V\  0(n)  0(n ) 2  pairs  and q^ >  Step 3.2b)  O(logn)  Since there are time and  In Step 3, connected components of  0(n ) 4  O(logn)  time using  t  O(n)  processors.  can be found in  {s , v)  to be considered simultaneously, Step (3.3)  t  t  processors.  Further, 3.3c) takes  | K (CX )| >  in (2.3)  O(logn)  G(M \ {s;,Sj})  {s , v})  processors. Finally, observe that in (2.2) | V ? | > | | F | , 3-separator, in  processors.  Step 2 requires  can be found in  Similarly, connected components of  0(n + m)  processors to compute, in Step 2.3, partial sums  2  and perform a binary search on them.  requires  time with  to be considered simultaneously,  processors. It takes q  O(logn)  O(logn)  q„ > \\V\  V\ — 2 . Therefore, we can have at most  O(logn)  algorithm 5.2 would terminate in 0(log n) time using 0(n ) 2  4  83  time using  s )\ t  > ±\V\  nested calls of RECl(G,a),  processors.  0(n)  0(n ) 2  a n d , since S is a  Further, in Step 3.3, \ Vj{v,  jf  time using  •  - 2 and  Bibliography A . V . Aho, J.E. Hopcroft and J.D. Ullman, "The Design and Analysis of Computer Algorithms," Addison- Wesley, Reading, 1974 S. Arnborg, Transactions  "Reduced State Enumeration: Another on Reliability 27 (1978), 101-105.  Algorithm  for  Reliability  Evaluation,'"  IEEE  S. Arnborg, " O n the Complexity of Multivariable Query Evaluation," F O A Rapport C 20292-D8, National Defence Research Institute, Stockholm, Sweden (1979). S. Arnborg, "Efficient Algorithms for Combinatorial Decomposability - A Survey," BIT 25 (1985), 2-33.  Problems  on  Graphs  with  Bounded  S. Arnborg, D . G . Corneil and A . Proskurowski, "Complexity of Finding Embeddings in a k-tree," SIAM Journal on Algebraic and Discrete Methods 8 (1987), 277-284. S. Arnborg and A . Proskurowski, "Characterization and Recognition of Partial k-Trees," Numerantium, 47 (1985), 69-75  Congressus  S. Arnborg and A . Proskurowski, "Characterization and Recognition of Partial 3-trees," SIAM on Algebraic and Discrete Methods 7 (1986), 305-314.  Journal  S. Arnborg and A . Proskurowski, "Linear Time Algorithms for NP-hard Problems on Graphs Embedded in k-trees," Discrete Applied Mathematics 23 (1989) 11-24. S. Arnborg, A . Proskurowski and D . Corneil, "Forbidden Minors Characterizations of Partial 3-trees," CIS-TR-86-07, University of Oregon, July 1986. N . W . Bern, E . L . Lawler and A . L . Wong, " W h y Certain Subgraph Computations Require Only Linear Time," Proc. 26th Ann. IEEE Symp. on Foundations of Computer Science (1985), 117-125. C . Berge, "Graphs," 2 USA, 1985.  n d  revised edition Amsterdam,  North Holland Publishing  Company,  NY,  NY,  C . Bird, " O n Cost Allocation for a Spanning Tree: A Game Theoretic Approach," Networks 6 (1976), 335-350. H . L . Bodlaender, "Classes of Graphs W i t h Bounded Tree-Width," Utrecht, The Netherlands, November 1986.  RUU-CS-86-22, Rijksuniversiteit  H . L . Bodlaender, "NC-Algorithms for graphs with small treewidth," RUV-CS-88-4, Rijksuniversiteit Utrecht, The Netherlands, February 1988. N . Chandrasekharan and S.S. Iyengar, " N C Algorithms for Recognizing Chordal Graphs and k-Trees," Technical Report 86-020, Department of Computer Science, Louisiana State University, 1986. C . J . Colbourn and A . Proskurowski, "Concurrent Transmission in Broadcast Networks," Proc. Conf. Automata, Languages, Programming, Springer-Verlag L N C S 172 (1984), 128-136.  84  Int.  :  D . G . Corneil and J . M . K e i l , " A Dynamic Programming Approach to the Dominating Set Problem on k-Trees," SIAM Journal on Algebraic and Discrete Methods 8 (1987), 535-543. D . G . Corneil and Y . P e r l , "Clustering and Mathematics 9 (1984), 27-39  Domination in Perfect  Graphs,"  Discrete  Applied  G.Cornuejols, J.Fonlupt and D.Naddef, "The traveling Salesman Problem and Some Related Integer Polyhedra," Mathematical Programming 33 (1985), 1-27 A . Edenbrandt, "Combinatorial Problems University, Ithaca, N Y , July 1985.  in Matrix  Computation,"  P h . D . Thesis  at  Cornell  A . M . Farley, "Networks Immune to Isolated Failures," Networks 11 (1981), 255-268. A . M . Farley and A . Proskurowski, "Networks Immune to Isolated Line Failures," Networks 12 (1982), 393-403. L . R . Ford Jr. and D . R . Fulkerson, "Flows in Networks," Princeton 1962.  University Press, Princeton  S. Fortune and J . Wyllie, "Parallelism in Random Access Machines," Proceedings ACM Symposium on Theory of Computing, (1978) 114-118.  of the 10th  N.J.  Annual  M . C . Golumbic, "Algorithmic Graph Theory and Perfect Graphs," Academic Press, New York, 1980. M . R . Garey and D.S. Johnson, Computers Completeness, Freeman, San Francisco (1979).  and Intractability:  A  Guide to the  Theory of NP-  F. G a v r i l , "Algorithms for M i n i m u m Coloring, M a x i m u m Clique, M i n i m u m Coloring by Cliques and M a x i m u m Independent Set of a Chordal G r a p h , " SIAM Journal on Computing 1 (1972) 180-187. D . Granot, " A Generalized Linear Production Model: A Unifying Model," Mathematical 34 (1986), 212-223.  Programming  D. Granot and F . Granot, " A Fixed-Cost Spanning-Forest Problem," University of British Columbia, Working Paper No. 1235, March 1987. D. Granot and G . Huberman, " M i n i m u m Cost Spanning Tree Games," Mathematical (1981) 1-18.  Programming  21  S.L. Hakimi and A . T . A m i n , " O N the Design of Reliable Networks," Networks 3 (1973), 241-260 G. Y. Handler, "Minimal 287-293.  Location of a Facility in an Undirected Tree Graph,"  Transp. Sc. 7 (1973),  F . Harary, " G r a p h Theory," Addison Wesley, Reading, Mass., 1969. R. Hassin and A . T a m i r , "Efficient Algorithms for Optimization and Selection on Series-Parallel Graphs," SIAM Journal on Algebraic and Discrete Methods 7 (3), July 1986, 379-389. D.S. Johnson, "The NP-Completeness Column: A n Ongoing Guide," Journal of Algorithms 434-451. 85  6 (1985),  A . Kolen and A . T a m i r , "Covering Problems" Chapter 6. in Discrete Location and D . B . Mirchandani, eds., John Wiley, New York (forthcoming). S.C. Littlechild, " A Simple Expression for the Nucleolus in a Special Case", Game Theory 3 (1974), 21-29.  Theory, L . R . Francis  International  Journal on  N . Megiddo, "Computational Complexity and the Game Theory Approach to Cost Allocation for a Tree", Mathematics of O.R. 3 (1978), 189-196. B . Monien and I . H . Sudborough, "Bandwidth-Constrained NP-complete Problems," Proceedings of the 13th Annual ACM Symposium on Theory of Computing, New York (1981), 207-217. E . M . Neufeldt and C . J . Colbourn, "The Most Reliable Series-Parallel Networks," Dept. of Computer Science, University of Saskatchewan, TR83-7 (1983). C . H . Papadimitriou and K . Steiglitz, "Combinatorial Optimization Algorithms and Complexity," Prentice Hall, Inc., 1982. N . Pippenger, " O n Simultaneous Resource Bounds," Proc. 20th Ann. IEEE Symp. on Foundations Computer Science (1979), 307-311.  of  A . Prodon, M . Liebling and H . Grb'flin, "Steiner's Problem on Two-Trees," R O 850315, Department of Mathematics, E P F Lausanne, Switzerland, March 1985. A . Proskurowski, "Separating Subgraphs in k-trees: Cables and 49 (1984), 275-285.  Caterpillars," Discrete  Mathematics  R . L . Rardin, R . G . Parker and M . B . Richey, " A Polynomial Algorithm for a Class of Steiner Tree Problems on Graphs, " I S Y E Report Series J-82.5, Georgia Tech., August 1982. N . Robertson and P . D . Seymour, " G r a p h Minors II: Algorithmic Aspects of Tree W i d t h , " Algorithms 7 (1986), 309-322. N . Robertson and P . D . Seymour, "Disjoint paths - A survey," SIAM Discrete Methods 6 (1985), 300-305. D . J . Rose, " O n Simple Characterizations of k-Trees," Discrete Mathematics  Journal  on  Journal of  Algebraic  and  7 (1974), 317-322.  J . C . Sheperdson and H . E . Sturgis/'Computability of Recursive Functions," Journal of the ACM 10, (1963), 217- 255 Y . Shiloach and U . Vishkin, " A n O(logn) Parallel Connecting A l g o r i t h m , " Journal of Algorithms (1982), 57-67.  3  K . Takamizawa, T . Nishizeki and N . Saito, "Linear-Time Computability of Combinatorial Problems on Series-Parallel Graphs," Journal of the ACM 29 (1982), 623-641. R . E . Tarjan and U . Vishkin, " A n Efficient Parallel Biconnectivity A l g o r i t h m , " SIAM Computing 14 (1985), 862-874. 86  Journal  on  P . Tseng, "Parallel Computation for Edge Weighted Network Problems on Series-Parallel Graphs," Working Paper #1240 , University of British Columbia, December 1987. J . Valdez, R . E . Tarjan and E . L . Lawler, "The Recognition of Series-Parallel Digraphs," SIAM on Computing 11 (1982), 298-313.  Journal  U . Viskin, "Implementation of Simultaneous-Memory Access in Models That Forbid It," Journal of Algorithms 4, (1983), 45-50 A . W a l d and C . J . Colbourn, "Steiner Trees, Partial 2-trees, and M i n i m u m IFI Networks," Networks 13 (1983), 159-167.  87  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0098333/manifest

Comment

Related Items