Distribution-sensitive set multi-partitioning

Amr Elmasry 1
1 Department of Computer and Systems Engineering [Alexandria]
Abstract : Given a set $\mathcal{S}$ with real-valued members, associated with each member one of two possible types; a multi-partitioning of $\mathcal{S}$ is a sequence of the members of $\mathcal{S}$ such that if $x,y \in \mathcal{S}$ have different types and $x < y$, $x$ precedes $y$ in the multi-partitioning of $\mathcal{S}$. We give two distribution-sensitive algorithms for the set multi-partitioning problem and a matching lower bound in the algebraic decision-tree model. One of the two algorithms can be made stable and can be implemented in place. We also give an output-sensitive algorithm for the problem.
Keywords : lower bounds algorithm analysis and design distribution-sensitive algorithms output-sensitive algorithms
Type de document :
Communication dans un congrès
Conrado Martìnez. 2005 International Conference on Analysis of Algorithms, 2005, Barcelona, Spain. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms, pp.353-356, 2005, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-01184216
Contributeur : Coordination Episciences Iam <>
Soumis le : jeudi 13 août 2015 - 13:34:46
Dernière modification le : jeudi 11 mai 2017 - 01:02:54
Document(s) archivé(s) le : samedi 14 novembre 2015 - 10:23:19

Fichier

dmAD0132.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01184216, version 1

Collections

INSMI | TDS-MACS

Citation

Amr Elmasry. Distribution-sensitive set multi-partitioning. Conrado Martìnez. 2005 International Conference on Analysis of Algorithms, 2005, Barcelona, Spain. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms, pp.353-356, 2005, DMTCS Proceedings. 〈hal-01184216〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

51

Téléchargements de fichiers

127

Contact


archive-ouverte@inria.fr