Two choices suffice: k-out sampling leaves O(n/k) intercomponent edges for k at least 2
cs.DM, cs.DS, math.CO
Submitted: 2026-10-30
Updated: 2026-10-30
Terminology
Sources
- Spanning Adjacency Oracles in Sublinear Time
- ConnectIt: A Framework for Static and Incremental Parallel Graph Connectivity Algorithms
Related papers
- Low-Temperature Sampling via Equilibrium Disagreements
- An Improved Bound for Testing k-Colorability
- Temporal Cliques Admit Linear Spanners
- Multiway Partition is FPT for Connectivity Functions
- Profile and neighbourhood complexity of graphs excluding a minor and tree-structured graphs
- Constrained intersection representations and forbidden patterns