Relational Minimum Spanning Tree Algorithms

Walter Guttmann and Nicolas Robinson-O’Brien

8 December 2020

Abstract

We verify the correctness of Prim's, Kruskal's and Borůvka's minimum spanning tree algorithms based on algebras for aggregation and minimisation.
BSD License

Depends On

Topics

Related Entries

Theories

Cite

×
@article{Relational_Minimum_Spanning_Trees-AFP,
  author  = {Walter Guttmann and Nicolas Robinson-O'Brien},
  title   = {Relational Minimum Spanning Tree Algorithms},
  journal = {Archive of Formal Proofs},
  month   = December,
  year    = 2020,
  note    = {\url{http://isa-afp.org/entries/Relational_Minimum_Spanning_Trees.html},
            Formal proof development},
  ISSN    = {2150-914x},
}
Download