On the readability of overlap digraphs

DOI10.1016/j.dam.2015.12.009zbMath1333.05134OpenAlexW2962911156MaRDI QIDQ266924

Sofya Raskhodnikova, Rayan Chikhi, Paul Medvedev, Martin Milanič

Publication date: 7 April 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2015.12.009

zbMATH Keywords

bioinformaticsgraph parameteroverlap graphreadabilitystringology

Mathematics Subject Classification ID

Applications of graph theory (05C90) Directed graphs (digraphs), tournaments (05C20)

Related Items

Classification of de Bruijn-based labeled digraphs, Bipartite graphs of small readability

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Recognition of overlap graphs
• A greedy approximation algorithm for constructing shortest common superstrings
• On the recognition of de Bruijn graphs and their induced subgraphs
• Recognizing DNA graphs is difficult.
• On some properties of DNA graphs
• Embedding on alphabet overlap digraphs
• Characterizations for some types of DNA graphs
• \boldmath A $2\frac12$-Approximation Algorithm for Shortest Superstring