Now showing items 1-5 of 5

• #### The Local Nature of $\Delta$-Coloring and Its Algorithmic Applications ﻿

(Cornell University, 1992-09)
Given a connected graph $G$ = ($V,E$) with $\mid$V$\mid$ = $n$ and maximum degree $\Delta$ such that $G$ is neither a complete graph nor an odd cycle, Brooks' theorem states that $G$ can be colored with $\Delta$ colors. ...
• #### Locality in Distributed Computing ﻿

(Cornell University, 1993-06)
The topic of this thesis is the issue of locality in distributed computing. A first set of results in this thesis concerns the $\Delta$-vertex coloring problem. They are all based on the following result. Let $G$ be a ...
• #### On the Complexity of Distributed Network Decomposition ﻿

(Cornell University, 1993-06)
In this paper, we improve the bounds for computing a network decomposition, which is a basic notion in distributed graph algorithms, distributively and deterministically. Our algorithm computes an \$(n^{\epsilon(n)},(n ...
• #### Quantifiers and Approximation ﻿

(Cornell University, 1989-11)
We investigate the relationship between logical expressibility of NP optimization problems and their approximation properties. First such attempt was made by Papadimitriou and Yannakakis, who defined the class of NPO ...
• #### Randomized Distributed Edge Coloring via an Extension of the Chernoff-Hoeffding Bounds ﻿

(Cornell University, 1993-06)
Certain types of routing, scheduling and resource allocation problems in a distributed setting can be modeled as edge coloring problems. We present fast and simple randomized algorithms for edge coloring a graph, in the ...