Imagen de Portada

Fully Dynamic Exact Edge Connectivity in Sublinear Time

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Goranci, Gramoz, Henzinger, Monika, Nanongkai, Danupon, Saranurak, Thatchaphol, Thorup, Mikkel, Wulff-Nilsen, Christian
Formato:	Preprint
Publicado:	2023
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

Negative-Weight Single-Source Shortest Paths in Near-linear Time
por: Bernstein, Aaron, et al.
Publicado: (2022)

Fully Dynamic Spectral Sparsification of Hypergraphs
por: Goranci, Gramoz, et al.
Publicado: (2025)

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

Dynamic Hierarchical $j$-Tree Decomposition and Its Applications
por: Goranci, Gramoz, et al.
Publicado: (2026)

Fully Dynamic Spectral Sparsification for Directed Hypergraphs
por: Forster, Sebastian, et al.
Publicado: (2025)

Dynamic $(1+ε)$-Approximate Matching Size in Truly Sublinear Update Time
por: Bhattacharya, Sayan, et al.
Publicado: (2023)

Deterministic Dynamic Maximal Matching in Sublinear Update Time
por: Bernstein, Aaron, et al.
Publicado: (2025)

Fully Dynamic Algorithms for Transitive Reduction
por: Goranci, Gramoz, et al.
Publicado: (2025)

Fully Dynamic Algorithms for Chamfer Distance
por: Goranci, Gramoz, et al.
Publicado: (2025)

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

Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries
por: Anand, Aditya, et al.
Publicado: (2024)

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

Minimum $s$--$t$ Cuts with Fewer Cut Queries
por: Jiang, Yonggang, et al.
Publicado: (2025)

Sublinear Data Structures for Nearest Neighbor in Ultra High Dimensions
por: Herold, Martin G., et al.
Publicado: (2025)

Decremental $(1+ε)$-Approximate Maximum Eigenvector: Dynamic Power Method
por: Adil, Deeksha, et al.
Publicado: (2024)

Near-Optimal Fault-Tolerant Strong Connectivity Preservers
por: Hoppenworth, Gary, et al.
Publicado: (2025)

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

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

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

On $b$-Matching and Fully-Dynamic Maximum $k$-Edge Coloring
por: El-Hayek, Antoine, et al.
Publicado: (2023)

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

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

Shortcuts and Transitive-Closure Spanners Approximation
por: Chalermsook, Parinya, et al.
Publicado: (2025)

Local Sherman's Algorithm for Multi-commodity Flow
por: Li, Jason, et al.
Publicado: (2025)

Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers
por: Haeupler, Bernhard, et al.
Publicado: (2025)

Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness
por: Jiang, Yonggang, et al.
Publicado: (2025)

A Constant-Approximation Distance Labeling Scheme under Polynomially Many Edge Failures
por: Haeupler, Bernhard, et al.
Publicado: (2026)

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

Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time
por: Meierhans, Simon, et al.
Publicado: (2025)

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

Connectivity Oracle Under Vertex Failures by Shortcutting Unbreakable Decomposition
por: Li, Xizhe, et al.
Publicado: (2026)

Expander Decomposition with Almost Optimal Overhead
por: Bansal, Nikhil, et al.
Publicado: (2026)

DAG Projections: Reducing Distance and Flow Problems to DAGs
por: Haeupler, Bernhard, et al.
Publicado: (2026)

Reducing Shortcut and Hopset Constructions to Shallow Graphs
por: Haeupler, Bernhard, et al.
Publicado: (2025)

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

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

Dynamic algorithms for k-center on graphs
por: Cruciani, Emilio, et al.
Publicado: (2023)

Maximum Flow by Augmenting Paths in $n^{2+o(1)}$ Time
por: Bernstein, Aaron, et al.
Publicado: (2024)

Disjoint Paths in Expanders in Deterministic Almost-Linear Time via Hypergraph Perfect Matching
por: Bucić, Matija, et al.
Publicado: (2025)

Cactus Representation of Minimum Cuts: Derandomize and Speed up
por: He, Zhongtian, et al.
Publicado: (2024)