Geodesic
Distribution-sensitive set multi-partitioning
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms (2005).

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2005_special_249_a29,
     author = {Elmasry, Amr},
     title = {Distribution-sensitive set multi-partitioning},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms},
     year = {2005},
     doi = {10.46298/dmtcs.3381},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3381/}
}
TY  - JOUR
AU  - Elmasry, Amr
TI  - Distribution-sensitive set multi-partitioning
JO  - Discrete mathematics & theoretical computer science
PY  - 2005
VL  - DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3381/
DO  - 10.46298/dmtcs.3381
LA  - en
ID  - DMTCS_2005_special_249_a29
ER  - 
%0 Journal Article
%A Elmasry, Amr
%T Distribution-sensitive set multi-partitioning
%J Discrete mathematics & theoretical computer science
%D 2005
%V DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3381/
%R 10.46298/dmtcs.3381
%G en
%F DMTCS_2005_special_249_a29
Elmasry, Amr. Distribution-sensitive set multi-partitioning. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms (2005). doi : 10.46298/dmtcs.3381. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3381/

Cité par Sources :