Fully-Dynamic Recognition Algorithm and Certificate for Directed Cographs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2004

Fully-Dynamic Recognition Algorithm and Certificate for Directed Cographs

Résumé

This paper presents an optimal fully dynamic recognition algorithm for directed cographs. Given the modular decomposition tree of a directed cograph G, the algorithm supports arc and vertex modification (insertion or deletion) in O(d) time where d is the number of arcs involved in the operation. Moreover, if the modified graph remains a directed cograph, the modular decomposition tree is updated; otherwise, a certificate is returned within the same complexity.

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
D322.PDF (177.82 Ko) Télécharger le fichier
Loading...

Dates et versions

lirmm-00108770 , version 1 (23-10-2006)

Identifiants

  • HAL Id : lirmm-00108770 , version 1

Citer

Christophe Crespelle, Christophe Paul. Fully-Dynamic Recognition Algorithm and Certificate for Directed Cographs. WG 2004 - 30th International Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2004, Bad Honnef, Germany. pp.93-104. ⟨lirmm-00108770⟩
55 Consultations
220 Téléchargements

Partager

Gmail Facebook X LinkedIn More