Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs
From MaRDI portal
Publication:5092380
DOI10.4230/LIPIcs.MFCS.2019.21OpenAlexW2970277130MaRDI QIDQ5092380
Christian Konrad, Victor Zamaraev
Publication date: 21 July 2022
Full work available at URL: https://doi.org/10.4230/LIPIcs.MFCS.2019.21
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An optimal maximal independent set algorithm for bounded-independence graphs
- Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
- Low diameter graph decompositions
- The local nature of \(\Delta\)-coloring and its algorithmic applications
- Tree-decompositions with bags of small diameter
- Deterministic (Δ + 1)-Coloring in Sublinear (in Δ) Time in Static, Dynamic and Faulty Networks
- On the Locality of Some NP-Complete Problems
- The Locality of Distributed Symmetry Breaking
- A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation
- Fast Distributed Approximations in Planar Graphs
- Leveraging Linial’s Locality Limit
- Deterministic coin tossing with applications to optimal parallel list ranking
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- Parallel Symmetry-Breaking in Sparse Graphs
- Power of Natural Semijoins
- Locality in Distributed Graph Algorithms
- An Improved Distributed Algorithm for Maximal Independent Set
- A Time Hierarchy Theorem for the LOCAL Model
- On the complexity of local distributed graph problems
- Reducibility among Combinatorial Problems
- A new technique for distributed symmetry breaking
- Brief Announcement
- Distributed Coloring in Sparse Graphs with Fewer Colors
- Improved Distributed Delta-Coloring
- An optimal distributed (Δ+1)-coloring algorithm?
- Fast randomized algorithms for distributed edge coloring
- Distributed (∆+1)-coloring in sublogarithmic rounds
- Brief Announcement
- Distributed Algorithms for Coloring Interval Graphs
- Improved distributed algorithms for coloring interval graphs with application to multicoloring trees
This page was built for publication: Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs