1
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Towards the Locality of Vizing's Theorem

      Preprint

      ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          Vizing showed that it suffices to color the edges of a simple graph using \(\Delta + 1\) colors, where \(\Delta\) is the maximum degree of the graph. However, up to this date, no efficient distributed edge-coloring algorithms are known for obtaining such a coloring, even for constant degree graphs. The current algorithms that get closest to this number of colors are the randomized \((\Delta + \tilde{\Theta}(\sqrt{\Delta}))\)-edge-coloring algorithm that runs in \(\text{polylog}(n)\) rounds by Chang et al. (SODA '18) and the deterministic \((\Delta + \text{polylog}(n))\)-edge-coloring algorithm that runs in \(\text{poly}(\Delta, \log n)\) rounds by Ghaffari et al. (STOC '18). We present two distributed edge-coloring algorithms that run in \(\text{poly}(\Delta,\log n)\) rounds. The first algorithm, with randomization, uses only \(\Delta+2\) colors. The second algorithm is a deterministic algorithm that uses \(\Delta+ O(\log n/ \log \log n)\) colors. Our approach is to reduce the distributed edge-coloring problem into an online, restricted version of balls-into-bins problem. If \(\ell\) is the maximum load of the bins, our algorithm uses \(\Delta + 2\ell - 1\) colors. We show how to achieve \(\ell = 1\) with randomization and \(\ell = O(\log n / \log \log n)\) without randomization.

          Related collections

          Most cited references 10

          • Record: found
          • Abstract: not found
          • Article: not found

          Locality in Distributed Graph Algorithms

           Nathan Linial (1992)
            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            Balls and bins: A study in negative dependence

              Bookmark
              • Record: found
              • Abstract: not found
              • Article: not found

              Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds

                Bookmark

                Author and article information

                Journal
                02 January 2019
                Article
                1901.00479

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                Custom metadata
                cs.DS cs.DC

                Data structures & Algorithms, Networking & Internet architecture

                Comments

                Comment on this article