Image de couverture de livre

Local Computation Algorithms for (Minimum) Spanning Trees on Expander Graphs

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Peng, Pan, Wang, Yuyang
Format:	Preprint
Publié:	2026
Sujets:	Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

New Algorithms for Incremental Minimum Spanning Trees and Temporal Graph Applications
par: Ding, Xiangyun, et autres
Publié: (2025)

Planar Length-Constrained Minimum Spanning Trees
par: Hershkowitz, D Ellis, et autres
Publié: (2025)

Simple Length-Constrained Minimum Spanning Trees
par: Hershkowitz, D Ellis, et autres
Publié: (2024)

Stochastic Minimum Spanning Trees with a Single Sample
par: Hoeksma, Ruben, et autres
Publié: (2024)

Approximating Directed Minimum Cut and Arborescence Packing via Directed Expander Hierarchies
par: Jiang, Yonggang, et autres
Publié: (2025)

Massively Parallel Minimum Spanning Tree in General Metric Spaces
par: Azarmehr, Amir, et autres
Publié: (2024)

Near-Optimal Algorithm for Directed Expander Decompositions
par: Sulser, Aurelio L., et autres
Publié: (2024)

Additive One Approximation for Minimum Degree Spanning Tree: Breaking the $O(mn)$ Time Barrier
par: Bhattacharya, Sayan, et autres
Publié: (2026)

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

New Structures and Algorithms for Length-Constrained Expander Decompositions
par: Haeupler, Bernhard, et autres
Publié: (2024)

Parameterized Algorithms for Spanning Tree Isomorphism by Redundant Set Size
par: Shen, Fangjian, et autres
Publié: (2025)

Near-Universally-Optimal Differentially Private Minimum Spanning Trees
par: Hladík, Richard, et autres
Publié: (2024)

Approximate Tree Completion and Learning-Augmented Algorithms for Metric Minimum Spanning Trees
par: Veldt, Nate, et autres
Publié: (2025)

Faster Private Minimum Spanning Trees
par: Pagh, Rasmus, et autres
Publié: (2024)

On the Streaming Complexity of Expander Decomposition
par: Chen, Yu, et autres
Publié: (2024)

Improved Directed Expander Decompositions
par: Fleischmann, Henry, et autres
Publié: (2025)

Expander Hierarchies for Normalized Cuts on Graphs
par: Hanauer, Kathrin, et autres
Publié: (2024)

A Fast Approximation Algorithm for the Minimum Balanced Vertex Separator in a Graph
par: Kolmogorov, Vladimir, et autres
Publié: (2026)

Above-Guarantee Algorithm for Properly Colored Spanning Trees
par: Bai, Yuhang, et autres
Publié: (2026)

Approximate Spanning Tree Counting from Uncorrelated Edge Sets
par: Liu, Yang P., et autres
Publié: (2025)

Minimum Sum Coloring with Bundles in Trees and Bipartite Graphs
par: Ito, Takehiro, et autres
Publié: (2025)

Expander Decomposition with Almost Optimal Overhead
par: Bansal, Nikhil, et autres
Publié: (2026)

Finding Colorings in One-Sided Expanders
par: Buhai, Rares-Darius, et autres
Publié: (2025)

Expanderizing Higher Order Random Walks
par: Alev, Vedat Levi, et autres
Publié: (2024)

Optimal Electrical Oblivious Routing on Expanders
par: Florescu, Cella, et autres
Publié: (2024)

Simple Length-Constrained Expander Decompositions
par: Bodwin, Greg, et autres
Publié: (2025)

A Spanning-Tree-Based Algorithm for Planar Graph Dismantling
par: You, Fangchen
Publié: (2025)

Improved Algorithms for Effective Resistance Computation on Graphs
par: Yang, Yichun, et autres
Publié: (2025)

Generating the Spanning Trees of Series-Parallel Graphs up to Graph Automorphism
par: Karamchedu, Mithra, et autres
Publié: (2025)

Witty: An Efficient Solver for Computing Minimum-Size Decision Trees
par: Staus, Luca Pascal, et autres
Publié: (2024)

Expander Decomposition for Non-Uniform Vertex Measures
par: Agassy, Daniel, et autres
Publié: (2025)

Approximation Algorithm of Minimum All-Ones Problem for Arbitrary Graphs
par: Wang, Chen, et autres
Publié: (2024)

Parallel Algorithm For Finding The Minimum s/t Cut in a Structured 3-Dimensional Proper Order Graph
par: Chandramouli, Shridharan
Publié: (2026)

Light Tree Covers, Routing, and Path-Reporting Oracles via Spanning Tree Covers in Doubling Graphs
par: Chang, Hsien-Chih, et autres
Publié: (2025)

A Simple Deterministic Reduction From Gomory-Hu Tree to Maxflow and Expander Decomposition
par: Gutenberg, Maximilian Probst, et autres
Publié: (2025)

Parameterized Algorithms for Minimum Sum Vertex Cover
par: Aute, Shubhada, et autres
Publié: (2024)

Minimum Temporal Spanners in Happy Graphs
par: Casteigts, Arnaud, et autres
Publié: (2026)

Beyond Worst Case Local Computation Algorithms
par: Biswas, Amartya Shankha, et autres
Publié: (2024)

Worst-Case to Expander-Case Reductions: Derandomized and Generalized
par: Abboud, Amir, et autres
Publié: (2024)

Faster Weak Expander Decompositions and Approximate Max Flow
par: Fleischmann, Henry, et autres
Publié: (2025)