Cover Image

Stochastic Minimum Spanning Trees with a Single Sample

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Hoeksma, Ruben, Speek, Gavin, Uetz, Marc
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Stochastic scheduling with Bernoulli-type jobs through policy stratification
by: Antoniadis, Antonios, et al.
Published: (2025)

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

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

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

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

Competitive Online Transportation Simplified
by: Arndt, Stephen, et al.
Published: (2025)

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

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

Additive One Approximation for Minimum Degree Spanning Tree: Breaking the $O(mn)$ Time Barrier
by: Bhattacharya, Sayan, et al.
Published: (2026)

Refining the Complexity Landscape of Speed Scaling: Hardness and Algorithms
by: Antoniadis, Antonios, et al.
Published: (2025)

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

Faster Private Minimum Spanning Trees
by: Pagh, Rasmus, et al.
Published: (2024)

Quantum Speedup for Sampling Random Spanning Trees
by: Apers, Simon, et al.
Published: (2025)

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

Online Disjoint Spanning Trees and Polymatroid Bases
by: Chandrasekaran, Karthekeyan, et al.
Published: (2025)

Spanning and Metric Tree Covers Parameterized by Treewidth
by: Elkin, Michael, et al.
Published: (2025)

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

Space Complexity of Minimum Cut Problems in Single-Pass Streams
by: Ding, Matthew, et al.
Published: (2024)

Two Complexity Results on Spanning-Tree Congestion Problems
by: Atalig, Sunny, et al.
Published: (2026)

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

Finding a Minimum Spanning Tree with a Small Non-Terminal Set
by: Hanaka, Tesshu, et al.
Published: (2023)

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

Optimal Bounds for Private Minimum Spanning Trees via Input Perturbation
by: Pagh, Rasmus, et al.
Published: (2024)

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

Parameterized Algorithms for Spanning Tree Isomorphism by Redundant Set Size
by: Shen, Fangjian, et al.
Published: (2025)

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

Thin Trees for Near Minimum Cuts
by: Klein, Nathan, et al.
Published: (2026)

Online Stochastic Matching with Unknown Arrival Order: Beating $0.5$ against the Online Optimum
by: Sun, Enze, et al.
Published: (2025)

Finding Spanning Trees with Perfect Matchings
by: Bérczi, Kristóf, et al.
Published: (2024)

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

Minimum Sum Coloring with Bundles in Trees and Bipartite Graphs
by: Ito, Takehiro, et al.
Published: (2025)

Light Tree Covers, Routing, and Path-Reporting Oracles via Spanning Tree Covers in Doubling Graphs
by: Chang, Hsien-Chih, et al.
Published: (2025)

Sample-Based Matroid Prophet Inequalities
by: Fu, Hu, et al.
Published: (2024)

Above-Guarantee Algorithm for Properly Colored Spanning Trees
by: Bai, Yuhang, et al.
Published: (2026)

Spanning tree congestion of proper interval graphs
by: Otachi, Yota
Published: (2026)

Witty: An Efficient Solver for Computing Minimum-Size Decision Trees
by: Staus, Luca Pascal, et al.
Published: (2024)

Fast Spanning Tree Sampling in Broadcast Congested Clique
by: Anari, Nima, et al.
Published: (2026)

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

Generating the Spanning Trees of Series-Parallel Graphs up to Graph Automorphism
by: Karamchedu, Mithra, et al.
Published: (2025)

Maximizing the Minimum Eigenvalue in Constant Dimension
by: Brown, Adam, et al.
Published: (2024)