20 citations · 29 across the 19 of their papers we have counts for
30 papers
Predicting Horizontal Gene Transfers with Perfect Transfer Networks
Alitzel López Sánchez, Manuel Lafond
Horizontal gene transfer inference approaches are usually based on gene sequences: parametric methods search for patterns that deviate from a particular genomic signature, while ph…
Parameterized Complexity of Domination Problems Using Restricted Modular Partitions
Manuel Lafond, Weidong Luo
For a graph class , we define the -modular cardinality of a graph as the minimum size of a vertex partition of into modules that each induces a gr…
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…
Preprocessing Complexity for Some Graph Problems Parameterized by Structural Parameters
Manuel Lafond, Weidong Luo
Structural graph parameters play an important role in parameterized complexity, including in kernelization. Notably, vertex cover, neighborhood diversity, twin-cover, and modular-w…
A lightweight semi-centralized strategy for the massive parallelization of branching algorithms
Andres Pastrana-Cruz, Manuel Lafond
Several NP-hard problems are solved exactly using exponential-time branching strategies, whether it be branch-and-bound algorithms, or bounded search trees in fixed-parameter algor…
Finding agreement cherry-reduced subnetworks in level-1 networks
Kaari Landry, Olivier Tremblay-Savard, Manuel Lafond
Phylogenetic networks are increasingly being considered as better suited to represent the complexity of the evolutionary relationships between species. One class of phylogenetic ne…
The Longest Subsequence-Repeated Subsequence Problem
Manuel Lafond, Wenfeng Lai, Adiesha Liyanage +1
Motivated by computing duplication patterns in sequences, a new fundamental problem called the longest subsequence-repeated subsequence (LSRS) is proposed. Given a sequence of…
The Two-Squirrel Problem and Its Relatives
Sergey Bereg, Yuya Higashikawa, Naoki Katoh +3
In this paper, we start with a variation of the star cover problem called the Two-Squirrel problem. Given a set of points in the plane, and two sites and , comp…
Relative Timing Information and Orthology in Evolutionary Scenarios
David Schaller, Tom Hartmann, Manuel Lafond +3
Evolutionary scenarios describing the evolution of a family of genes within a collection of species comprise the mapping of the vertices of a gene tree to vertices and edges of…
Recognizing k-leaf powers in polynomial time, for constant k
Manuel Lafond
A graph is a -leaf power if there exists a tree whose leaf set is , and such that if and only if the distance between and in is at most $…
Indirect Identification of Horizontal Gene Transfer
David Schaller, Manuel Lafond, Peter F. Stadler +2
Several implicit methods to infer Horizontal Gene Transfer (HGT) focus on pairs of genes that have diverged only after the divergence of the two species in which the genes reside.…
Further results on Hendry's Conjecture
Manuel Lafond, Ben Seamone, Rezvan Sherkati
Recently, a conjecture due to Hendry was disproved which stated that every Hamiltonian chordal graph is cycle extendible. Here we further explore the conjecture, showing that it fa…
Comparing copy-number profiles under multi-copy amplifications and deletions
Garance Cordonnier, Manuel Lafond
During cancer progression, malignant cells accumulate somatic mutations that can lead to genetic aberrations. In particular, evolutionary events akin to segmental duplications or d…
Genomic Problems Involving Copy Number Profiles: Complexity and Algorithms
Manuel Lafond, Binhai Zhu, Peng Zou
Recently, due to the genomic sequence analysis in several types of cancer, the genomic data based on {\em copy number profiles} ({\em CNP} for short) are getting more and more popu…
Reconstruction of time-consistent species trees
Manuel Lafond, Marc Hellmuth
The history of gene families -- which are equivalent to event-labeled gene trees -- can to some extent be reconstructed from empirically estimated evolutionary event-relations cont…
The Tandem Duplication Distance is NP-hard
Manuel Lafond, Binhai Zhu, Peng Zou
In computational biology, tandem duplication is an important biological phenomenon which can occur either at the genome or at the DNA level. A tandem duplication takes a copy of a…
Distributed Pattern Formation in a Ring
Anne-Laure Ehresmann, Manuel Lafond, Lata Narayanan +1
Motivated by concerns about diversity in social networks, we consider the following pattern formation problems in rings. Assume mobile agents are located at the nodes of an …
Time-Energy Tradeoffs for Evacuation by Two Robots in the Wireless Model
Jurek Czyzowicz, Konstantinos Georgiou, Ryan Killick +6
Two robots stand at the origin of the infinite line and are tasked with searching collaboratively for an exit at an unknown location on the line. They can travel at maximum speed $…
Energy Consumption of Group Search on a Line
Jurek Czyzowicz, Konstantinos Georgiou, Ryan Killick +6
Consider two robots that start at the origin of the infinite line in search of an exit at an unknown location on the line. The robots can only communicate if they arrive at the sam…
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…
The complexity of comparing multiply-labelled trees by extending phylogenetic-tree metrics
Manuel Lafond, Nadia El-Mabrouk, Katharina T. Huber +1
A multilabeled tree (or MUL-tree) is a rooted tree in which every leaf is labelled by an element from some set, but in which more than one leaf may be labelled by the same element…
Constructing a Consensus Phylogeny from a Leaf-Removal Distance
Cedric Chauve, Mark Jones, Manuel Lafond +2
Understanding the evolution of a set of genes or species is a fundamental problem in evolutionary biology. The problem we study here takes as input a set of trees describing {possi…
On strongly chordal graphs that are not leaf powers
Manuel Lafond
A common task in phylogenetics is to find an evolutionary tree representing proximity relationships between species. This motivates the notion of leaf powers: a graph G = (V, E) is…
Weak Coverage of a Rectangular Barrier
Stefan Dobrev, Evangelos Kranakis, Danny Krizanc +5
Assume n wireless mobile sensors are initially dispersed in an ad hoc manner in a rectangular region. They are required to move to final locations so that they can detect any intru…