Image de couverture de livre

Dynamic O(arboricity) coloring in polylogarithmic worst-case time

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Ghaffari, Mohsen, Grunau, Christoph
Format:	Preprint
Publié:	2024
Sujets:	Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Density-Dependent Graph Orientation and Coloring in Scalable MPC
par: Ghaffari, Mohsen, et autres
Publié: (2026)

Near-Optimal Deterministic Network Decomposition and Ruling Set, and Improved MIS
par: Ghaffari, Mohsen, et autres
Publié: (2024)

Towards True Work-Efficiency in Parallel Derandomization: MIS, Maximal Matching, and Hitting Set
par: Ghaffari, Mohsen, et autres
Publié: (2025)

Parallel Batch-Dynamic Algorithms for Spanners, and Extensions
par: Ghaffari, Mohsen, et autres
Publié: (2025)

Dynamic Graph Coloring: Sequential, Parallel, and Distributed
par: Ghaffari, Mohsen, et autres
Publié: (2025)

Parallel Batch-Dynamic Coreness Decomposition with Worst-Case Guarantees
par: Ghaffari, Mohsen, et autres
Publié: (2025)

Acceleration for Distributed Transshipment and Parallel Maximum Flow
par: Grunau, Christoph, et autres
Publié: (2025)

Constant Approximation of Arboricity in Near-Optimal Sublinear Time
par: Dai, Jiangqi, et autres
Publié: (2025)

Parallel Dynamic Maximal Matching
par: Ghaffari, Mohsen, et autres
Publié: (2024)

Testing $C_k$-freeness in bounded-arboricity graphs
par: Eden, Talya, et autres
Publié: (2024)

A Near-Optimal Low-Energy Deterministic Distributed SSSP with Ramifications on Congestion and APSP
par: Ghaffari, Mohsen, et autres
Publié: (2024)

Edge-coloring sparse graphs with $Δ$ colors in quasilinear time
par: Kowalik, Lukasz
Publié: (2024)

Beyond the worst case: Distortion in impartial culture electorates
par: Caragiannis, Ioannis, et autres
Publié: (2023)

A Cut-Matching Game for Constant-Hop Expanders
par: Haeupler, Bernhard, et autres
Publié: (2022)

Generating a Gray code for prefix normal words in amortized polylogarithmic time per word
par: Burcsi, Péter, et autres
Publié: (2020)

Differentially private graph coloring
par: Xie, Michael, et autres
Publié: (2026)

HENN: A Hierarchical Epsilon Net Navigation Graph for Approximate Nearest Neighbor Search
par: Dehghankar, Mohsen, et autres
Publié: (2025)

Coloring tournaments with few colors: Algorithms and complexity
par: Klingelhoefer, Felix, et autres
Publié: (2023)

Finding $b$-colorings Using Feedback Edges
par: Balabán, Jakub
Publié: (2025)

Fully Scalable MPC Algorithms for Euclidean k-Center
par: Czumaj, Artur, et autres
Publié: (2025)

Comparative genomics with succinct colored de Bruijn graphs
par: Ramos, Lucas P., et autres
Publié: (2024)

On Fair Epsilon Net and Geometric Hitting Set
par: Dehghankar, Mohsen, et autres
Publié: (2025)

A note on approximating the average degree of bounded arboricity graphs
par: Eden, Talya, et autres
Publié: (2026)

Improved linearly ordered colorings of hypergraphs via SDP rounding
par: Louis, Anand, et autres
Publié: (2024)

Brief announcement: A special case of maximum flow over time with network changes
par: Chawla, Shuchi, et autres
Publié: (2026)

Fast Broadcast in Highly Connected Networks
par: Chandra, Shashwat, et autres
Publié: (2024)

Fair Set Cover
par: Dehghankar, Mohsen, et autres
Publié: (2024)

Approximating maximum properly colored forests via degree bounded independent sets
par: Bai, Yuhang, et autres
Publié: (2025)

A QPTAS for Facility Location on Unit Disk graphs
par: Friggstad, Zachary, et autres
Publié: (2024)

The planar edge-coloring theorem of Vizing in $O(n\log n)$ time
par: Jędrzejczak, Patryk, et autres
Publié: (2025)

Space-efficient SLP encoding for $O(\log N)$-time random access
par: Takasaka, Akito, et autres
Publié: (2024)

Parallel, Distributed, and Quantum Exact Single-Source Shortest Paths with Negative Edge Weights
par: Ashvinkumar, Vikrant, et autres
Publié: (2023)

Fully dynamic biconnectivity in $\tilde{\mathcal{O}}(\log^2 n)$ time
par: Holm, Jacob, et autres
Publié: (2025)

LZBE: an LZ-style compressor supporting $O(\log n)$-time random access
par: Shibata, Hiroki, et autres
Publié: (2025)

An $O(n^3)$ time algorithm for the maximum-weight limited-capacity many-to-many matching
par: Rajabi-Alni, Fatemeh, et autres
Publié: (2014)

Kernelization for list $H$-coloring for graphs with small vertex cover
par: Piecyk, Marta, et autres
Publié: (2025)

Decay of correlation for edge colorings when $q>3Δ$
par: Chen, Zejia, et autres
Publié: (2025)

Fully Dynamic Connectivity in $O(\log n(\log\log n)^2)$ Amortized Expected Time
par: Huang, Shang-En, et autres
Publié: (2016)

Weighted $k$-Path and Other Problems in Almost $O^*(2^k)$ Deterministic Time via Dynamic Representative Sets
par: Nederlof, Jesper
Publié: (2025)

Dynamic Detours
par: Dadush, Daniel, et autres
Publié: (2026)