Abstract:
Numerous applications of resource partitioning have been found in electrical power distribution
systems, telecommunication networks, computer networks, fault tolerant systems,
grid computing etc. The resource partitioning problem is concerned with finding
a k-resource partitioning of a given graph. In this problem, given a connected graph
G = (V, E), k distinct base vertices UI, U2, ... ,Uk E V, a set 11;. <;;; V of T special vertices
called resource vertices and k natural numbers TI,T2, ... , Tk such that L::~ITi = T, we
wish to find a partition VI, V2, ... , Vk of the vertex set V such that V; contains Ui along
with T, resource vertices, V; induces a connected subgraph of G for each 'i, 1 ::; i ::;k. In
this thesis we present linear-time algorithms for computing a resource tripartition of a
3-connected planar graph and a resource four-partition of a 4-connected planar graph. To
solve the resource tripartitioning problem, we have developed a linear-time algorithm for
constructing a. nonseparating em decomposition through two vertices a, b and avoiding a
third vertex c of a 3-connected graph G for 3J'Y three vertices a, b, c. We also give bounds
on the number of ears and the length of an ear for the nonscparating ear decomposition
produced by our algorithm.
