On the readability of overlap digraphs

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We introduce the graph parameter readability and study it as a function of the number of vertices in a graph. Given a digraph D, an injective overlap labeling assigns a unique string to each vertex such that there is an arc from x to y if and only if x properly overlaps y. The readability of D is the minimum string length for which an injective overlap labeling exists. In applications that utilize overlap digraphs (e.g., in bioinformatics), readability reflects the length of the strings from which the overlap digraph is constructed. We study the asymptotic behaviour of readability by casting it in purely graph theoretic terms (without any reference to strings). We prove upper and lower bounds on readability for certain graph families and general graphs.

Original languageEnglish (US)
Title of host publicationCombinatorial Pattern Matching - 26th Annual Symposium, CPM 2015, Proceedings
EditorsUgo Vaccaro, Ely Porat, Ferdinando Cicalese
PublisherSpringer Verlag
Pages124-137
Number of pages14
ISBN (Print)9783319199283
DOIs
StatePublished - 2015
Event26th Annual Symposium on Combinatorial Pattern Matching, CPM 2015 - Ischia Island, Italy
Duration: Jun 29 2015Jul 1 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9133
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other26th Annual Symposium on Combinatorial Pattern Matching, CPM 2015
Country/TerritoryItaly
CityIschia Island
Period6/29/157/1/15

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'On the readability of overlap digraphs'. Together they form a unique fingerprint.

Cite this