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.
Type de document :
Communication dans un congrès
Michel Morvan AND C. Meinel AND D. Krob. 15th Symposium on Theoretical Aspects of Computer Science (STACS), 1998, Paris, France. Springer Berlin / Heidelberg, 1373, pp.25-38, 1998, Lecture Notes in Computer Science. 〈10.1007/BFb0028546〉
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00471611
Contributeur : Laurent Viennot <>
Soumis le : jeudi 8 avril 2010 - 16:13:36
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : vendredi 9 juillet 2010 - 21:18:11

Fichiers

stacs98.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Michel Habib, Christophe Paul, Laurent Viennot. A Synthesis on Partition Refinement: a Usefull Routine for Strings, Graphs, Boolean Matrices and Automata. Michel Morvan AND C. Meinel AND D. Krob. 15th Symposium on Theoretical Aspects of Computer Science (STACS), 1998, Paris, France. Springer Berlin / Heidelberg, 1373, pp.25-38, 1998, Lecture Notes in Computer Science. 〈10.1007/BFb0028546〉. 〈inria-00471611〉

Partager

Métriques

Consultations de la notice

202

Téléchargements de fichiers

195