1 citations · 1 across the 3 of their papers we have counts for
4 papers
On the maximum weight convex problem for some geometric graph-convexities
Fariza Aklouche, Pierre Bergé, Michel Habib
For a given geometric graph-convexity on a graph equipped with a weight function on the vertices with value in , the Max Weight Convex Set problem consists in deter…
Deciding twin-width at most 4 is NP-complete
Pierre Bergé, Édouard Bonnet, Hugues Déprés
We show that determining if an -vertex graph has twin-width at most 4 is NP-complete, and requires time unless the Exponential-Time Hypothesis fails. Along the…
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 -time algorithm achieves an approximation factor smaller than for the diameter prob…
Diameter, radius and all eccentricities in linear time for constant-dimension median graphs
Pierre Bergé, Michel Habib
Median graphs form the class of graphs which is the most studied in metric graph theory. Recently, Bénéteau et al. [2019] designed a linear-time algorithm computing both the -cl…