95 citations · 97 across the 5 of their papers we have counts for
8 papers
Lower bounds on collective additive spanners
Derek G. Corneil, Feodor F. Dragan, Ekkehard Köhler +1
In this paper we present various lower bound results on collective tree spanners and on spanners of bounded treewidth. A graph is said to admit a system of collective addit…
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…
Practical and Efficient Circle Graph Recognition
Emeric Gioan, Christophe Paul, Marc Tedder +1
Circle graphs are the intersection graphs of chords in a circle. This paper presents the first sub-quadratic recognition algorithm for the class of circle graphs. Our algorithm is…
Practical and Efficient Split Decomposition via Graph-Labelled Trees
Emeric Gioan, Christophe Paul, Marc Tedder +1
Split decomposition of graphs was introduced by Cunningham (under the name join decomposition) as a generalization of the modular decomposition. This paper undertakes an investigat…
A Simple Polynomial Algorithm for the Longest Path Problem on Cocomparability Graphs
George B. Mertzios, Derek G. Corneil
Given a graph , the longest path problem asks to compute a simple path of with the largest number of vertices. This problem is the most natural optimization version of the w…