6 citations · 13 across the 17 of their papers we have counts for
6 papers · 1 filter
Faster approximation algorithms for computing shortest cycles on weighted graphs
Guillaume Ducoffe
Given an -vertex -edge graph with non negative edge-weights, the girth of is the weight of a shortest cycle in . For any graph with polynomially bounded intege…
Polynomial-time Recognition of 4-Steiner Powers
Guillaume Ducoffe
The -power of a given graph is obtained from by adding an edge between every two distinct vertices at a distance at most in . We call a -Steiner…
Equivalence between pathbreadth and strong pathbreadth
Guillaume Ducoffe, Arne Leitert
We say that a given graph has \emph{pathbreadth} at most , denoted $\pb(G) \leq ρ$, if there exists a Roberston and Seymour's path decomposition where every bag is…
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…
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…
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…