4 citations · 7 across the 11 of their papers we have counts for
13 papers
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…
Linear-Time Safe-Alternating DFS and SCCs
Carlo Comin, Romeo Rizzi
An alternating graph is a directed graph whose vertex set is partitioned into two classes, existential and universal. This forms the basic arena for a plethora of infinite duration…
Faster O(|V|^2|E|W)-Time Energy Algorithms for Optimal Strategy Synthesis in Mean Payoff Games
Carlo Comin, Romeo Rizzi
This study strengthens the links between Mean Payoff Games (\MPG{s}) and Energy Games (EG{s}). Firstly, we offer a faster pseudo-polynomial time and spa…
Instantaneous Reaction-Time in Dynamic-Consistency Checking of Conditional Simple Temporal Networks -- Extended version with an Improved Upper Bound --
Massimo Cairo, Carlo Comin, Romeo Rizzi
CSTNs is a constraint-based graph-formalism for conditional temporal planning. In order to address the DC-Checking problem, in [Comin and Rizzi, TIME 2015] we introduced epsilon-DC…
Sorting With Forbidden Intermediates
Carlo Comin, Anthony Labarre, Romeo Rizzi +1
A wide range of applications, most notably in comparative genomics, involve the computation of a shortest sorting sequence of operations for a given permutation, where the set of a…
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…
Energy Structure of Optimal Positional Strategies in Mean Payoff Games
Carlo Comin
This note studies structural aspects concerning Optimal Positional Strategies (OPSs) in Mean Payoff Games (MPGs), it is a contribution to understanding the relationship between OPS…
An Improved Upper Bound on Maximal Clique Listing via Rectangular Fast Matrix Multiplication
Carlo Comin, Romeo Rizzi
The first output-sensitive algorithm for the Maximal Clique Listing problem was given by Tsukiyama et.al. in 1977. As any algorithm falling within the Reverse Search paradigm, it p…
Dynamic Consistency of Conditional Simple Temporal Networks via Mean Payoff Games: a Singly-Exponential Time DC-Checking
Carlo Comin, Romeo Rizzi
Conditional Simple Temporal Network (CSTN) is a constraint-based graph-formalism for conditional temporal planning. It offers a more flexible formalism than the equivalent CSTP mod…
An Improved Pseudo-Polynomial Upper Bound for the Value Problem and Optimal Strategy Synthesis in Mean Payoff Games
Carlo Comin, Romeo Rizzi
In this work we offer an pseudo-polynomial time deterministic algorithm for solving the Value Problem and Optimal Strategy Synthesis in Mean Payoff Games. This i…
Hyper Temporal Networks
Carlo Comin, Roberto Posenato, Romeo Rizzi
Simple Temporal Networks (STNs) provide a powerful and general tool for representing conjunctions of maximum delay constraints over ordered pairs of temporal variables. In this pap…
(Extended Version) Algebraic Characterization of the Class of Languages recognized by Measure Only Quantum Automata
Carlo Comin
We study a model of one-way quantum automaton where only measurement operations are allowed ($\mon$). We give an algebraic characterization of $\lmo(Σ)$, showing that the syntactic…
Algebraic Characterization of the Class of Languages recognized by Measure Only Quantum Automata
Carlo Comin, Maria Paola Bianchi
We study a model of one-way quantum automaton where only measurement operations are allowed (MOn-1qfa). We give an algebraic characterization of LMO, showing that the syntactic mon…