33 citations · 116 across the 28 of their papers we have counts for
21 papers · 1 filter
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…
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…
Fast Diameter Computation within Split Graphs
Guillaume Ducoffe, Michel Habib, Laurent Viennot
When can we compute the diameter of a graph in quasi linear time? We address this question for the class of {\em split graphs}, that we observe to be the hardest instances for deci…
Graph classes and forbidden patterns on three vertices
Laurent Feuilloley, Michel Habib
This paper deals with graph classes characterization and recognition. A popular way to characterize a graph class is to list a minimal set of forbidden induced subgraphs. Unfortuna…
Fast approximation of centrality and distances in hyperbolic graphs
Victor Chepoi, Feodor F. Dragan, Michel Habib +2
We show that the eccentricities (and thus the centrality indices) of all vertices of a -hyperbolic graph can be computed in linear time with an additive one-sided erro…
Maximum Induced Matching Algorithms via Vertex Ordering Characterizations
Michel Habib, Lalla Mouatadid
We study the maximum induced matching problem on a graph g. Induced matchings correspond to independent sets in L2(g), the square of the line graph of g. The problem is NP-complete…
A New Graph Parameter To Measure Linearity
Pierre Charbit, Michel Habib, Lalla Mouatadid +1
Consider a sequence of LexBFS vertex orderings σ1, σ2, . . . where each ordering σi is used to break ties for σi+1. Since the total number of vertex orderings of a finite graph is…
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…
A general method for common intervals
Ismael Belghiti, Michel Habib
Given an elementary chain of vertex set V, seen as a labelling of V by the set {1, ...,n=|V|}, and another discrete structure over , say a graph G, the problem of common interva…
Detecting 2-joins faster
Pierre Charbit, Michel Habib, Nicolas Trotignon +1
2-joins are edge cutsets that naturally appear in the decomposition of several classes of graphs closed under taking induced subgraphs, such as balanced bipartite graphs, even-hole…
On a conjecture of compatibility of multi-states characters
Michel Habib, Thu-Hien To
Perfect phylogeny consisting of determining the compatibility of a set of characters is known to be NP-complete. We propose in this article a conjecture on the necessary and suffic…
Fast Computation of Empirically Tight Bounds for the Diameter of Massive Graphs
Clemence Magnien, Matthieu Latapy, Michel Habib
The diameter of a graph is among its most basic parameters. Since a few years, it moreover became a key issue to compute it for massive graphs in the context of complex network ana…
On some simplicial elimination schemes for chordal graphs
Michel Habib, Vincent Limouzy
We present here some results on particular elimination schemes for chordal graphs, namely we show that for any chordal graph we can construct in linear time a simplicial eliminatio…
A Note On Computing Set Overlap Classes
Pierre Charbit, Michel Habib, Vincent Limouzy +3
Let be a finite set of elements and a family of subsets of Two sets and of overlap if $X_i \…
Algorithmic Aspects of a General Modular Decomposition Theory
Binh-Minh Bui-Xuan, Michel Habib, Vincent Limouzy +1
A new general decomposition theory inspired from modular graph decomposition is presented. This helps unifying modular decomposition on different structures, including (but not res…
Unifying two Graph Decompositions with Modular Decomposition
Binh-Minh Bui-Xuan, Michel Habib, Vincent Limouzy +1
We introduces the umodules, a generalisation of the notion of graph module. The theory we develop captures among others undirected graphs, tournaments, digraphs, and structures…
Homogeneity vs. Adjacency: generalising some graph decomposition algorithms
Binh Minh Bui Xuan, Michel Habib, Vincent Limouzy +1
In this paper, a new general decomposition theory inspired from modular graph decomposition is presented. Our main result shows that, within this general theory, most of the nice a…