skip to main content
Explore Scholarly Publications and Datasets in the NSF-PAR

  • Home
  • Search Results
  • Page 1 of 2

Search for: All records

Creators/Authors contains: "Gibney, Daniel"

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. ; ( , Algorithmica)
    Free, publicly-accessible full text available March 1, 2023
  2. ; ; ( , Research in Computational Molecular Biology - 26th Annual International Conference, RECOMB 2022)
    Free, publicly-accessible full text available January 1, 2023
  3. ; ; ( , Research in Computational Molecular Biology - 26th Annual International Conference, RECOMB 2022)
    Free, publicly-accessible full text available January 1, 2023
  4. ; ; ( , 4th Symposium on Simplicity in Algorithms, SOSA 2021)
    Full Text Available 
  5. ; ; ; ( , 28th Annual European Symposium on Algorithms, ESA 2020)
    Full Text Available 
  6. ; ; ; ( , 28th Annual European Symposium on Algorithms, ESA 2020)
    Accepted Manuscript Full Text Available
  7. ; ; ; ; ( , 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020, June 17-19, 2020, Copenhagen, Denmark)
    Accepted Manuscript Full Text Available
  8. ; ; ; ; ( , 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020)
    Full Text Available 
  9. ; ( , 27th Annual European Symposium on Algorithms (ESA) 2019)
    In recent years several compressed indexes based on variants of the Burrows-Wheeler transformation have been introduced. Some of these are used to index structures far more complex than a single string, as was originally done with the FM-index [Ferragina and Manzini, J. ACM 2005]. As such, there has been an increasing effort to better understand under which conditions such an indexing scheme is possible. This has led to the introduction of Wheeler graphs [Gagie et al., Theor. Comput. Sci., 2017]. Gagie et al. showed that de Bruijn graphs, generalized compressed suffix arrays, and several other BWT related structures can bemore »represented as Wheeler graphs and that Wheeler graphs can be indexed in a way which is space-efficient. Hence, being able to recognize whether a given graph is a Wheeler graph, or being able to approximate a given graph by a Wheeler graph, could have numerous applications in indexing. Here we resolve the open question of whether there exists an efficient algorithm for recognizing if a given graph is a Wheeler graph. We present - The problem of recognizing whether a given graph G=(V,E) is a Wheeler graph is NP-complete for any edge label alphabet of size sigma >= 2, even when G is a DAG. This holds even on a restricted, subset of graphs called d-NFA's for d >= 5. This is in contrast to recent results demonstrating the problem can be solved in polynomial time for d-NFA's where d <= 2. We also show the recognition problem can be solved in linear time for sigma =1; - There exists an 2^{e log sigma + O(n + e)} time exact algorithm where n = |V| and e = |E|. This algorithm relies on graph isomorphism being computable in strictly sub-exponential time; - We define an optimization variant of the problem called Wheeler Graph Violation, abbreviated WGV, where the aim is to remove the minimum number of edges in order to obtain a Wheeler graph. We show WGV is APX-hard, even when G is a DAG, implying there exists a constant C >= 1 for which there is no C-approximation algorithm (unless P = NP). Also, conditioned on the Unique Games Conjecture, for all C >= 1, it is NP-hard to find a C-approximation; - We define the Wheeler Subgraph problem, abbreviated WS, where the aim is to find the largest subgraph which is a Wheeler Graph (the dual of the WGV). In contrast to WGV, we prove that the WS problem is in APX for sigma=O(1); The above findings suggest that most problems under this theme are computationally difficult. However, we identify a class of graphs for which the recognition problem is polynomial-time solvable, raising the open question of which parameters determine this problem's difficulty.« less
    Full Text Available 
  10. ; ; ; ; ( , 2018 IEEE 8th International Conference on Computational Advances in Bio and Medical Sciences (ICCABS))
    Full Text Available