Common Connected Components of Interval Graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Reports (Research Report) Year : 2003

Common Connected Components of Interval Graphs

Michel Habib
Christophe Paul
Mathieu Raffinot
  • Function : Author
  • PersonId : 844841


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.
Fichier principal
Vignette du fichier
D101.PDF (160.94 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-00269438 , version 1 (03-04-2008)


  • 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⟩
238 View
197 Download


Gmail Mastodon Facebook X LinkedIn More