Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Some lower bounds for comparison-based algorithms
Luleå tekniska universitet.
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
1994 (English)In: Algorithms - ESA '94: Second Annual European Symposium Utrecht, The Netherlands, September 26-28, 1994 Proceedings / [ed] Jan van Leeuwen, Encyclopedia of Global Archaeology/Springer Verlag, 1994, p. 106-117Conference paper, Published paper (Refereed)
Abstract [en]

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. We first disprove a folk theorem stating that there always exists an optimal algorithm for producing a partial order that involves the maximum number of disjoint comparisons between singleton elements. We also present some algorithmic properties of partial orders, which demand that any optimal production algorithm must make the all possible disjoint comparisons. Moreover, we show how to and when one can save comparisons in producing a given partial order by constructing many isomorphic copies of the partial order simultaneously or by providing extra elements. Furthermore, the techniques obtained and the results presented have been successful applied to investigate the problem of constructing data structures, resulting in efficient algorithms and tight lower bounds.

Place, publisher, year, edition, pages
Encyclopedia of Global Archaeology/Springer Verlag, 1994. p. 106-117
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 855
National Category
Computer Sciences
Research subject
Dependable Communication and Computation Systems
Identifiers
URN: urn:nbn:se:ltu:diva-37998DOI: 10.1007/BFb0049401Local ID: c3cb8280-a7f6-11dc-9534-000ea68e967bISBN: 978-3-540-58434-6 (print)OAI: oai:DiVA.org:ltu-37998DiVA, id: diva2:1011497
Conference
Annual European Symposium on Algorithms (ESA'94) : 26/09/1994 - 28/09/1994
Note
Godkänd; 1994; 20071211 (ysko)Available from: 2016-10-03 Created: 2016-10-03 Last updated: 2018-01-14Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Search in DiVA

By author/editor
Chen, Jingsen
By organisation
Computer Science
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 29 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf