Common Connected Components of Interval Graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2003

Common Connected Components of Interval Graphs

Michel Habib
Christophe Paul
Mathieu Raffinot
  • Fonction : Auteur
  • PersonId : 844841

Résumé

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
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Identifiants

  • HAL Id : lirmm-00269438 , version 1

Citer

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

Partager

Gmail Facebook X LinkedIn More