An algebraic framework for minimum spanning tree problems

DOI10.1016/j.tcs.2018.04.012zbMath1401.68246OpenAlexW2802771107MaRDI QIDQ1786562

Walter Guttmann

Publication date: 24 September 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2018.04.012

zbMATH Keywords

relationsaggregationweighted graphsformal methodsKleene algebrasStone algebrascorrectness proof

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)

Related Items

Reasoning About Algebraic Structures with Implicit Carriers in Isabelle/HOL, Second-order properties of undirected graphs, Relation-algebraic verification of Borůvka's minimum spanning tree algorithm, Relational characterisations of paths, Verifying minimum spanning tree algorithms with Stone relation algebras, Improving dynamic programming for travelling salesman with precedence constraints: parallel Morin–Marsten bounding

Uses Software

• Isabelle
• RelView
• Isabelle/HOL
• HOL
• Sledgehammer
• Stone Algebras
• Archive Formal Proofs
• Algorithm 97
• Relation Algebra
• Kleene Algebra

Cites Work

• A note on two problems in connexion with graphs
• Relational style laws and constructs of linear algebra
• The saga of minimum spanning trees
• Abstract abstract reduction
• The verified incremental design of a distributed spanning tree algorithm: Extended abstract
• The Min-Max Spanning Tree Problem and some extensions
• Winskel is (almost) right: Towards a mechanized semantics textbook
• A completeness theorem for Kleene algebras and the algebra of regular events
• Relation-algebraic semantics
• Isabelle/HOL. A proof assistant for higher-order logic
• A new algebraic approach to L-fuzzy relations convenient to study crispness
• Lattices and ordered algebraic structures
• Towards a linear algebra of programming
• Dijkstra, Floyd and Warshall meet Kleene
• Categorical representation theorems of fuzzy relations
• Computing tournament solutions using relation algebra and RelView
• Theory of T-norms and fuzzy inference methods
• Combining relation algebra and data refinement to develop rectangle-based functional programs for reflexive-transitive closures
• A linear algebra approach to OLAP
• Absorbent tuples of aggregation operators
• Graphs, dioids and semirings. New models and algorithms.
• L-fuzzy sets
• Concrete Semantics
• Relation-Algebraic Verification of Prim’s Minimum Spanning Tree Algorithm
• C-semiring Frameworks for Minimum Spanning Tree Problems
• Totally ordered commutative semigroups
• Relations among Matrices over a Semiring
• Regular Algebra Applied to Path-finding Problems
• On the History of the Minimum Spanning Tree Problem
• Extended Static Checking by Calculation Using the Pointfree Transform
• Extending Sledgehammer with SMT Solvers
• Stone Relation Algebras
• WEIGHTED AUTOMATA AS COALGEBRAS IN CATEGORIES OF MATRICES
• On the Cardinality of Relations
• A Theorem on Boolean Matrices
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item