Probe split graphs

Abstract : An undirected graph G=(V,E) is a probe split graph if its vertex set can be partitioned into two sets, N (non-probes) and P (probes) where N is independent and there exists E' ⊆ N× N such that G'=(V,E∪ E') is a split graph. Recently Chang et al. gave an O(V4(V+E)) time recognition algorithm for probe split graphs. In this article we give O(V2+VE) time recognition algorithms and characterisations by forbidden induced subgraphs both for the case when the partition into probes and non-probes is given, and when it is not given.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2007, 9 (1), pp.207--238
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00966503
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mercredi 26 mars 2014 - 16:59:19
Dernière modification le : mercredi 29 novembre 2017 - 10:26:25
Document(s) archivé(s) le : jeudi 26 juin 2014 - 11:55:14

Fichier

713-2533-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00966503, version 1

Collections

Citation

Van Bang Le, H. N. Ridder. Probe split graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2007, 9 (1), pp.207--238. 〈hal-00966503〉

Partager

Métriques

Consultations de la notice

49

Téléchargements de fichiers

169