Paper

{
  "raw_xml": "<entry>\n    <id>http://arxiv.org/abs/2603.02006v1</id>\n    <title>Kruskal-EDS: Edge Dynamic Stratification</title>\n    <updated>2026-03-02T15:55:12Z</updated>\n    <link href='https://arxiv.org/abs/2603.02006v1' rel='alternate' type='text/html'/>\n    <link href='https://arxiv.org/pdf/2603.02006v1' rel='related' title='pdf' type='application/pdf'/>\n    <summary>We introduce Kruskal-EDS (Edge Dynamic Stratification), a distribution-adaptive variant of Kruskal's minimum spanning tree (MST) algorithm that replaces the mandatory $Θ$(m log m) global sort with a three-phase$\\sqrt$procedure inspired by Birkhoff's ergodic theorem. In Phase 1, a sample of m edges estimates the weight distribution in O (m log m) time. In Phase 2, all m edges are assigned to k strata in O(m log k) time via binary search on quantile boundaries - no global sort. In Phase 3, strata are sorted and processed in order; execution halts as soon as n--1 MST edges are accepted. We prove an effective complexity of O(m + p $\\times$ (m/k) log(m/k)), where p $\\le$ k is the number of strata actually processed. On sparse graphs or heavy-tailed weight distributions, p $\\ll$ k and the algorithm achieves near-O(m) behaviour. We further derive the optimal p strata count k$\\star$ = ___ m/ ln(m + 1) ___, balancing partition overhead against intra-stratum sort cost. An extensive benchmark on 14 graph families demonstrates correctness on 12 test cases and practical speedups reaching 10x in wall-clock time and 33x in sort operations over standard Kruskal. A 3-dimensional TikZ visualisation of the complexity landscape illus- trates the algorithm's adaptive behaviour as a function of graph density and weight distri- bution skewness.</summary>\n    <category scheme='http://arxiv.org/schemas/atom' term='cs.DS'/>\n    <published>2026-03-02T15:55:12Z</published>\n    <arxiv:primary_category term='cs.DS'/>\n    <author>\n      <name>Yves Mercadier</name>\n      <arxiv:affiliation>LIRMM</arxiv:affiliation>\n    </author>\n  </entry>"
}