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.
Document type :
Journal articles
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00533516
Contributor : Christophe Paul <>
Submitted on : Sunday, November 7, 2010 - 7:51:53 AM
Last modification on : Thursday, February 7, 2019 - 5:10:09 PM

Identifiers

  • 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⟩

Share

Metrics

Record views

301