Fully Dynamic Algorithm for Modular Decomposition and Recognition of Permutation Graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles Algorithmica Year : 2010

Fully Dynamic Algorithm for Modular Decomposition and Recognition of Permutation Graphs

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.

Dates and versions

lirmm-00533516 , version 1 (07-11-2010)

Identifiers

Cite

Christophe Crespelle, Christophe Paul. Fully Dynamic Algorithm for Modular Decomposition and Recognition of Permutation Graphs. Algorithmica, 2010, 58 (2), pp.405-432. ⟨10.1007/s00453-008-9273-0⟩. ⟨lirmm-00533516⟩
199 View
0 Download

Altmetric

Share

More