24 citations · 27 across the 5 of their papers we have counts for
5 papers
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…
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…
Maximal cliques structure for cocomparability graphs and applications
Jérémie Dusart, Michel Habib, Derek G. Corneil
A cocomparability graph is a graph whose complement admits a transitive orientation. An interval graph is the intersection graph of a family of intervals on the real line. In this…
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…
Into the Square - On the Complexity of Quadratic-Time Solvable Problems
Michele Borassi, Pierluigi Crescenzi, Michel Habib
This paper will analyze several quadratic-time solvable problems, and will classify them into two classes: problems that are solvable in truly subquadratic time (that is, in time $…