TY - GEN
T1 - On the readability of overlap digraphs
AU - Chikhi, Rayan
AU - Medvedev, Paul
AU - Milanič, Martin
AU - Raskhodnikova, Sofya
N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2015.
PY - 2015
Y1 - 2015
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84949008172&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84949008172&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-19929-0_11
DO - 10.1007/978-3-319-19929-0_11
M3 - Conference contribution
AN - SCOPUS:84949008172
SN - 9783319199283
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 124
EP - 137
BT - Combinatorial Pattern Matching - 26th Annual Symposium, CPM 2015, Proceedings
A2 - Vaccaro, Ugo
A2 - Porat, Ely
A2 - Cicalese, Ferdinando
PB - Springer Verlag
T2 - 26th Annual Symposium on Combinatorial Pattern Matching, CPM 2015
Y2 - 29 June 2015 through 1 July 2015
ER -