Formal derivation of spanning trees algorithms

Jean-Raymond Abrial Dominique Cansell 1 Dominique Méry 1
1 MOSEL - Proof-oriented development of computer-based systems
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : Graphs algorithms and graph-theoretical problems provide a challenging battlefield for the incremental development of proved models. The B event-based approach implements the incremental and proved development of abstract models which are translated into algorithms; we focus our methodology on the minimum spanning tree problem and on Prim's algorithm. The correctness of the resulting solution is based on properties over trees and we show how the greedy strategy is efficient in this case. We compare properties proven mechanically to the properties found in a classical algorithms textbook.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/inria-00099793
Contributor : Publications Loria <>
Submitted on : Tuesday, September 26, 2006 - 9:41:16 AM
Last modification on : Thursday, September 19, 2019 - 5:00:14 PM

Identifiers

  • HAL Id : inria-00099793, version 1

Collections

Citation

Jean-Raymond Abrial, Dominique Cansell, Dominique Méry. Formal derivation of spanning trees algorithms. Third International Conference of B and Z Users - ZB'2003, Marina Walden, 2003, Turku, Finland, pp.457-476. ⟨inria-00099793⟩

Share

Metrics

Record views

167