On the Readability of Overlap Digraphs

DOI10.1007/978-3-319-19929-0_11MaRDI QIDQ2942251zbMATH OpenOpenAlexFDO

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

Publication date 20 August 2015

Published in Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.04616

zbMATH Keywords

graph parameter readability injective overlap labeling

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20)

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

Recommendations

Cites work

Cited in

(5)

This page was built for publication: On the Readability of Overlap Digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2942251)