View in EDS

Algorithms and Lower Bounds for Ordering Problems on Strings

Saved in:
Bibliographic Details
Title: Algorithms and Lower Bounds for Ordering Problems on Strings
Authors: Gibney, Daniel
Committee Members: Valliyil Thankachan, Sharma
Summary: This dissertation presents novel algorithms and conditional lower bounds for a collection of string and text-compression-related problems. These results are unified under the theme of ordering constraint satisfaction. Utilizing the connections to ordering constraint satisfaction, we provide hardness results and algorithms for the following: recognizing a type of labeled graph amenable to text-indexing known as Wheeler graphs, minimizing the number of maximal unary substrings occurring in the Burrows-Wheeler Transformation of a text, minimizing the number of factors occurring in the Lyndon factorization of a text, and finding an optimal reference string for relative Lempel-Ziv encoding.
URL: https://stars.library.ucf.edu/etd2020/507
Database: OpenDissertations
FullText Text:
  Availability: 0
Header DbId: ddu
DbLabel: OpenDissertations
An: ddu.oai.stars.library.ucf.edu.etd2020.1506
AccessLevel: 6
PubType: Dissertation/ Thesis
PubTypeId: dissertation
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Algorithms and Lower Bounds for Ordering Problems on Strings
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Gibney%2C+Daniel%22">Gibney, Daniel</searchLink>
– Name: Author
  Label: Committee Members
  Group: Au
  Data: <searchLink fieldCode="CO" term="%22Valliyil+Thankachan%2C+Sharma%22">Valliyil Thankachan, Sharma</searchLink>
– Name: Abstract
  Label: Summary
  Group: Ab
  Data: This dissertation presents novel algorithms and conditional lower bounds for a collection of string and text-compression-related problems. These results are unified under the theme of ordering constraint satisfaction. Utilizing the connections to ordering constraint satisfaction, we provide hardness results and algorithms for the following: recognizing a type of labeled graph amenable to text-indexing known as Wheeler graphs, minimizing the number of maximal unary substrings occurring in the Burrows-Wheeler Transformation of a text, minimizing the number of factors occurring in the Lyndon factorization of a text, and finding an optimal reference string for relative Lempel-Ziv encoding.
– Name: URL
  Label: URL
  Group: URL
  Data: <link linkTarget="URL" linkTerm="https://stars.library.ucf.edu/etd2020/507" linkWindow="_blank">https://stars.library.ucf.edu/etd2020/507</link>
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=ddu&AN=ddu.oai.stars.library.ucf.edu.etd2020.1506
RecordInfo BibRecord:
  BibEntity:
    Languages:
      – Code: eng
        Text: English
    Subjects:
      – SubjectFull: String algorithms; Text compression; Ordering constraints; Graph indexing; Lempel-Ziv encoding
        Type: general
      – SubjectFull: Computer Sciences
        Type: general
      – SubjectFull: Dissertations, Academic--Mathematics; Algorithms--Research; Combinatorial optimization; Graph theory --Extremal problems; Data compression (Computer science)--Computer programs
        Type: general
    Titles:
      – TitleFull: Algorithms and Lower Bounds for Ordering Problems on Strings
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Gibney, Daniel
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 01
              Type: published
              Y: 2021
ResultId 1