National Institute for Research and Development in Informatics

output

19962025

most citedExploring the reproducibility of functional connectivity alterations in Parkinson's Disease

98 citations

researchers with a paper here

Counting papers with at most 25 authors, so collaboration author lists do not stand in for the people here.

collaborating institutions

Showing cs.DSShow all

13 papers · 1 filter

cs.DS2024

Practical Computation of Graph VC-Dimension

David Coudert, Mónika Csikós, Guillaume Ducoffe +1

For any set system $H = (V, R), R \subseteq 2^{V}$ , a subset $S \subseteq V$ is called \emph{shattered} if every $S^{'} \subseteq S$ results from the intersection of $S$ with some set in…

cs.DS2023

$α_{i}$ -Metric Graphs: Radius, Diameter and all Eccentricities

Feodor F. Dragan, Guillaume Ducoffe

We extend known results on chordal graphs and distance-hereditary graphs to much larger graph classes by using only a common metric property of these graphs. Specifically, a graph…

cs.DS2021

Subquadratic-time algorithm for the diameter and all eccentricities on median graphs

Pierre Bergé, Guillaume Ducoffe, Michel Habib

On sparse graphs, Roditty and Williams [2013] proved that no $O (n^{2 - ε})$ -time algorithm achieves an approximation factor smaller than $\frac{3}{2}$ for the diameter prob…

cs.DS2020★ 2 cited

Around the diameter of AT-free graphs

Guillaume Ducoffe

A graph algorithm is truly subquadratic if it runs in $O (m^{b})$ time on connected $m$ -edge graphs, for some positive $b < 2$ . Roditty and Vassilevska Williams (STOC'13) prove…

cs.DS2020★ 4 cited

Isometric embeddings in trees and their use in the diameter problem

Guillaume Ducoffe

We prove that given a discrete space with $n$ points which is either embedded in a system of $k$ trees, or the Cartesian product of $k$ trees, we can compute all eccentricities in…

cs.DS2019★ 8 cited

Diameter computation on $H$ -minor free graphs and graphs of bounded (distance) VC-dimension

Guillaume Ducoffe, Michel Habib, Laurent Viennot

We propose to study unweighted graphs of constant distance VC-dimension as a broad generalization of many graph classes for which we can compute the diameter in truly subquadratic-…

cs.DS2018★ 4 cited

Faster approximation algorithms for computing shortest cycles on weighted graphs

Guillaume Ducoffe

Given an $n$ -vertex $m$ -edge graph $G$ with non negative edge-weights, the girth of $G$ is the weight of a shortest cycle in $G$ . For any graph $G$ with polynomially bounded intege…

cs.DS2018★ 1 cited

An output-sensitive algorithm for the minimization of 2-dimensional String Covers

Alexandru Popa, Andrei Tanasescu

String covers are a powerful tool for analyzing the quasi-periodicity of 1-dimensional data and find applications in automata theory, computational biology, coding and the analysis…

cs.DS2018

The use of a pruned modular decomposition for Maximum Matching algorithms on some graph classes

Guillaume Ducoffe, Alexandru Popa

We address the following general question: given a graph class C on which we can solve Maximum Matching in (quasi) linear time, does the same hold true for the class of graphs that…

cs.DS2018

A quasi linear-time b-Matching algorithm on distance-hereditary graphs and bounded split-width graphs

Guillaume Ducoffe, Alexandru Popa

We present a quasi linear-time algorithm for Maximum Matching on distance-hereditary graphs and some of their generalizations. This improves on [Dragan, WG'97], who proposed such a…

cs.DS2018★ 8 cited

Fast approximation and exact computation of negative curvature parameters of graphs

Jérémie Chalopin, Victor Chepoi, Feodor F. Dragan +3

In this paper, we study Gromov hyperbolicity and related parameters, that represent how close (locally) a metric space is to a tree from a metric point of view. The study of Gromov…

cs.DS2018★ 4 cited

Heuristic algorithms for the min-max edge 2-coloring problem

Radu Stefan Mincu, Alexandru Popa

In multi-channel Wireless Mesh Networks (WMN), each node is able to use multiple non-overlapping frequency channels. Raniwala et al. (MC2R 2004, INFOCOM 2005) propose and study sev…

cs.DS2017★ 1 cited

Fully polynomial FPT algorithms for some classes of bounded clique-width graphs

David Coudert, Guillaume Ducoffe, Alexandru Popa

Parameterized complexity theory has enabled a refined classification of the difficulty of NP-hard optimization problems on graphs with respect to key structural properties, and so…

Practical Computation of Graph VC-Dimension

αi​-Metric Graphs: Radius, Diameter and all Eccentricities

Subquadratic-time algorithm for the diameter and all eccentricities on median graphs

Around the diameter of AT-free graphs

Isometric embeddings in trees and their use in the diameter problem

Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension

Faster approximation algorithms for computing shortest cycles on weighted graphs

An output-sensitive algorithm for the minimization of 2-dimensional String Covers

The use of a pruned modular decomposition for Maximum Matching algorithms on some graph classes

A quasi linear-time b-Matching algorithm on distance-hereditary graphs and bounded split-width graphs

Fast approximation and exact computation of negative curvature parameters of graphs

Heuristic algorithms for the min-max edge 2-coloring problem

Fully polynomial FPT algorithms for some classes of bounded clique-width graphs

$α_{i}$ -Metric Graphs: Radius, Diameter and all Eccentricities

Diameter computation on $H$ -minor free graphs and graphs of bounded (distance) VC-dimension