Skip to Main content Skip to Navigation

Common Connected Components of Interval Graphs

Michel Habib 1 Christophe Paul 1 Mathieu Raffinot 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : The Common Connected Problem (CCP) consists in identifying common connected components in two or more graphs on the same vertices (or reduced to). More formally, let G1(V,E1) and G2(V,E2) be two such graphs and let V′ ⊂ V. If G1[V′] and G2[V′] are both connected, V ′ is said a common connected component. The CCP problem is the identification of maximal (for the inclusion order) such components, that form a partition of V. Let n = |V| and m = |E1|+|E2|. We present an O((n+m)logn) worst case time algorithm solving the CCP problem when G1 and G2 are two interval graphs. The algorithm combines maximal clique path decompositions of the two input graphs together with an Hopcroft like partitioning approach.
Document type :
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download
Contributor : Christine Carvalho de Matos Connect in order to contact the contributor
Submitted on : Thursday, April 3, 2008 - 8:11:56 AM
Last modification on : Friday, October 22, 2021 - 3:07:27 PM
Long-term archiving on: : Friday, May 21, 2010 - 1:12:38 AM


Files produced by the author(s)


  • HAL Id : lirmm-00269438, version 1



Michel Habib, Christophe Paul, Mathieu Raffinot. Common Connected Components of Interval Graphs. [Research Report] 03014, LIRMM (UM, CNRS). 2003, pp.13. ⟨lirmm-00269438⟩



Record views


Files downloads