Cover Image

Improved Deterministic Distributed Maximum Weight Independent Set Approximation in Sparse Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Gil, Yuval
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms Distributed, Parallel, and Cluster Computing
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Distributed Reductions for the Maximum Weight Independent Set Problem
by: Borowitz, Jannick, et al.
Published: (2025)

Faster CONGEST Approximation Algorithms for Maximum Weighted Independent Set in Sparse Graphs
by: Faour, Salwa, et al.
Published: (2025)

Distributed Interactive Proofs for Planarity with Log-Star Communication
by: Gil, Yuval, et al.
Published: (2025)

New Distributed Interactive Proofs for Planarity: A Matter of Left and Right
by: Gil, Yuval, et al.
Published: (2025)

Distributed Approximation Algorithms for Minimum Dominating Set in Locally Nice Graphs
by: Bonamy, Marthe, et al.
Published: (2025)

Distributed Maximum Flow in Planar Graphs
by: Abd-Elhaleem, Yaseen, et al.
Published: (2024)

Near-Optimal Deterministic Network Decomposition and Ruling Set, and Improved MIS
by: Ghaffari, Mohsen, et al.
Published: (2024)

A Simple $(1-ε)$-Approximation Semi-Streaming Algorithm for Maximum (Weighted) Matching
by: Assadi, Sepehr
Published: (2023)

Improved Approximation Bounds for Minimum Weight Cycle in the CONGEST Model
by: Manoharan, Vignesh, et al.
Published: (2023)

Massively Parallel Ruling Set Made Deterministic
by: Giliberti, Jeff, et al.
Published: (2024)

Fast Deterministic Distributed Degree Splitting
by: Maus, Yannic, et al.
Published: (2026)

Parallel Batch-Dynamic Maximal Independent Set
by: Blelloch, Guy, et al.
Published: (2026)

A Simple Distributed Deterministic Planar Separator
by: Abd-Elhaleem, Yaseen, et al.
Published: (2026)

Energy-Efficient Maximal Independent Sets in Radio Networks
by: Banasik, Dominick, et al.
Published: (2025)

Near-Optimal Distributed Ruling Sets for Trees and High-Girth Graphs
by: Baumecker, Malte, et al.
Published: (2025)

Deterministic Lower Bounds for $k$-Edge Connectivity in the Distributed Sketching Model
by: Robinson, Peter, et al.
Published: (2025)

Local Density and its Distributed Approximation
by: Christiansen, Aleksander Bjørn, et al.
Published: (2024)

A Near-Optimal Low-Energy Deterministic Distributed SSSP with Ramifications on Congestion and APSP
by: Ghaffari, Mohsen, et al.
Published: (2024)

Fully-Distributed Byzantine Agreement in Sparse Networks
by: Augustine, John, et al.
Published: (2024)

Adaptive Massively Parallel Coloring in Sparse Graphs
by: Latypov, Rustam, et al.
Published: (2024)

Improved All-Pairs Approximate Shortest Paths in Congested Clique
by: Bui, Hong Duc, et al.
Published: (2024)

A Simple Distributed Algorithm for Sparse Fractional Covering and Packing Problems
by: Li, Qian, et al.
Published: (2024)

Distributed Stochastic Graph Algorithms
by: Censor-Hillel, Keren, et al.
Published: (2026)

Distributed Graph Algorithms with Predictions
by: Boyar, Joan, et al.
Published: (2025)

Optimal Deterministic Rendezvous in Labeled Lines
by: Bourreau, Yann, et al.
Published: (2025)

TC-MIS: Maximal Independent Set on Tensor-cores
by: Nijhara, Prajjwal, et al.
Published: (2026)

Distributed Download from an External Data Source in Faulty Majority Settings
by: Augustine, John, et al.
Published: (2024)

Deterministic Expander Routing: Faster and More Versatile
by: Chang, Yi-Jun, et al.
Published: (2024)

Deterministic Even-Cycle Detection in Broadcast CONGEST
by: Fraigniaud, Pierre, et al.
Published: (2024)

Time-Optimal and Energy-Efficient Deterministic Consensus
by: Meir, Shachar, et al.
Published: (2025)

Õptimal Fault-Tolerant Labeling for Reachability and Approximate Distances in Directed Planar Graphs
by: Boneh, Itai, et al.
Published: (2025)

Parallel, Distributed, and Quantum Exact Single-Source Shortest Paths with Negative Edge Weights
by: Ashvinkumar, Vikrant, et al.
Published: (2023)

The Local Information Cost of Distributed Graph Spanners
by: Robinson, Peter
Published: (2020)

Decentralized Distributed Graph Coloring II: degree+1-Coloring Virtual Graphs
by: Flin, Maxime, et al.
Published: (2024)

Massively Parallel Maximum Coverage Revisited
by: Bui, Thai, et al.
Published: (2024)

History-Independent Concurrent Hash Tables
by: Attiya, Hagit, et al.
Published: (2025)

Brief Announcement: Distributed Unconstrained Local Search for Multilevel Graph Partitioning
by: Sanders, Peter, et al.
Published: (2024)

Two for One, One for All: Deterministic LDC-based Robust Computation in Congested Clique
by: Censor-Hillel, Keren, et al.
Published: (2025)

A Nearly Linear-Time Distributed Algorithm for Maximum Cardinality Matching
by: Izumi, Taisuke, et al.
Published: (2023)

Dynamic Approximate Maximum Matching in the Distributed Vertex Partition Model
by: Robinson, Peter, et al.
Published: (2025)