| Title: | Approximate edge 3-coloring of cubic graphs |
| Author: | Gajewar, Amita Surendra |
| Abstract: | The 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. |
| Type: | Thesis |
| URI: | http://hdl.handle.net/1853/29735 |
| Date: | 2008-07-10 |
| Publisher: | Georgia Institute of Technology |
| Subject: |
Deterministic random walk
Cubic graphs Edge 3-coloring Propp model Graph coloring Graph algorithms |
| Department: | Computing |
| Advisor: | Committee Chair: Prof. Richard Lipton; Committee Member: Prof. Dana Randall; Committee Member: Prof. H. Venkateswaran |
| Degree: | M.S. |
| Files | Size | Format | View |
|---|---|---|---|
| gajewar_amita_s_200808_mast.pdf | 184.3Kb |
View/
|
