37 citations · 65 across the 16 of their papers we have counts for
21 papers
An FTP Algorithm for Temporal Graph Untangling
Riccardo Dondi, Manuel Lafond
Several classical combinatorial problems have been considered and analysed on temporal graphs. Recently, a variant of Vertex Cover on temporal graphs, called MinTimelineCover, has…
Finding Colorful Paths in Temporal Graphs
Riccardo Dondi, Mohammad Mehdi Hosseinzadeh
The problem of finding paths in temporal graphs has been recently considered due to its many applications. In this paper we consider a variant of the problem that, given a vertex-c…
The Longest Run Subsequence Problem: Further Complexity Results
Riccardo Dondi, Florian Sikora
Longest Run Subsequence is a problem introduced recently in the context of the scaffolding phase of genome assembly (Schrinner et al., WABI 2020). The problem asks for a maximum le…
Top-k Connected Overlapping Densest Subgraphs in Dual Networks
Riccardo Dondi, Pietro Hiram Guzzi, Mohammad Mehdi Hosseinzadeh
Networks are largely used for modelling and analysing data and relations among them. Recently, it has been shown that the use of a single network may not be the optimal choice, sin…
Computing the k Densest Subgraphs of a Graph
Riccardo Dondi, Danny Hermelin
Computing cohesive subgraphs is a central problem in graph theory. While many formulations of cohesive subgraphs lead to NP-hard problems, finding a densest subgraph can be done in…
Complexity Issues of String to Graph Approximate Matching
Riccardo Dondi, Giancarlo Mauri, Italo Zoppis
The problem of matching a query string to a directed graph, whose vertices are labeled by strings, has application in different fields, from data mining to computational biology. S…
Top-k Overlapping Densest Subgraphs: Approximation and Complexity
Riccardo Dondi, Mohammad Mehdi Hosseinzadeh, Giancarlo Mauri +1
A central problem in graph mining is finding dense subgraphs, with several applications in different fields, a notable example being identifying communities. While a lot of effort…
Reconciling Multiple Genes Trees via Segmental Duplications and Losses
Riccardo Dondi, Manuel Lafond, Celine Scornavacca
Reconciling gene trees with a species tree is a fundamental problem to understand the evolution of gene families. Many existing approaches reconcile each gene tree independently. H…
Covering with Clubs: Complexity and Approximability
Riccardo Dondi, Giancarlo Mauri, Florian Sikora +1
Finding cohesive subgraphs in a network is a well-known problem in graph theory. Several alternative formulations of cohesive subgraph have been proposed, a notable example being $…
Finding Disjoint Paths on Edge-Colored Graphs: More Tractability Results
Riccardo Dondi, Florian Sikora
The problem of finding the maximum number of vertex-disjoint uni-color paths in an edge-colored graph (called MaxCDP) has been recently introduced in literature, motivated by appli…
Parameterized Complexity and Approximation Issues for the Colorful Components Problems
Riccardo Dondi, Florian Sikora
The quest for colorful components (connected components where each color is associated with at most one vertex) inside a vertex-colored graph has been widely considered in the last…
Parameterized Tractability of the Maximum-Duo Preservation String Mapping Problem
Stefano Beretta, Mauro Castelli, Riccardo Dondi
In this paper we investigate the parameterized complexity of the Maximum-Duo Preservation String Mapping Problem, the complementary of the Minimum Common String Partition Problem.…
Covering Pairs in Directed Acyclic Graphs
Niko Beerenwinkel, Stefano Beretta, Paola Bonizzoni +2
The Minimum Path Cover problem on directed acyclic graphs (DAGs) is a classical problem that provides a clear and simple mathematical formulation for several applications in differ…
On the Complexity of Minimum Labeling Alignment of Two Genomes
Riccardo Dondi, Nadia El-Mabrouk
In this note we investigate the complexity of the Minimum Label Alignment problem and we show that such a problem is APX-hard.
The Binary Perfect Phylogeny with Persistent characters
Paola Bonizzoni, Chiara Braghin, Riccardo Dondi +1
The binary perfect phylogeny model is too restrictive to model biological events such as back mutations. In this paper we consider a natural generalization of the model that allows…
Pure Parsimony Xor Haplotyping
Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi +2
The haplotype resolution from xor-genotype data has been recently formulated as a new model for genetic studies. The xor-genotype data is a cheaply obtainable type of data distingu…
Variants of Constrained Longest Common Subsequence
Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi +1
In this work, we consider a variant of the classical Longest Common Subsequence problem called Doubly-Constrained Longest Common Subsequence (DC-LCS). Given two strings s1 and s2 o…
Parameterized Complexity of the k-anonymity Problem
Stefano Beretta, Paola Bonizzoni, Gianluca Della Vedova +2
The problem of publishing personal data without giving up privacy is becoming increasingly important. An interesting formalization that has been recently proposed is the -anonym…
A PTAS for the Minimum Consensus Clustering Problem with a Fixed Number of Clusters
Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi
The Consensus Clustering problem has been introduced as an effective way to analyze the results of different microarray experiments. The problem consists of looking for a partition…
The -anonymity Problem is Hard
Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi
The problem of publishing personal data without giving up privacy is becoming increasingly important. An interesting formalization recently proposed is the k-anonymity. This approa…
Approximating Clustering of Fingerprint Vectors with Missing Values
Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi
The problem of clustering fingerprint vectors is an interesting problem in Computational Biology that has been proposed in (Figureroa et al. 2004). In this paper we show some impro…