Imagen de Portada

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

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Ghaffari, Mohsen, Grunau, Christoph
Formato:	Preprint
Publicado:	2024
Materias:	Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Density-Dependent Graph Orientation and Coloring in Scalable MPC
por: Ghaffari, Mohsen, et al.
Publicado: (2026)

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

Towards True Work-Efficiency in Parallel Derandomization: MIS, Maximal Matching, and Hitting Set
por: Ghaffari, Mohsen, et al.
Publicado: (2025)

Parallel Batch-Dynamic Algorithms for Spanners, and Extensions
por: Ghaffari, Mohsen, et al.
Publicado: (2025)

Dynamic Graph Coloring: Sequential, Parallel, and Distributed
por: Ghaffari, Mohsen, et al.
Publicado: (2025)

Parallel Batch-Dynamic Coreness Decomposition with Worst-Case Guarantees
por: Ghaffari, Mohsen, et al.
Publicado: (2025)

Acceleration for Distributed Transshipment and Parallel Maximum Flow
por: Grunau, Christoph, et al.
Publicado: (2025)

Constant Approximation of Arboricity in Near-Optimal Sublinear Time
por: Dai, Jiangqi, et al.
Publicado: (2025)

Parallel Dynamic Maximal Matching
por: Ghaffari, Mohsen, et al.
Publicado: (2024)

Testing $C_k$-freeness in bounded-arboricity graphs
por: Eden, Talya, et al.
Publicado: (2024)

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

Edge-coloring sparse graphs with $Δ$ colors in quasilinear time
por: Kowalik, Lukasz
Publicado: (2024)

Beyond the worst case: Distortion in impartial culture electorates
por: Caragiannis, Ioannis, et al.
Publicado: (2023)

A Cut-Matching Game for Constant-Hop Expanders
por: Haeupler, Bernhard, et al.
Publicado: (2022)

Generating a Gray code for prefix normal words in amortized polylogarithmic time per word
por: Burcsi, Péter, et al.
Publicado: (2020)

Differentially private graph coloring
por: Xie, Michael, et al.
Publicado: (2026)

HENN: A Hierarchical Epsilon Net Navigation Graph for Approximate Nearest Neighbor Search
por: Dehghankar, Mohsen, et al.
Publicado: (2025)

Coloring tournaments with few colors: Algorithms and complexity
por: Klingelhoefer, Felix, et al.
Publicado: (2023)

Finding $b$-colorings Using Feedback Edges
por: Balabán, Jakub
Publicado: (2025)

Fully Scalable MPC Algorithms for Euclidean k-Center
por: Czumaj, Artur, et al.
Publicado: (2025)

Comparative genomics with succinct colored de Bruijn graphs
por: Ramos, Lucas P., et al.
Publicado: (2024)

On Fair Epsilon Net and Geometric Hitting Set
por: Dehghankar, Mohsen, et al.
Publicado: (2025)

A note on approximating the average degree of bounded arboricity graphs
por: Eden, Talya, et al.
Publicado: (2026)

Improved linearly ordered colorings of hypergraphs via SDP rounding
por: Louis, Anand, et al.
Publicado: (2024)

Brief announcement: A special case of maximum flow over time with network changes
por: Chawla, Shuchi, et al.
Publicado: (2026)

Fast Broadcast in Highly Connected Networks
por: Chandra, Shashwat, et al.
Publicado: (2024)

Fair Set Cover
por: Dehghankar, Mohsen, et al.
Publicado: (2024)

Approximating maximum properly colored forests via degree bounded independent sets
por: Bai, Yuhang, et al.
Publicado: (2025)

A QPTAS for Facility Location on Unit Disk graphs
por: Friggstad, Zachary, et al.
Publicado: (2024)

The planar edge-coloring theorem of Vizing in $O(n\log n)$ time
por: Jędrzejczak, Patryk, et al.
Publicado: (2025)

Space-efficient SLP encoding for $O(\log N)$-time random access
por: Takasaka, Akito, et al.
Publicado: (2024)

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

Fully dynamic biconnectivity in $\tilde{\mathcal{O}}(\log^2 n)$ time
por: Holm, Jacob, et al.
Publicado: (2025)

LZBE: an LZ-style compressor supporting $O(\log n)$-time random access
por: Shibata, Hiroki, et al.
Publicado: (2025)

An $O(n^3)$ time algorithm for the maximum-weight limited-capacity many-to-many matching
por: Rajabi-Alni, Fatemeh, et al.
Publicado: (2014)

Kernelization for list $H$-coloring for graphs with small vertex cover
por: Piecyk, Marta, et al.
Publicado: (2025)

Decay of correlation for edge colorings when $q>3Δ$
por: Chen, Zejia, et al.
Publicado: (2025)

Fully Dynamic Connectivity in $O(\log n(\log\log n)^2)$ Amortized Expected Time
por: Huang, Shang-En, et al.
Publicado: (2016)

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

Dynamic Detours
por: Dadush, Daniel, et al.
Publicado: (2026)