A Synthesis on Partition Refinement: a Usefull Routine for Strings, Graphs, Boolean Matrices and Automata

Abstract : Partition refinement techniques are used in many algorithms. This tool allows efficient computation of equivalence relations and is somehow dual to union-find algorithms. The goal of this paper is to propose a single routine to quickly implement all these already known algorithms and to solve a large class of potentially new problems. Our framework yields to a unique scheme for correctness proofs and complexity analysis. Various examples are presented to show the different ways of using this routine.
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/inria-00471611
Contributor : Laurent Viennot <>
Submitted on : Thursday, April 8, 2010 - 4:13:36 PM
Last modification on : Friday, January 4, 2019 - 5:32:57 PM
Long-term archiving on : Friday, July 9, 2010 - 9:18:11 PM

Files

stacs98.pdf
Files produced by the author(s)

Identifiers

Citation

Michel Habib, Christophe Paul, Laurent Viennot. A Synthesis on Partition Refinement: a Usefull Routine for Strings, Graphs, Boolean Matrices and Automata. 15th Symposium on Theoretical Aspects of Computer Science (STACS), 1998, Paris, France. pp.25-38, ⟨10.1007/BFb0028546⟩. ⟨inria-00471611⟩

Share

Metrics

Record views

224

Files downloads

215