DOAJ
Open Access
2005
Distribution-sensitive set multi-partitioning
Amr Elmasry
Abstrak
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.
Topik & Kata Kunci
Penulis (1)
A
Amr Elmasry
Akses Cepat
Informasi Jurnal
- Tahun Terbit
- 2005
- Sumber Database
- DOAJ
- DOI
- 10.46298/dmtcs.3381
- Akses
- Open Access ✓