Analysis and enumeration. Algorithms for biological graphs (Q2353660)

This monograph presents the Ph.D. dissertation of the author written under the supervision of Professor Pierluigi Crescenzi, University of Firenze, Italy. It is devoted to the investigation of efficient enumeration algorithms on biological graphs. Such enumeration algorithms are extremely helpful for the investigation of graphs representing biological networks having several bias features. Among the results, there is a detailed description of algorithms for enumeration with the following invariants: {\parindent=0.6cm \begin{itemize}\item[--] all diametral and radial vertices, \item[--] all maximal directed acyclic sub-graphs in which sources and targets belong to a predefined subset of the vertices, \item[--] all cycles and/or paths in an undirected graph, \item[--] all pairs of \((s,t)\)-paths sharing only nodes \(s\) and \(t\). \end{itemize}} A number of examples illustrating the work of these algorithms is presented and several open problems concerning complexity of these algorithms are formulated.