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.
Type de document :
Rapport
[Research Report] 03014, LIRMM (UM, CNRS). 2003, pp.13
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00269438
Contributeur : Christine Carvalho de Matos <>
Soumis le : jeudi 3 avril 2008 - 08:11:56
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : vendredi 21 mai 2010 - 01:12:38

Fichier

D101.PDF
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-00269438, version 1

Collections

Citation

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

Partager

Métriques

Consultations de la notice

132

Téléchargements de fichiers

118