Now showing items 1-5 of 5

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

      Panconesi, Alessandro; Srinivasan, Aravind (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 

      Panconesi, Alessandro (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 

      Panconesi, Alessandro; Srinivasan, Aravind (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 

      Panconesi, Alessandro; Ranjan, Desh (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 

      Panconesi, Alessandro; Srinivasan, Aravind (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 ...