Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs

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

zbMATH Keywords

chordal graphsapproximation algorithmsmaximum independent setlocal modelminimum vertex coloring

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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