Skip to Main content Skip to Navigation
Journal articles

Practical and Efficient Split Decomposition via Graph-Labelled Trees

Emeric Gioan 1 Christophe Paul 1 Marc Tedder 2 Derek Corneil 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Split decomposition of graphs was introduced by Cunningham (under the name join decomposition) as a generalization of the modular decomposition. This paper undertakes an investigation into the algorithmic properties of split decompo- sition. We do so in the context of graph-labelled trees (GLTs), a new combinatorial object designed to simplify its consideration. GLTs are used to derive an incremental characterization of split decomposition, with a simple combinatorial description, and to explore its properties with respect to Lexicographic Breadth-First Search (LBFS). Applying the incremental characterization to an LBFS ordering results in a split de- composition algorithm that runs in time O(n + m)α(n + m), where α is the inverse Ackermann function, whose value is smaller than 4 for any practical graph. Com- pared to Dahlhaus' linear time split decomposition algorithm (Dahlhaus in J. Algo- rithms 36(2):205-240, 2000), which does not rely on an incremental construction, our algorithm is just as fast in all but the asymptotic sense and full implementation
Document type :
Journal articles
Complete list of metadata
Contributor : Christophe Paul <>
Submitted on : Wednesday, March 27, 2013 - 12:54:43 PM
Last modification on : Monday, November 30, 2020 - 5:32:03 PM

Links full text




Emeric Gioan, Christophe Paul, Marc Tedder, Derek Corneil. Practical and Efficient Split Decomposition via Graph-Labelled Trees. Algorithmica, Springer Verlag, 2014, 69 (4), pp.789-843. ⟨10.1007/s00453-013-9752-9⟩. ⟨lirmm-00805193⟩



Record views