Back to Search
Start Over
Fully Dynamic Algorithm for Modular Decomposition and Recognition of Permutation Graphs
- Source :
- Algorithmica, Algorithmica, Springer Verlag, 2010, 58 (2), pp.405-432, Algorithmica, 2010, 58 (2), pp.405-432. ⟨10.1007/s00453-008-9273-0⟩, WG'05: 31st International Workshop on Graph Theoretical Concepts in Computer Science, WG'05: 31st International Workshop on Graph Theoretical Concepts in Computer Science, Jun 2005, Metz, France. pp.38-48, ⟨10.1007/11604686_4⟩
- Publication Year :
- 2010
- Publisher :
- HAL CCSD, 2010.
-
Abstract
- International audience; 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.
Details
- Language :
- English
- ISSN :
- 01784617 and 14320541
- Database :
- OpenAIRE
- Journal :
- Algorithmica, Algorithmica, Springer Verlag, 2010, 58 (2), pp.405-432, Algorithmica, 2010, 58 (2), pp.405-432. ⟨10.1007/s00453-008-9273-0⟩, WG'05: 31st International Workshop on Graph Theoretical Concepts in Computer Science, WG'05: 31st International Workshop on Graph Theoretical Concepts in Computer Science, Jun 2005, Metz, France. pp.38-48, ⟨10.1007/11604686_4⟩
- Accession number :
- edsair.dedup.wf.001..d863ad7bf8dd017956da0891eef35e9e
- Full Text :
- https://doi.org/10.1007/s00453-008-9273-0⟩