Linear Time Split Decomposition Revisited

Pierre Charbit (1, 2) , Fabien de Montgolfier (1, 2) , Mathieu Raffinot (1)

1 LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications
2 GANG - Networks, Graphs and Algorithms

Given a family $\mathcal{F}$ of subsets of a ground set V, its orthogonal is defined to be the family of subsets that do not overlap any element of $\mathcal{F}$. Using this tool we revisit the problem of designing a simple linear time algorithm for undirected graph split (also known as 1-join) decomposition.

Mots clés: graph theory; graph algorithms; graph decomposition; split decomposition; 1-join decomposition

Domaines: Algorithme et structure de données [cs.DS]

Pierre Charbit, Fabien de Montgolfier, Mathieu Raffinot. Linear Time Split Decomposition Revisited. SIAM Journal on Discrete Mathematics, 2012, 26 (2), pp.499-514. ⟨10.1137/10080052X⟩. ⟨hal-00921774⟩