Treffer: Distribution-sensitive set multi-partitioning
Title:
Distribution-sensitive set multi-partitioning
Authors:
Contributors:
Department of Computer and Systems Engineering [Alexandria], Alexandria University [Alexandrie], Conrado Martìnez
Source:
2005 International Conference on Analysis of Algorithms. :353-356
Publisher Information:
HAL CCSD; Discrete Mathematics and Theoretical Computer Science; DMTCS, 2005.
Publication Year:
2005
Collection:
collection:DMTCS
collection:TDS-MACS
collection:TDS-MACS
Subject Terms:
algorithm analysis and design, distribution-sensitive algorithms, output-sensitive algorithms, lower bounds, [INFO.INFO-DS]Computer Science [cs], Data Structures and Algorithms [cs.DS], [INFO.INFO-DM]Computer Science [cs], Discrete Mathematics [cs.DM], [MATH.MATH-CO]Mathematics [math], Combinatorics [math.CO], [INFO.INFO-CG]Computer Science [cs], Computational Geometry [cs.CG]
Subject Geographic:
Original Identifier:
HAL: hal-01184216
Document Type:
Konferenz
conferenceObject<br />Conference papers
Language:
English
ISSN:
1462-7264
1365-8050
1365-8050
Relation:
info:eu-repo/semantics/altIdentifier/doi/10.46298/dmtcs.3381
DOI:
10.46298/dmtcs.3381
Access URL:
Rights:
info:eu-repo/semantics/OpenAccess
Accession Number:
edshal.hal.01184216v1
Database:
HAL
Weitere Informationen
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.