On the problem of packing Steiner trees of a graph
Item
-
Title
-
On the problem of packing Steiner trees of a graph
-
Identifier
-
d_2009_2013:e8ba71173f19:10514
-
identifier
-
10686
-
Creator
-
Talafha, Mohammad T.,
-
Contributor
-
LOUIS PETINGI
-
Date
-
2010
-
Language
-
English
-
Publisher
-
City University of New York.
-
Subject
-
Computer science
-
Abstract
-
Let G = (V, E) be an undirected graph with vertex-set V, edge-set E, and a subset of distinguished terminal vertices K of V, where |K| ≥ 2 (the vertices in V -- K are called the non-terminal vertices). The degree of a vertex nu of G is the number of edges incident at nu in G. A K-Steiner tree T of G is a tree containing the terminal vertex-set K, and any vertex of degree one in T must belong to K. The K-edge-connectivity, denoted as lambdaK(G), of a connected graph G with terminal vertex-set K, is the minimum number of edges whose removal from G disconnects at least two vertices of K..;The Steiner Tree Packing problem (STPP for short) is the problem of finding the maximum number of edge-disjoint K-Steiner trees, tK(G), contained in G. Specifically, in this thesis, we are interested in finding a lower bound on tK(G) with respect to the K-edge-connectivity, lambdaK(G).;The Steiner Tree Packing problem has attracted considerable attention from many researchers in different areas because of its wide applicability. It has applications in routing problems arising in VLSI circuit design, where an effective way of sharing different signals among cells in a circuit can be achieved by the use of edge-disjoint Steiner trees. It also has a variety of computer network applications such as multicasting, video-conferencing, and network information flow where simultaneous communications can be facilitated by using edge-disjoint Steiner trees.;In 2003, Kriesell conjectured that any graph G = ( V, E) with terminal vertex-set K ⊆ V has at least &fll0; lambdaK(G) / 2 &flr0; edge-disjoint K-Steiner trees. In this thesis we give a background on this problem and we present most of the major results obtained so far. Moreover, we show that Kriesell's conjecture can be answered affirmatively if the edges of G can be partitioned into K-Steiner trees. This result yields bounds for the problem of packing K-Steiner trees with certain intersection properties in a graph. In addition we show that for any graph G with terminal vertex-set K, tK(G) ≥ &fll0; lambdaK(G) / 2 &flr0; - |V -- K| / 2 - 1. Moreover, we study a vulnerability index called the edge-toughness, which connects the connectivity of a network with the problem of packing Steiner trees of a graph.
-
Type
-
dissertation
-
Source
-
2009_2013.csv
-
degree
-
Ph.D.
-
Program
-
Computer Science
