Buchumschlag

Parallel Batch-Dynamic Coreness Decomposition with Worst-Case Guarantees

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Ghaffari, Mohsen, Koo, Jaehyun
Format:	Preprint
Veröffentlicht:	2025
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

Parallel Batch-Dynamic Algorithms for Spanners, and Extensions
von: Ghaffari, Mohsen, et al.
Veröffentlicht: (2025)

Dynamic Graph Coloring: Sequential, Parallel, and Distributed
von: Ghaffari, Mohsen, et al.
Veröffentlicht: (2025)

An Optimal MPC Algorithm for Subunit-Monge Matrix Multiplication, with Applications to LIS
von: Koo, Jaehyun
Veröffentlicht: (2024)

Anarchy in the APSP: Algorithm and Hardness for Incorrect Implementation of Floyd-Warshall
von: Koo, Jaehyun
Veröffentlicht: (2024)

Parallel Dynamic Maximal Matching
von: Ghaffari, Mohsen, et al.
Veröffentlicht: (2024)

Dynamic O(arboricity) coloring in polylogarithmic worst-case time
von: Ghaffari, Mohsen, et al.
Veröffentlicht: (2024)

Adaptive Fully Dynamic $k$-Center Clustering with (Near-)Optimal Worst-Case Guarantees
von: Grilnberger, Mara, et al.
Veröffentlicht: (2026)

Density-Dependent Graph Orientation and Coloring in Scalable MPC
von: Ghaffari, Mohsen, et al.
Veröffentlicht: (2026)

Dynamic Set Cover with Worst-Case Recourse
von: Solomon, Shay, et al.
Veröffentlicht: (2025)

(Worst-Case) Optimal Adaptive Dynamic Bitvectors
von: Navarro, Gonzalo
Veröffentlicht: (2024)

Parallel $k$-Core Decomposition with Batched Updates and Asynchronous Reads
von: Liu, Quanquan C., et al.
Veröffentlicht: (2024)

Near-Optimal Deterministic Network Decomposition and Ruling Set, and Improved MIS
von: Ghaffari, Mohsen, et al.
Veröffentlicht: (2024)

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

Dynamic Connectivity with Expected Polylogarithmic Worst-Case Update Time
von: Meierhans, Simon, et al.
Veröffentlicht: (2025)

Constant Approximation of Arboricity in Near-Optimal Sublinear Time
von: Dai, Jiangqi, et al.
Veröffentlicht: (2025)

Dynamic Data Layout Optimization with Worst-case Guarantees
von: Rong, Kexin, et al.
Veröffentlicht: (2024)

Fully Dynamic Set Cover: Worst-Case Recourse and Update Time
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2025)

UFO Trees: Practical and Provably-Efficient Parallel Batch-Dynamic Trees
von: De Man, Quinten, et al.
Veröffentlicht: (2026)

Maximal Biclique Enumeration with Improved Worst-Case Time Complexity Guarantee: A Partition-Oriented Strategy
von: Wang, Kaixin, et al.
Veröffentlicht: (2026)

Worst-Case to Expander-Case Reductions: Derandomized and Generalized
von: Abboud, Amir, et al.
Veröffentlicht: (2024)

Online Metric Matching: Beyond the Worst Case
von: Yang, Mingwei, et al.
Veröffentlicht: (2024)

Beyond Worst Case Local Computation Algorithms
von: Biswas, Amartya Shankha, et al.
Veröffentlicht: (2024)

Fully-Dynamic All-Pairs Shortest Paths: Likely Optimal Worst-Case Update Time
von: Mao, Xiao
Veröffentlicht: (2023)

Dynamic Deterministic Constant-Approximate Distance Oracles with $n^ε$ Worst-Case Update Time
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2024)

Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time
von: Meierhans, Simon, et al.
Veröffentlicht: (2025)

Optimal Static Dictionary with Worst-Case Constant Query Time
von: Hu, Yang, et al.
Veröffentlicht: (2024)

Parallel Higher-order Truss Decomposition
von: Chen, Chen, et al.
Veröffentlicht: (2024)

Tight Better-Than-Worst-Case Bounds for Element Distinctness and Set Intersection
von: van der Hoog, Ivor, et al.
Veröffentlicht: (2025)

Sensitivity Sampling for $k$-Means: Worst Case and Stability Optimal Coreset Bounds
von: Bansal, Nikhil, et al.
Veröffentlicht: (2024)

Non-Splitting Coflow Scheduling with Provable Guarantees in Heterogeneous Parallel Networks
von: Chen, Chi-Yeh
Veröffentlicht: (2025)

Count-Min Sketch with Conservative Updates: Worst-Case Analysis
von: Mazziane, Younes Ben, et al.
Veröffentlicht: (2024)

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

Parallel Batch-Dynamic Maximal Independent Set
von: Blelloch, Guy, et al.
Veröffentlicht: (2026)

Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal
von: Chen, Daoyuan, et al.
Veröffentlicht: (2024)

Hardness of Dynamic Core and Truss Decompositions
von: Couto, Yan S., et al.
Veröffentlicht: (2025)

Efficient Defective Clique Enumeration and Search with Worst-Case Optimal Search Space
von: Jang, Jihoon, et al.
Veröffentlicht: (2025)

Parallel $k$-Core Decomposition: Theory and Practice
von: Liu, Youzhe, et al.
Veröffentlicht: (2025)

Beyond Worst-Case Dimensionality Reduction for Sparse Vectors
von: Silwal, Sandeep, et al.
Veröffentlicht: (2025)

From Amortized to Worst Case Delay in Enumeration Algorithms
von: Capelli, Florent, et al.
Veröffentlicht: (2021)

Hypergraph Samplers: Typical and Worst Case Behavior
von: Alev, Vedat Levi, et al.
Veröffentlicht: (2026)