Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00106039
Contributor : Christine Carvalho de Matos <>
Submitted on : Friday, October 13, 2006 - 10:22:59 AM
Last modification on : Thursday, May 24, 2018 - 3:59:22 PM

Links full text

Identifiers

Collections

Citation

Christophe Crespelle, 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. pp.38-48, ⟨10.1007/11604686_4⟩. ⟨lirmm-00106039⟩

Share

Metrics

Record views

317