Practical and Efficient Split Decomposition via Graph-Labelled Trees - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Algorithmica Year : 2014

Practical and Efficient Split Decomposition via Graph-Labelled Trees

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

Dates and versions

lirmm-00805193 , version 1 (27-03-2013)

Identifiers

Cite

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

Altmetric

Share

Gmail Facebook X LinkedIn More