33 citations · 116 across the 28 of their papers we have counts for
33 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…
On the power of standard DFS and BFS
Binh-Minh Bui-Xuan, Michel Habib, Fabien de Montgolfier +1
It is well-known since the seventies of last century that Depth First Search (DFS) can be used to compute strongly connected components [RE. Tarjan. SIAM Journal on Computing, 1972…
Pattern detection in ordered graphs
Guillaume Ducoffe, Laurent Feuilloley, Michel Habib +1
A popular way to define or characterize graph classes is via forbidden subgraphs or forbidden minors. These characterizations play a key role in graph theory, but they rarely lead…
Forbidden Patterns in Temporal Graphs Resulting from Encounters in a Corridor
Mónika Csikós, Michel Habib, Minh-Hang Nguyen +2
In this paper, we study temporal graphs arising from mobility models, where vertices correspond to agents moving in space and edges appear each time two agents meet. We propose a r…
Classifying grounded intersection graphs via ordered forbidden patterns
Laurent Feuilloley, Michel Habib
It was noted already in the 90s that many classic graph classes, such as interval, chordal, and bipartite graphs, can be characterized by the existence of an ordering of the vertic…
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…