Imagen de Portada

Additive One Approximation for Minimum Degree Spanning Tree: Breaking the $O(mn)$ Time Barrier

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Bhattacharya, Sayan, Farokhnejad, Ermiya, Wang, Haoze
Formato:	Preprint
Publicado:	2026
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

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

Deterministic $k$-Median Clustering in Near-Optimal Time
por: Costa, Martín, et al.
Publicado: (2025)

Breaking the O(mn)-Time Barrier for Vertex-Weighted Global Minimum Cut
por: Chuzhoy, Julia, et al.
Publicado: (2025)

Almost Optimal Fully Dynamic $k$-Center Clustering with Recourse
por: Bhattacharya, Sayan, et al.
Publicado: (2024)

Improved Approximation Algorithms for (1,2)-TSP and Max-TSP Using Path Covers in the Semi-Streaming Model
por: Alipour, Sharareh, et al.
Publicado: (2025)

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

Faster $(Δ+ 1)$-Edge Coloring: Breaking the $m \sqrt{n}$ Time Barrier
por: Bhattacharya, Sayan, et al.
Publicado: (2024)

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

Planar Length-Constrained Minimum Spanning Trees
por: Hershkowitz, D Ellis, et al.
Publicado: (2025)

Simple Length-Constrained Minimum Spanning Trees
por: Hershkowitz, D Ellis, et al.
Publicado: (2024)

Local Computation Algorithms for (Minimum) Spanning Trees on Expander Graphs
por: Peng, Pan, et al.
Publicado: (2026)

Time, Message and Memory-Optimal Distributed Minimum Spanning Tree and Partwise Aggregation
por: Goldenfeld, Michael Elkin Tanya
Publicado: (2026)

Stochastic Minimum Spanning Trees with a Single Sample
por: Hoeksma, Ruben, et al.
Publicado: (2024)

Massively Parallel Minimum Spanning Tree in General Metric Spaces
por: Azarmehr, Amir, et al.
Publicado: (2024)

Energy-Efficient Aggregation and Minimum-Degree Spanning Trees in Radio Networks
por: Chang, Yi-Jun, et al.
Publicado: (2026)

New Algorithms for Incremental Minimum Spanning Trees and Temporal Graph Applications
por: Ding, Xiangyun, et al.
Publicado: (2025)

Budget and Profit Approximations for Spanning Tree Interdiction
por: Ostrovsky, Rafail, et al.
Publicado: (2025)

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

FAMST: Fast Approximate Minimum Spanning Tree Construction for Large-Scale and High-Dimensional Data
por: Almansoori, Mahmood K. M., et al.
Publicado: (2025)

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

Approximate Spanning Tree Counting from Uncorrelated Edge Sets
por: Liu, Yang P., et al.
Publicado: (2025)

Approximate Tree Completion and Learning-Augmented Algorithms for Metric Minimum Spanning Trees
por: Veldt, Nate, et al.
Publicado: (2025)

Polynomial-Time Constant-Approximation for Fair Sum-of-Radii Clustering
por: Nezhad, Sina Bagheri, et al.
Publicado: (2025)

Breaking a Long-Standing Barrier: 2-$\varepsilon$ Approximation for Steiner Forest
por: Ahmadi, Ali, et al.
Publicado: (2025)

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

Near-Universally-Optimal Differentially Private Minimum Spanning Trees
por: Hladík, Richard, et al.
Publicado: (2024)

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

Enumerating All Directed Spanning Trees in Optimal Time
por: Gawrychowski, Paweł, et al.
Publicado: (2026)

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

Faster Private Minimum Spanning Trees
por: Pagh, Rasmus, et al.
Publicado: (2024)

Breaking the $n^{1.5}$ Additive Error Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition
por: Aamand, Anders, et al.
Publicado: (2025)

Breaking Barriers: Combinatorial Algorithms for Non-monotone Submodular Maximization with Sublinear Adaptivity and $1/e$ Approximation
por: Chen, Yixin, et al.
Publicado: (2025)

Vizing's Theorem in Near-Linear Time
por: Assadi, Sepehr, et al.
Publicado: (2024)

A Unified Approach for Approximating 2-Edge-Connected Spanning Subgraph and 2-Vertex-Connected Spanning Subgraph
por: Çivril, Ali
Publicado: (2023)

Approximate Minimum Tree Cover in All Symmetric Monotone Norms Simultaneously
por: Kaul, Matthias, et al.
Publicado: (2025)

Vizing's Theorem in Deterministic Almost-Linear Time
por: Assadi, Sepehr, et al.
Publicado: (2025)

Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in-$f$ Time Barrier
por: Bukov, Anton, et al.
Publicado: (2023)

Economic Warehouse Lot Scheduling: Breaking the 2-Approximation Barrier
por: Segev, Danny
Publicado: (2026)

Breaking Barriers for Distributed MIS by Faster Degree Reduction
por: Khoury, Seri, et al.
Publicado: (2025)

Approximation of Spanning Tree Congestion using Hereditary Bisection
por: Kolman, Petr
Publicado: (2024)