Fully dynamic algorithm for recognition and modular decomposition of permutation graphs

DOI10.1007/s00453-008-9273-0zbMath1205.68258OpenAlexW1996087362MaRDI QIDQ5961976

Christophe Crespelle, Christophe Paul

Publication date: 16 September 2010

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.188.4787

zbMATH Keywords

dynamic algorithmsmodular decompositionpermutation graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Related Items (12)

Complete edge-colored permutation graphs ⋮ Permutation bigraphs and interval containments ⋮ Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs ⋮ Succinct permutation graphs ⋮ Certifying fully dynamic algorithms for recognition and Hamiltonicity of threshold and chain graphs ⋮ A fully dynamic algorithm for the recognition of \(P_4\)-sparse graphs ⋮ Fully dynamic representations of interval graphs ⋮ An \(O(n^2)\) time algorithm for the minimal permutation completion problem ⋮ A certifying and dynamic algorithm for the recognition of proper circular-arc graphs ⋮ Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs ⋮ An $$\mathcal {O}(n^2)$$ Time Algorithm for the Minimal Permutation Completion Problem ⋮ Fully dynamic recognition of proper circular-arc graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Modular decomposition and transitive orientation
• Efficient graph representations
• A fully dynamic algorithm for modular decomposition and recognition of cographs.
• Fast algorithms to enumerate all common intervals of two permutations
• Fully dynamic recognition algorithm and certificate for directed cographs
• A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs
• A Fully Dynamic Algorithm for the Recognition of P 4-Sparse Graphs
• A Linear Recognition Algorithm for Cographs
• Incremental modular decomposition
• Separator-Based Sparsification II: Edge and Vertex Connectivity
• Graph Classes: A Survey
• An O(n2) Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs
• On-Line Planarity Testing
• Algorithms – ESA 2005
• Transitiv orientierbare Graphen
• Graph-Theoretic Concepts in Computer Science
• Algorithms and Computation

This page was built for publication: Fully dynamic algorithm for recognition and modular decomposition of permutation graphs