Copertina

Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Jin, Wenyu, Sun, Xiaorui, Thorup, Mikkel
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Deterministic and Exact Fully-dynamic Minimum Cut of Superpolylogarithmic Size in Subpolynomial Time
di: El-Hayek, Antoine, et al.
Pubblicazione: (2025)

Fully Dynamic Approximate Minimum Cut in Subpolynomial Time per Operation
di: El-Hayek, Antoine, et al.
Pubblicazione: (2024)

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

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

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

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

Tree-Packing Revisited: Faster Fully Dynamic Min-Cut and Arboricity
di: de Vos, Tijn, et al.
Pubblicazione: (2024)

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

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

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)

Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming
di: Kacham, Praneeth, et al.
Pubblicazione: (2023)

Dynamic Kernel Graph Sparsifiers
di: Cao, Yang, et al.
Pubblicazione: (2022)

Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut
di: Cheng, Yu, et al.
Pubblicazione: (2024)

Superconstant Inapproximability of Decision Tree Learning
di: Koch, Caleb, et al.
Pubblicazione: (2024)

Fully Dynamic Spectral and Cut Sparsifiers for Directed Graphs
di: Zhao, Yibin
Pubblicazione: (2025)

Estimating Random-Walk Probabilities in Directed Graphs
di: Bertram, Christian, et al.
Pubblicazione: (2025)

Faster All-Pairs Optimal Electric Car Routing
di: Dorfman, Dani, et al.
Pubblicazione: (2025)

Maintaining $k$-MinHash Signatures over Fully-Dynamic Data Streams with Recovery
di: Clementi, Andrea, et al.
Pubblicazione: (2024)

Fast Similarity Sketching
di: Dahlgaard, Søren, et al.
Pubblicazione: (2017)

Hashing for Sampling-Based Estimation
di: Aamand, Anders, et al.
Pubblicazione: (2024)

Combinatorial Correlation Clustering
di: Cohen-Addad, Vincent, et al.
Pubblicazione: (2024)

Static to Dynamic Correlation Clustering
di: Cao, Nairen, et al.
Pubblicazione: (2025)

Solving the Correlation Cluster LP in Sublinear Time
di: Cao, Nairen, et al.
Pubblicazione: (2025)

Better coloring of 3-colorable graphs
di: Kawarabayashi, Ken-ichi, et al.
Pubblicazione: (2024)

Finding Most Shattering Minimum Vertex Cuts of Polylogarithmic Size in Near-Linear Time
di: Hua, Kevin, et al.
Pubblicazione: (2024)

Min-Max Connected Multiway Cut
di: Tiwary, Hans Raj, et al.
Pubblicazione: (2026)

Canonical forms for matrix tuples in polynomial time
di: Qiao, Youming, et al.
Pubblicazione: (2024)

Deterministic Monotone Min-Plus Product and Convolution
di: Jin, Ce, et al.
Pubblicazione: (2026)

Fully Dynamic Euclidean k-Means
di: Bhattacharya, Sayan, et al.
Pubblicazione: (2025)

Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers
di: Khanna, Sanjeev, et al.
Pubblicazione: (2024)

A tight quasi-polynomial bound for Global Label Min-Cut
di: Jaffke, Lars, et al.
Pubblicazione: (2022)

Fully Dynamic $k$-Clustering with Fast Update Time and Small Recourse
di: Bhattacharya, Sayan, et al.
Pubblicazione: (2024)

Fully Dynamic k-Means Coreset in Near-Optimal Update Time
di: la Tour, Max Dupré, et al.
Pubblicazione: (2024)

Fully Dynamic $k$-Median with Near-Optimal Update Time and Recourse
di: Bhattacharya, Sayan, et al.
Pubblicazione: (2024)

Fully Dynamic Set Cover: Worst-Case Recourse and Update Time
di: Bhattacharya, Sayan, et al.
Pubblicazione: (2025)

Fully Dynamic Euclidean Bi-Chromatic Matching in Sublinear Update Time
di: Goranci, Gramoz, et al.
Pubblicazione: (2025)

Explicit Min-wise Hash Families with Optimal Size
di: Chen, Xue, et al.
Pubblicazione: (2025)

ExpoSort: Breaking the quasi-polynomial-time barrier for reluctant sorting
di: Abrahamsen, Mikkel
Pubblicazione: (2024)

Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT
di: Anand, Aditya, et al.
Pubblicazione: (2025)