A Linear Time Algorithm for Ordered Partition

DOI10.1007/978-3-319-19647-3_9MaRDI QIDQ3452555zbMATH OpenOpenAlexFDO

Authors Yijie Han

Publication date 12 November 2015

Published in Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-19647-3_9

zbMATH Keywords

algorithmshashinginteger sortinglinear-time algorithmordered partitionperfect hash functionssorting

Mathematics Subject Classification ID

Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A linear time algorithm for graph partition problems
• scientific article; zbMATH DE number 1559404
• scientific article; zbMATH DE number 3908442
• scientific article; zbMATH DE number 3883625
• Generic top-down discrimination for sorting and partitioning in linear time
• Partitioning of sequentially ordered systems using linear programming
• Partitioning arrangements of lines. I: An efficient deterministic algorithm
• scientific article; zbMATH DE number 626017
• A linear partitioning algorithm for hybrid Lyndons using \(V\)-order

Cites work

• A Reliable Randomized Algorithm for the Closest-Pair Problem
• Conservative algorithms for parallel and sequential integer sorting
• Deterministic sorting in O(nloglogn) time and linear space
• Expected linear time sorting for word size \(\Omega (\log ^{2} n \log\log n)\)
• Parallel Integer Sorting Is More Efficient Than Parallel Comparison Sorting on Exclusive Write PRAMs
• Priority queues: small, monotone and trans-dichotomous
• Sorting in linear time?
• Time bounds for selection
• Upper bounds for sorting integers on random access machines

Cited in

(4)

• Sorting real numbers in \(O(n \sqrt{\log n})\) time and linear space
• Construct a perfect word hash function in time independent of the size of integers
• Queueing and glueing for optimal partitioning (functional pearl)
• An set refinement algorithm with applications

This page was built for publication: A Linear Time Algorithm for Ordered Partition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3452555)