4 papers
Simpler, Linear-Time Transitive Orientation via Lexicographic Breadth-First Search
Marc Tedder
Comparability graphs are the undirected graphs whose edges can be directed so that the resulting directed graph is transitive. They are related to posets and have applications in s…
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 recursive linear time modular decomposition algorithm via LexBFS
Derek Corneil, Michel Habib, Christophe Paul +1
A module of a graph G is a set of vertices that have the same set of neighbours outside. Modules of a graphs form a so-called partitive family and thereby can be represented by a u…