Abstract
dc:description.abstractThe work in this thesis can be divided into two different parts. In the first part, we suggest an approximate edge 3-coloring polynomial time algorithm for cubic graphs. For any cubic graph with n vertices, using this coloring algorithm, we get an edge 3-coloring with at most n/3 error vertices. In the second part, we study Jim Propp's Rotor-Router model on some non-bipartite graph. We find the difference between the number of chips at vertices after performing a walk on this graph using Propp model and the expected number of chips after a random walk. It is known that for line of integers and d-dimenional grid, this deviation is constant. However, it is also proved that for k-ary infinite trees, for some initial configuration the deviation is no longer a constant and say it is D. We present a similar study on some non-bipartite graph constructed from k-ary infinite trees and conclude that for this graph with the same initial configuration, the deviation is almost (k²)D.
Degree
thesis:*- Department dc:contributor.department
- Computing
- Grantor dc:publisher
- Georgia Institute of Technology
- Year dc:date.issued
- 2008
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Gajewar, Amita Surendra
- Advisor dc:contributor.advisor
-
- Lipton, Richard J.
- Committee members dc:contributor.committeemember
-
- Basu, Sumit
- Bobick, Aaron
- Ellis, Dan
- Isbell, Charles
- Weinberg, Gil
Subjects
dc:subject × 6Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/1853/29735