Imagen de Portada

Improved Tree Sparsifiers in Near-Linear Time

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Agassy, Daniel, Dorfman, Dani, Kaplan, Haim
Formato:	Preprint
Publicado:	2025
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

Expander Decomposition for Non-Uniform Vertex Measures
por: Agassy, Daniel, et al.
Publicado: (2025)

Expander Decomposition with Fewer Inter-Cluster Edges Using a Spectral Cut Player
por: Agassy, Daniel, et al.
Publicado: (2022)

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

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

Beyond Vizing Chains: Improved Recourse in Dynamic Edge Coloring
por: Sadeh, Yaniv, et al.
Publicado: (2026)

Nearly-Tight Bounds for Flow Sparsifiers in Quasi-Bipartite Graphs
por: Das, Syamantak, et al.
Publicado: (2024)

Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems
por: Dughmi, Shaddin, et al.
Publicado: (2025)

Minimum-cost paths for electric cars
por: Dorfman, Dani, et al.
Publicado: (2024)

Search Trees on Trees via LP
por: Sadeh, Yaniv, et al.
Publicado: (2025)

On Differentially Private Linear Algebra
por: Kaplan, Haim, et al.
Publicado: (2024)

Caching Connections in Matchings
por: Sadeh, Yaniv, et al.
Publicado: (2023)

An Improved Quality Hierarchical Congestion Approximator in Near-Linear Time
por: Henzinger, Monika, et al.
Publicado: (2025)

Dynamic Kernel Graph Sparsifiers
por: Cao, Yang, et al.
Publicado: (2022)

Dynamic Edge Coloring of Forests
por: Kaplan, Haim, et al.
Publicado: (2026)

A Simpler Analysis for $\varepsilon$-Clairvoyant Flow Time Scheduling
por: Gupta, Anupam, et al.
Publicado: (2026)

Twice-Ramanujan Sparsifiers
por: Batson, Joshua, et al.
Publicado: (2008)

Sparsifying Sums of Positive Semidefinite Matrices
por: Basu, Arpon, et al.
Publicado: (2025)

Sparsifying Cayley Graphs on Every Group
por: Hsieh, Jun-Ting, et al.
Publicado: (2025)

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

Approximating Partition in Near-Linear Time
por: Chen, Lin, et al.
Publicado: (2024)

Lower Bounds on Flow Sparsifiers with Steiner Nodes
por: Chen, Yu, et al.
Publicado: (2026)

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

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

Linear-Sized Spectral Sparsifiers and the Kadison-Singer Problem
por: Paschalidis, Phevos, et al.
Publicado: (2023)

Cut-Preserving Vertex Sparsifiers for Planar and Quasi-bipartite Graphs
por: Chen, Yu, et al.
Publicado: (2024)

Many Hamiltonians Are Sparsifiable
por: Basu, Arpon, et al.
Publicado: (2026)

Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time
por: Fischer, Nick, et al.
Publicado: (2024)

Approximating the Geometric Knapsack Problem in Near-Linear Time and Dynamically
por: Buchem, Moritz, et al.
Publicado: (2024)

Deterministic Near-Linear Time Minimum Cut in Weighted Graphs
por: Henzinger, Monika, et al.
Publicado: (2024)

A Little Clairvoyance Is All You Need
por: Gupta, Anupam, et al.
Publicado: (2025)

Near Linear Time Approximation Schemes for Clustering of Partially Doubling Metrics
por: Driemel, Anne, et al.
Publicado: (2026)

Deterministic Simple $(Δ+\varepsilonα)$-Edge-Coloring in Near-Linear Time
por: Elkin, Michael, et al.
Publicado: (2024)

Unweighted One-Sided Code Sparsifiers and Thin Subgraphs
por: Gharan, Shayan Oveis, et al.
Publicado: (2025)

A Simple Algorithm for Near-Vizing Edge-Coloring in Near-Linear Time
por: Dhawan, Abhishek
Publicado: (2024)

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

A Nearly Linear Time Construction of Approximate Single-Source Distance Sensitivity Oracles
por: Harada, Kaito, et al.
Publicado: (2024)

All-Subsets Important Separators with Applications to Sample Sets, Balanced Separators and Vertex Sparsifiers in Directed Graphs
por: Anand, Aditya, et al.
Publicado: (2025)

Near-Linear Time Generalized Sinkhorn Algorithms for Bounded Genus Graphs
por: Choromanski, Krzysztof, et al.
Publicado: (2026)

Learning-Augmented Algorithms with Explicit Predictors
por: Elias, Marek, et al.
Publicado: (2024)

Ortho-Radial Drawing in Near-Linear Time
por: Chang, Yi-Jun
Publicado: (2023)