Algorithms for Fundamental Problems in Computer Networks.

Show simple item record Su, Hsin-Hao en_US 2015-09-30T14:24:19Z NO_RESTRICTION en_US 2015-09-30T14:24:19Z 2015 en_US 2015 en_US
dc.description.abstract Traditional studies of algorithms consider the sequential setting, where the whole input data is fed into a single device that computes the solution. Today, the network, such as the Internet, contains of a vast amount of information. The overhead of aggregating all the information into a single device is too expensive, so a distributed approach to solve the problem is often preferable. In this thesis, we aim to develop efficient algorithms for the following fundamental graph problems that arise in networks, in both sequential and distributed settings. Graph coloring is a basic symmetry breaking problem in distributed computing. Each node is to be assigned a color such that adjacent nodes are assigned different colors. Both the efficiency and the quality of coloring are important measures of an algorithm. One of our main contributions is providing tools for obtaining colorings of good quality whose existence are non-trivial. We also consider other optimization problems in the distributed setting. For example, we investigate efficient methods for identifying the connectivity as well as the bottleneck edges in a distributed network. Our approximation algorithm is almost-tight in the sense that the running time matches the known lower bound up to a poly-logarithmic factor. For another example, we model how the task allocation can be done in ant colonies, when the ants may have different capabilities in doing different tasks. The matching problems are one of the classic combinatorial optimization problems. We study the weighted matching problems in the sequential setting. We give a new scaling algorithm for finding the maximum weight perfect matching in general graphs, which improves the long-standing Gabow-Tarjan's algorithm (1991) and matches the running time of the best weighted bipartite perfect matching algorithm (Gabow and Tarjan, 1989). Furthermore, for the maximum weight matching problem in bipartite graphs, we give a faster scaling algorithm whose running time is faster than Gabow and Tarjan's weighted bipartite {it perfect} matching algorithm. en_US
dc.language.iso en_US en_US
dc.subject algorithms en_US
dc.subject distributed computing en_US
dc.subject graph theory en_US
dc.title Algorithms for Fundamental Problems in Computer Networks. en_US
dc.description.thesisdegreename PhD en_US
dc.description.thesisdegreediscipline Computer Science and Engineering en_US
dc.description.thesisdegreegrantor University of Michigan, Horace H. Rackham School of Graduate Studies en_US
dc.contributor.committeemember Pettie, Seth en_US
dc.contributor.committeemember Gilbert, Anna Catherine en_US
dc.contributor.committeemember Schoenebeck, Grant en_US
dc.contributor.committeemember Wattenhofer, Roger en_US
dc.subject.hlbsecondlevel Computer Science en_US
dc.subject.hlbtoplevel Engineering en_US
dc.owningcollname Dissertations and Theses (Ph.D. and Master's)
 Show simple item record

This item appears in the following Collection(s)

Search Deep Blue

Advanced Search

Browse by

My Account


Coming Soon

MLibrary logo