Loading...
Please wait, while we are loading the content...
Similar Documents
Routing, Disjoint Paths, and Classification (CMU-PDL-06-109)
| Content Provider | Semantic Scholar |
|---|---|
| Author | Zhou, Shuheng |
| Copyright Year | 2006 |
| Abstract | In this thesis, we study two classes of problems: routing and classification. Routing problems include those that concern the tradeoff between routing table size and short-path forwarding (Part I), and the classic Edge Disjoint Paths problem (Part II). Both have applications in communication networks, especially in overlay network, and in large and high-speed networks, such as optical networks. The third part of this thesis concerns a type of classification problem that is motivated by a computational biology problem, where it is desirable that a small amount of genotype data from each individual is sufficient to classify individuals according to their populations of origin. In hierarchical routing, we obtain “near-optimal” routing table size and path stretch through a randomized hierarchical decomposition scheme in the metric space induced by a graph. We say that a metric X d has doubling dimension dim X at most α if every set of diameter D can be covered by 2α sets of diameter D 2. (A doubling metric is one whose doubling dimension dim X is a constant.) For a connected graph G, whose shortest path distances dG induce the doubling metric X dG , we show how to perform 1 τ -stretch routing on G for any 0 τ 1 with routing tables of size at most α τ O α log∆ logδ bits with only α τ O α log∆ entries, where ∆ is the diameter of G and δ is the maximum degree of G. Hence, the number of routing table entries is just τ O 1 log∆ for doubling metrics. The Edge Disjoint Paths (EDP) problem in undirected graphs refers to the following: Given a graph G with n nodes and a set T of pairs of terminals, connect as many terminal pairs as possible using paths that are mutually edge disjoint. This leads to a variety of classic NP-complete problems, for which approximabil- |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://repository.cmu.edu/cgi/viewcontent.cgi?article=1034&context=pdl |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
