 Library Home /
 Search Collections /
 Open Collections /
 Browse Collections /
 UBC Theses and Dissertations /
 On some problems on ktrees and partial ktrees
Open Collections
UBC Theses and Dissertations
UBC Theses and Dissertations
On some problems on ktrees and partial ktrees SkorinKapov, Darko
Abstract
The objective of this thesis is to investigate some structural and algorithmic properties of ktrees and partial ktrees. A ktree can be constructed from a kcomplete graph by recursively adding a new vertex which is adjacent to all vertices of an existing kcomplete subgraph. Partial ktrees are graphs embeddable in a ktree with the same vertex set. They are natural generalizations of forests and seriesparallel graphs which are the first two members of the hierarchy of partial ktrees. The many applications of ktrees and partial ktrees have motivated their study from both an algorithmic and a theoretical point of view. For example, ktrees arise in reliable communication network design problems (Farley (1981), Farley and Proskurowski (1982), Neufeld and Colbourn (1983), Wald 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 ktrees is special in the sense that many problems, which are NPcomplete for arbitrary graphs, are solvable in polynomial time when restricted to ktrees or partial ktrees (Arnborg and Proskurowski (1989)). In Chapter 2 of the thesis we analyze a fixed cost spanning forest (FCSF) 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 FCSF problem when the customers and potential facilities' sites are located on a seriesparallel network or, equivalently, a partial 2tree. 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 ktree can be reduced to the kcomplete graph by sequentially removing kdegree vertices with completely connected neighbors. We use this reduction process to develop, in Chapter 3, efficient algorithms for several optimization problems on ktrees and partial ktrees. In particular, we develop a linear time algorithm to find shortest simple paths from a given vertex to all other vertices in a ktree, we compute the diameter of a ktree with equal edge lengths in linear time, and we construct an O(n[sup k+2]) algorithm to solve the Simple Plant Location problem in an nvertex partial ktree. In Chapter 4 we present a new characterization of a kpath between two vertices u and v, in an equal weight ktree 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+1 cliques in a ktree. We use it to develop an O(n²) algorithm to decompose a vertex set V of a ktree G to a minimum 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 kcable diameter of a ktree with equal edge lengths in linear time. In Chapter 5 we derive some separation properties of partial ktrees and use them to develop NC algorithms for recognizing partial 2trees and 3trees. Explicitly, we prove the existence of a kseparator in a partial ktree graph and construct a linear time algorithm that finds such a separator in ktrees. This algorithm can be used to obtain a balanced binary decomposition of a ktree in 0(n log n) time. We derive some other separation properties of partial ktrees and use them to construct a balanced decomposition of an embedding of a kconnected partial ktree when k = 2 and 3. Finally, we construct NC algorithms for the recognition of a partial ktree for k  2 and 3, which run in O(log²n) time using, respectively, O(n³) and O(n⁴) processors.
Item Metadata
Title 
On some problems on ktrees and partial ktrees

Creator  
Publisher 
University of British Columbia

Date Issued 
1989

Description 
The objective of this thesis is to investigate some structural and algorithmic properties of ktrees and partial ktrees. A ktree can be constructed from a kcomplete graph by recursively adding a new vertex which is adjacent to all vertices of an existing kcomplete subgraph. Partial ktrees are graphs embeddable in a ktree with the same vertex set. They are natural generalizations of forests and seriesparallel graphs which are the first two members of the hierarchy of partial ktrees. The many applications of ktrees and partial ktrees have motivated their study from both an algorithmic and a theoretical point of view. For example, ktrees arise in reliable communication network design problems (Farley (1981), Farley and Proskurowski (1982), Neufeld and Colbourn (1983), Wald 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 ktrees is special in the sense that many problems, which are NPcomplete for arbitrary graphs, are solvable in polynomial time when restricted to ktrees or partial ktrees (Arnborg and Proskurowski (1989)).
In Chapter 2 of the thesis we analyze a fixed cost spanning forest (FCSF) 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 FCSF problem when the customers and potential facilities' sites are located on a seriesparallel network or, equivalently, a partial 2tree. 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 ktree can be reduced to the kcomplete graph by sequentially removing kdegree vertices with completely connected neighbors. We use this reduction process to develop, in Chapter 3, efficient algorithms for several optimization problems on ktrees and partial ktrees. In particular, we develop a linear time algorithm to find shortest simple paths from a given vertex to all other vertices in a ktree, we compute the diameter of a ktree with equal edge lengths in linear time, and we construct an O(n[sup k+2]) algorithm to solve the Simple Plant Location problem in an nvertex partial ktree.
In Chapter 4 we present a new characterization of a kpath between two vertices u and v, in an equal weight ktree 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+1 cliques in a ktree. We use it to develop an O(n²) algorithm to decompose a vertex set V of a ktree G to a minimum 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 kcable diameter of a ktree with equal edge lengths in linear time.
In Chapter 5 we derive some separation properties of partial ktrees and use them to develop NC algorithms for recognizing partial 2trees and 3trees. Explicitly, we prove the existence of a kseparator in a partial ktree graph and construct a linear time algorithm that finds such a separator in ktrees. This algorithm can be used to obtain a balanced binary decomposition of a ktree in 0(n log n) time. We derive some other separation properties of partial ktrees and use them to construct a balanced decomposition of an embedding of a kconnected partial ktree when k = 2 and 3. Finally, we construct NC algorithms for the recognition of a partial ktree for k  2 and 3, which run in O(log²n) time using, respectively, O(n³) and O(n⁴) processors.

Genre  
Type  
Language 
eng

Date Available 
20101018

Provider 
Vancouver : University of British Columbia Library

Rights 
For noncommercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.

DOI 
10.14288/1.0098333

URI  
Degree  
Program  
Affiliation  
Degree Grantor 
University of British Columbia

Campus  
Scholarly Level 
Graduate

Aggregated Source Repository 
DSpace

Item Media
Item Citations and Data
Rights
For noncommercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.