A four-sweep LBFS recognition algorithm for interval graphs

Abstract : In their 2009 paper, Corneil et al. design a linear time interval graph recognition algorithm based on six sweeps of Lexicographic Breadth-First Search (LBFS) and prove its correctness. They believe that their corresponding 5-sweep LBFS interval graph recognition algorithm is also correct. Thanks to the LBFS structure theory established mainly by Corneil et al., we are able to present a 4-sweep LBFS algorithm which determines whether or not the input graph is a unit interval graph or an interval graph. Like the algorithm of Corneil et al., our algorithm does not involve any complicated data structure and can be executed in linear time.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 3 (in progress) (3), pp.23--50
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01188908
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 31 août 2015 - 17:03:34
Dernière modification le : jeudi 7 septembre 2017 - 01:03:47
Document(s) archivé(s) le : mardi 1 décembre 2015 - 10:43:29

Fichier

dmtcs-16-3-2.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01188908, version 1

Collections

Citation

Peng Li, Yaokun Wu. A four-sweep LBFS recognition algorithm for interval graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 3 (in progress) (3), pp.23--50. 〈hal-01188908〉

Partager

Métriques

Consultations de la notice

57

Téléchargements de fichiers

234