Fully Dynamic Algorithm for Modular Decomposition and Recognition of Permutation Graphs

1 Christophe Paul 2
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : This paper considers the problem of maintaining a compact representation (O(n) space) of permutation graphs under vertex and edge modifications (insertion or deletion). That representation allows us to answer adjacency queries in O(1) time. The approach is based on a fully dynamic modular decomposition algorithm for permutation graphs that works in O(n) time per edge and vertex modification. We thereby obtain a fully dynamic algorithm for the recognition of permutation graphs.
Type de document :
Communication dans un congrès
WG'05: 31st International Workshop on Graph Theoretical Concepts in Computer Science, Jun 2005, Metz, France. LNCS (3787), pp.38-48, 2005, 〈10.1007/11604686_4〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00106039
Contributeur : Christine Carvalho de Matos <>
Soumis le : vendredi 13 octobre 2006 - 10:22:59
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Lien texte intégral

Identifiants

Collections

Citation

, Christophe Paul. Fully Dynamic Algorithm for Modular Decomposition and Recognition of Permutation Graphs. WG'05: 31st International Workshop on Graph Theoretical Concepts in Computer Science, Jun 2005, Metz, France. LNCS (3787), pp.38-48, 2005, 〈10.1007/11604686_4〉. 〈lirmm-00106039〉

Partager

Métriques

Consultations de la notice

128