Fully Dynamic Algorithm for Modular Decomposition and Recognition of Permutation Graphs

Christophe Crespelle 1, 2, 3 Christophe Paul 4
1 DNET - Dynamic Networks
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
4 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 :
Article dans une revue
Algorithmica, Springer Verlag, 2010, 58 (2), pp.405-432
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00533516
Contributeur : Christophe Paul <>
Soumis le : dimanche 7 novembre 2010 - 07:51:53
Dernière modification le : jeudi 12 juillet 2018 - 01:04:47

Identifiants

  • HAL Id : lirmm-00533516, version 1

Citation

Christophe Crespelle, Christophe Paul. Fully Dynamic Algorithm for Modular Decomposition and Recognition of Permutation Graphs. Algorithmica, Springer Verlag, 2010, 58 (2), pp.405-432. 〈lirmm-00533516〉

Partager

Métriques

Consultations de la notice

260