8 citations · 54 across the 39 of their papers we have counts for
5 papers · 1 filter
On Restricted Disjunctive Temporal Problems: Faster Algorithms and Tractability Frontier
Carlo Comin, Romeo Rizzi
In 2005 Kumar studied the Restricted Disjunctive Temporal Problem (RDTP), a restricted but very expressive class of disjunctive temporal problems (DTPs). It was shown that that RDT…
Hardness of Covering Alignment: Phase Transition in Post-Sequence Genomics
Romeo Rizzi, Massimo Cairo, Veli Mäkinen +2
Covering alignment problems arise from recent developments in genomics; so called pan-genome graphs are replacing reference genomes, and advances in haplotyping enable full content…
The Complexity of Simulation and Matrix Multiplication
Massimo Cairo, Romeo Rizzi
Computing the simulation preorder of a given Kripke structure (i.e., a directed graph with labeled vertices) has crucial applications in model checking of temporal logic. It am…
Checking Dynamic Consistency of Conditional Hyper Temporal Networks via Mean Payoff Games (Hardness and (pseudo) Singly-Exponential Time Algorithm)
Carlo Comin, Romeo Rizzi
In this work we introduce the \emph{Conditional Hyper Temporal Network (CHyTN)} model, which is a natural extension and generalization of both the \CSTN and the \HTN model. Our con…
Some results on more flexible versions of Graph Motif
Romeo Rizzi, Florian Sikora
The problems studied in this paper originate from Graph Motif, a problem introduced in 2006 in the context of biological networks. Informally speaking, it consists in deciding if a…