Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Computing maximum-scoring segments in almost linear time
Luleå tekniska universitet, Institutionen för system- och rymdteknik, Datavetenskap.
Luleå tekniska universitet, Institutionen för system- och rymdteknik, Datavetenskap.
2006 (Engelska)Ingår i: Computing and Combinatorics: 12th annual international conference, COCOON 2006, Taipei, Taiwan, August 15 - 18, 2006 ; proceedings / [ed] Danny Z. Chen, Encyclopedia of Global Archaeology/Springer Verlag, 2006, s. 255-264Konferensbidrag, Publicerat paper (Refereegranskat)
Abstract [en]

Given a sequence, the problem studied in this paper is to find a set of k disjoint continuous subsequences such that the total sum of all elements in the set is maximized. This problem arises naturally in the analysis of DNA sequences. The previous best known algorithm requires Θ(n log n) time in the worst case. For a given sequence of length n, we present an almost linear-time algorithm for this problem. Our algorithm uses a disjoint-set data structure and requires O(nα(n, n)) time in the worst case, where α(n, n) is the inverse Ackermann function.

Ort, förlag, år, upplaga, sidor
Encyclopedia of Global Archaeology/Springer Verlag, 2006. s. 255-264
Serie
Lecture Notes in Computer Science, ISSN 0302-9743 ; 4112
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
Kommunikations- och beräkningssystem
Identifikatorer
URN: urn:nbn:se:ltu:diva-31459DOI: 10.1007/11809678_28Lokalt ID: 5a2a9d00-7bed-11dc-a72d-000ea68e967bISBN: 978-3-540-36925-7 (tryckt)OAI: oai:DiVA.org:ltu-31459DiVA, id: diva2:1004693
Konferens
Annual International Computing and Combinatorics Conference : 15/08/2006 - 18/08/2006
Anmärkning
Validerad; 2006; 20071016 (bson)Tillgänglig från: 2016-09-30 Skapad: 2016-09-30 Senast uppdaterad: 2018-01-14Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltext

Personposter BETA

Bengtsson, FredrikChen, Jingsen

Sök vidare i DiVA

Av författaren/redaktören
Bengtsson, FredrikChen, Jingsen
Av organisationen
Datavetenskap
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetricpoäng

doi
isbn
urn-nbn
Totalt: 71 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf