Distributed minimum vertex coloring and maximum independent set in chordal graphs

DOI10.1016/j.tcs.2022.04.047OpenAlexW2803082133WikidataQ114129109 ScholiaQ114129109MaRDI QIDQ2672608

Christian Konrad, Victor Zamaraev

Publication date: 13 June 2022

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2022.04.047

zbMATH Keywords

chordal graphsapproximation algorithmsdistributed algorithmsmaximum independent setminimum vertex coloring

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Low diameter graph decompositions
• 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
• On the complexity of local distributed graph problems
• Reducibility among Combinatorial Problems
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• Brief Announcement
• An optimal distributed (Δ+1)-coloring algorithm?
• Brief Announcement
• Distributed Algorithms for Coloring Interval Graphs
• Logical Locality Entails Frugal Distributed Computation over Graphs (Extended Abstract)
• Improved distributed algorithms for coloring interval graphs with application to multicoloring trees
• A distributed low tree-depth decomposition algorithm for bounded expansion classes

This page was built for publication: Distributed minimum vertex coloring and maximum independent set in chordal graphs