Paper Info
Title
Some Lower Bounds for Comparison-Based Algorithms
Abstract
Any comparison-based algorithm for solving a given problem can be viewed as a partial order production. The productions of some particular partial orders, such as sorting and selection, have received much attention in the past decades. As to general partial orders, very little is known about the inherent complexity of their productions. This paper investigates how different sequences of comparisons affect the complexity of the production.
Year
DOI
Venue
1994
10.1007/BFb0049401
ESA
Keywords
Field
DocType
lower bounds,comparison-based algorithms,lower bound,partial order
Discrete mathematics,Binomial options pricing model,Combinatorics,Hasse diagram,Algorithm,Sorting,Folk theorem,Mathematics
Conference
ISBN
Citations 
PageRank 
3-540-58434-X
1
0.36
References 
Authors
8
2
Name
Order
Citations
PageRank
Svante Carlsson176490.17
Jingsen Chen2669.80