5 papers
Minimum Eccentricity Shortest Path Problem: an Approximation Algorithm and Relation with the k-Laminarity Problem
Etienne Birmelé, Fabien De Montgolfier, Léo Planche
The Minimum Eccentricity Shortest Path (MESP) Problem consists in determining a shortest path (a path whose length is the distance between its extremities) of minimum eccentricity…
A tie-break model for graph search
Derek G. Corneil, Jeremie Dusart, Michel Habib +1
In this paper, we consider the problem of the recognition of various kinds of orderings produced by graph searches. To this aim, we introduce a new framework, the Tie-Breaking Labe…
Algorithmic Aspects of Switch Cographs
Vincent Cohen-Addad, Michel Habib, Fabien de Montgolfier
This paper introduces the notion of involution module, the first generalization of the modular decomposition of 2-structure which has a unique linear-sized decomposition tree. We d…
Easy identification of generalized common and conserved nested intervals
Fabien de Montgolfier, Mathieu Raffinot, Irena Rusu
In this paper we explain how to easily compute gene clusters, formalized by classical or generalized nested common or conserved intervals, between a set of K genomes represented as…
Linear Time Split Decomposition Revisited
Pierre Charbit, Fabien de Montgolfier, Mathieu Raffinot
Given a family F of subsets of a ground set V, its orthogonal is defined to be the family of subsets that do not overlap any element of F. Using this tool we revisit the problem of…