Distributed graph coloring: Fundamentals and recent developments
L Barenboim, M Elkin - 2013 - books.google.com
Page 1 MORGAN & CLAYPOOL PUBLISHERS Distributed Graph Coloring Fundamentals and
Recent Developments Leonid Barenboim Michael Elkin HESIS SYNTHESIS LECTURES ON …
Recent Developments Leonid Barenboim Michael Elkin HESIS SYNTHESIS LECTURES ON …
The locality of distributed symmetry breaking
Symmetry-breaking problems are among the most well studied in the field of distributed
computing and yet the most fundamental questions about their complexity remain open. In …
computing and yet the most fundamental questions about their complexity remain open. In …
Fast hybrid network algorithms for shortest paths in sparse graphs
M Feldmann, K Hinnenthal, C Scheideler - arXiv preprint arXiv …, 2020 - arxiv.org
We consider the problem of computing shortest paths in hybrid networks, in which nodes
can make use of different communication modes. For example, mobile phones may use ad …
can make use of different communication modes. For example, mobile phones may use ad …
Fully Dynamic (Δ +1)-Coloring in O(1) Update Time
The problem of (Δ+ 1)-vertex coloring a graph of maximum degree Δ has been extremely
well studied over the years in various settings and models. Surprisingly, for the dynamic …
well studied over the years in various settings and models. Surprisingly, for the dynamic …
Distributed computation in node-capacitated networks
In this paper, we study distributed graph algorithms in networks in which the nodes have a
limited communication capacity. Many distributed systems are built on top of an underlying …
limited communication capacity. Many distributed systems are built on top of an underlying …
Graph coloring via degeneracy in streaming and other space-conscious models
We study the problem of coloring a given graph using a small number of colors in several
well-established models of computation for big data. These include the data streaming …
well-established models of computation for big data. These include the data streaming …
Built-in self-test of configurable logic blocks in Virtex-5 FPGAs
BF Dutton, CE Stroud - 2009 41st Southeastern Symposium on …, 2009 - ieeexplore.ieee.org
A built-in self-test (BIST) approach is presented for the configurable logic blocks (CLBs) in
Xilinx Virtex-5 field programmable gate arrays (FPGAs). A total of 17 configurations were …
Xilinx Virtex-5 field programmable gate arrays (FPGAs). A total of 17 configurations were …
Feluca: A two-stage graph coloring algorithm with color-centric paradigm on gpu
There are great challenges in performing graph coloring on GPU in general. First, the long-
tail problem exists in the recursion algorithm because the conflict (ie, different threads assign …
tail problem exists in the recursion algorithm because the conflict (ie, different threads assign …
Simple and near-optimal distributed coloring for sparse graphs
M Ghaffari, C Lymouri - arXiv preprint arXiv:1708.06275, 2017 - arxiv.org
Graph coloring is one of the central problems in distributed graph algorithms. Much of the
research on this topic has focused on coloring with $\Delta+ 1$ colors, where $\Delta …
research on this topic has focused on coloring with $\Delta+ 1$ colors, where $\Delta …
Approximating the Arboricity in Sublinear Time∗
T Eden, S Mossel, D Ron - Proceedings of the 2022 Annual ACM-SIAM …, 2022 - SIAM
We consider the problem of approximating the arboricity of a graph G=(V, E), which we
denote by arb (G), in sublinear time, where the arboricity of a graph is the minimal number of …
denote by arb (G), in sublinear time, where the arboricity of a graph is the minimal number of …