Copertina

Fully Dynamic Connectivity in $O(\log n(\log\log n)^2)$ Amortized Expected Time

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Huang, Shang-En, Huang, Dawei, Kopelowitz, Tsvi, Pettie, Seth, Thorup, Mikkel
Natura:	Preprint
Pubblicazione:	2016
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

PCF Learned Sort: a Learning Augmented Sort Algorithm with $O(n \log\log n)$ Expected Complexity
di: Sato, Atsuki, et al.
Pubblicazione: (2024)

Finding a solution to the Erdős-Ginzburg-Ziv theorem in $O(n\log\log\log n)$ time
di: Leung, Yui Hin Arvin
Pubblicazione: (2025)

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

Color Distance Oracles and Snippets: Separation Between Exact and Approximate Solutions
di: Horowicz, Noam, et al.
Pubblicazione: (2025)

Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time
di: Jin, Wenyu, et al.
Pubblicazione: (2024)

Fully Dynamic Exact Edge Connectivity in Sublinear Time
di: Goranci, Gramoz, et al.
Pubblicazione: (2023)

An $Ω( (\log n / \log \log n)^2 )$ Cell-Probe Lower Bound for Dynamic Boolean Data Structures
di: Ko, Young Kun
Pubblicazione: (2026)

On the Space Usage of Approximate Distance Oracles with Sub-2 Stretch
di: Kopelowitz, Tsvi, et al.
Pubblicazione: (2023)

$O(\log n)$-Approximation Algorithms for Bipartiteness Ratio
di: Soma, Tasuku, et al.
Pubblicazione: (2025)

On the Hardness Hierarchy for the $O(n \sqrt{\log n})$ Complexity in the Word RAM
di: Kempa, Dominik, et al.
Pubblicazione: (2025)

Connectivity augmentation is fixed-parameter tractable
di: Korhonen, Tuukka, et al.
Pubblicazione: (2026)

Building a Balanced k-d Tree in O(kn log n) Time
di: Brown, Russell A.
Pubblicazione: (2014)

Embedding Planar Graphs into Graphs of Treewidth $O(\log^{3} n)$
di: Chang, Hsien-Chih, et al.
Pubblicazione: (2024)

An $O(n \log n)$-Time Approximation Scheme for Geometric Many-to-Many Matching
di: Bandyapadhyay, Sayan, et al.
Pubblicazione: (2024)

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

The Contiguous Art Gallery Problem is in Θ(n log n)
di: de Berg, Sarita, et al.
Pubblicazione: (2025)

A simpler and parallelizable $O(\sqrt{\log n})$-approximation algorithm for Sparsest Cut
di: Kolmogorov, Vladimir
Pubblicazione: (2023)

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

Learning Multinomial Logits in $O(n \log n)$ time
di: Chierichetti, Flavio, et al.
Pubblicazione: (2026)

Connectivity Labeling Schemes for Edge and Vertex Faults via Expander Hierarchies
di: Long, Yaowei, et al.
Pubblicazione: (2024)

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

An $n^{O(\log\log n)}$ time approximation scheme for capacitated VRP in the Euclidean plane
di: Sitters, René
Pubblicazione: (2025)

Space Complexity of Vertex Connectivity Oracles
di: Pettie, Seth, et al.
Pubblicazione: (2022)

An $O(n\log n)$ Algorithm for Single-Item Lot Sizing with a One-Breakpoint All-Units Discount and Non-Increasing Prices
di: Papadopoulos, Kleitos
Pubblicazione: (2025)

Instance-Optimality in PageRank Computation
di: Thorup, Mikkel, et al.
Pubblicazione: (2025)

An $\mathcal{O}(\log N)$ Time Algorithm for the Generalized Egg Dropping Problem
di: Papadopoulos, Kleitos
Pubblicazione: (2026)

An $Ω(n \log n)$ Randomized Lower Bound for Cutting a Cake into Proportionally Fair Pieces
di: Arndt, Stephen, et al.
Pubblicazione: (2026)

The adaptive complexity of parallelized log-concave sampling
di: Zhou, Huanjian, et al.
Pubblicazione: (2024)

A Unified Construction of Streaming Sketches via the Lévy-Khintchine Representation Theorem
di: Pettie, Seth, et al.
Pubblicazione: (2024)

Universal Perfect Samplers for Incremental Streams
di: Pettie, Seth, et al.
Pubblicazione: (2024)

Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation
di: Narayanan, Shyam, et al.
Pubblicazione: (2024)

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

Information Theoretic Limits of Cardinality Estimation: Fisher Meets Shannon
di: Pettie, Seth, et al.
Pubblicazione: (2020)

Pivot based correlation clustering in the presence of good clusters
di: Lolck, David Rasmussen, et al.
Pubblicazione: (2026)

Dynamic Connectivity with Expected Polylogarithmic Worst-Case Update Time
di: Meierhans, Simon, et al.
Pubblicazione: (2025)

An $O(\log \log n)$-approximate budget feasible mechanism for subadditive valuations
di: Neogi, Rian, et al.
Pubblicazione: (2025)

A Faster Algorithm for Constrained Correlation Clustering
di: Fischer, Nick, et al.
Pubblicazione: (2025)

PageRank Centrality in Directed Graphs with Bounded In-Degree
di: Thorup, Mikkel, et al.
Pubblicazione: (2025)

An O(log n)-Approximation Algorithm for (p,q)-Flexible Graph Connectivity via Independent Rounding
di: Ibrahimpur, Sharat, et al.
Pubblicazione: (2025)

A mixing time bound for Gibbs sampling from log-smooth log-concave distributions
di: Wadia, Neha S.
Pubblicazione: (2024)