Buchumschlag

$(Δ+ 1)$ Vertex Coloring in $O(n)$ Communication

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Flin, Maxime, Mittal, Parth
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Beyond Brooks: $(Δ-1)$-Coloring in Semi-Streaming
von: Flin, Maxime, et al.
Veröffentlicht: (2026)

Faster Dynamic $(Δ+1)$-Coloring Against Adaptive Adversaries
von: Flin, Maxime, et al.
Veröffentlicht: (2025)

Dynamic $(Δ+ 1)$ Vertex Coloring
von: Benson-Tilsen, Noam
Veröffentlicht: (2026)

Sublogarithmic Distributed Vertex Coloring with Optimal Number of Colors
von: Flin, Maxime, et al.
Veröffentlicht: (2026)

Brooks' Theorem in Graph Streams: A Single-Pass Semi-Streaming Algorithm for $Δ$-Coloring
von: Assadi, Sepehr, et al.
Veröffentlicht: (2022)

Simple Sublinear Algorithms for $(Δ+1)$ Vertex Coloring via Asymmetric Palette Sparsification
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

Decentralized Distributed Graph Coloring II: degree+1-Coloring Virtual Graphs
von: Flin, Maxime, et al.
Veröffentlicht: (2024)

Faster $(Δ+ 1)$-Edge Coloring: Breaking the $m \sqrt{n}$ Time Barrier
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2024)

Density-Sensitive Algorithms for $(Δ+ 1)$-Edge Coloring
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2023)

Fully Dynamic (Δ+1) Coloring Against Adaptive Adversaries
von: Behnezhad, Soheil, et al.
Veröffentlicht: (2024)

Parallel Batch Dynamic Vertex Coloring in $O(\log Δ)$ Amortized Update Time
von: Hutton, Chase, et al.
Veröffentlicht: (2025)

Decentralized Distributed Graph Coloring: Cluster Graphs
von: Flin, Maxime, et al.
Veröffentlicht: (2024)

Faster Deterministic Streaming Vertex Coloring
von: Chechik, Shiri, et al.
Veröffentlicht: (2026)

Sampling Proper Colorings on Line Graphs Using $(1+o(1))Δ$ Colors
von: Wang, Yulin, et al.
Veröffentlicht: (2023)

Deterministic Simple $(Δ+\varepsilonα)$-Edge-Coloring in Near-Linear Time
von: Elkin, Michael, et al.
Veröffentlicht: (2024)

Even Faster $(Δ+ 1)$-Edge Coloring via Shorter Multi-Step Vizing Chains
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2024)

Fast and Simple $(1+ε)Δ$-Edge-Coloring of Dense Graphs
von: Dhawan, Abhishek
Veröffentlicht: (2024)

Enumeration kernels for Vertex Cover and Feedback Vertex Set
von: Bougeret, Marin, et al.
Veröffentlicht: (2025)

When MIS and Maximal Matching are Easy in the Congested Clique
von: Censor-Hillel, Keren, et al.
Veröffentlicht: (2025)

Addressing Bias in Algorithmic Solutions: Exploring Vertex Cover and Feedback Vertex Set
von: Akhtar, Sheikh Shakil, et al.
Veröffentlicht: (2025)

Solution Discovery for Vertex Cover, Independent Set, Dominating Set, and Feedback Vertex Set
von: Saito, Rin, et al.
Veröffentlicht: (2025)

Structural Parameterizations of Vertex Integrity
von: Gima, Tatsuya, et al.
Veröffentlicht: (2023)

Faster Parameterized Vertex Multicut
von: Chu, Huairui, et al.
Veröffentlicht: (2026)

Colorful Vertex Recoloring of Bipartite Graphs
von: Patt-Shamir, Boaz, et al.
Veröffentlicht: (2025)

Engineering Fully Dynamic Exact $Δ$-Orientation Algorithms
von: Großmann, Ernestine, et al.
Veröffentlicht: (2024)

Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy
von: Assadi, Sepehr, et al.
Veröffentlicht: (2024)

Breaking the O(mn)-Time Barrier for Vertex-Weighted Global Minimum Cut
von: Chuzhoy, Julia, et al.
Veröffentlicht: (2025)

An Optimal Algorithm for Stochastic Vertex Cover
von: Brand, Jan van den, et al.
Veröffentlicht: (2026)

Weighted Partition Vertex and Edge Cover
von: Dabas, Rajni, et al.
Veröffentlicht: (2025)

Cluster Vertex Deletion on Chordal Graphs
von: Cao, Yixin, et al.
Veröffentlicht: (2026)

Edge-coloring sparse graphs with $Δ$ colors in quasilinear time
von: Kowalik, Lukasz
Veröffentlicht: (2024)

$Δ$-Motif: Parallel Subgraph Isomorphism via Tabular Operations
von: Wang, Yulun, et al.
Veröffentlicht: (2025)

Parameterized Algorithms for Minimum Sum Vertex Cover
von: Aute, Shubhada, et al.
Veröffentlicht: (2024)

Quadratic Kernel for Cliques or Trees Vertex Deletion
von: Kumabe, Soh
Veröffentlicht: (2025)

Expander Decomposition for Non-Uniform Vertex Measures
von: Agassy, Daniel, et al.
Veröffentlicht: (2025)

The Connected k-Vertex One-Center Problem on Graphs
von: Zhang, Jingru
Veröffentlicht: (2024)

Twin-Width Meets Feedback Edges and Vertex Integrity
von: Balabán, Jakub, et al.
Veröffentlicht: (2024)

Capacitated Partition Vertex Cover and Partition Edge Cover
von: Dabas, Rajni, et al.
Veröffentlicht: (2025)

Path-Reporting Distance Oracles for Vertex-Labeled Graphs
von: Neiman, Ofer, et al.
Veröffentlicht: (2026)

New Oracles and Labeling Schemes for Vertex Cut Queries
von: Jiang, Yonggang, et al.
Veröffentlicht: (2025)