Fully dynamic algorithm for recognition and modular decomposition of permutation graphs
DOI10.1007/S00453-008-9273-0zbMATH Open1205.68258OpenAlexW1996087362MaRDI QIDQ5961976FDOQ5961976
Authors: 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
Recommendations
- Graph-Theoretic Concepts in Computer Science
- A fully dynamic algorithm for modular decomposition and recognition of cographs.
- Reconstruction Algorithm for Permutation Graphs
- scientific article; zbMATH DE number 1741000
- scientific article; zbMATH DE number 1156661
- Fully dynamic algorithms for permutation graph coloring
- A fully dynamic algorithm for recognizing and representing chordal graphs
- An Algorithm for the Modular Decomposition of Hypergraphs
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Graph Classes: A Survey
- Modular decomposition and transitive orientation
- Efficient graph representations
- Transitiv orientierbare Graphen
- On-Line Planarity Testing
- A Linear Recognition Algorithm for Cographs
- Incremental modular decomposition
- An O(n2) Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs
- 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 modular decomposition and recognition of cographs.
- Fast algorithms to enumerate all common intervals of two permutations
- Title not available (Why is that?)
- A Fully Dynamic Algorithm for the Recognition of P 4-Sparse Graphs
- Algorithms – ESA 2005
- Algorithms and Computation
- Title not available (Why is that?)
- Separator-Based Sparsification II: Edge and Vertex Connectivity
- Graph-Theoretic Concepts in Computer Science
Cited In (17)
- Fully dynamic recognition algorithm and certificate for directed cographs
- A Fully Dynamic Algorithm for the Recognition of P 4-Sparse Graphs
- Fully dynamic recognition of proper circular-arc graphs
- Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
- An \(\mathcal {O}(n^2)\) time algorithm for the minimal permutation completion problem
- A fully dynamic algorithm for the recognition of \(P_4\)-sparse graphs
- A fully dynamic algorithm for modular decomposition and recognition of cographs.
- A certifying and dynamic algorithm for the recognition of proper circular-arc graphs
- Graph-Theoretic Concepts in Computer Science
- Permutation bigraphs and interval containments
- Complete edge-colored permutation graphs
- Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs
- Succinct permutation graphs
- Fully dynamic representations of interval graphs
- Graph-Theoretic Concepts in Computer Science
- Certifying fully dynamic algorithms for recognition and Hamiltonicity of threshold and chain graphs
- An \(O(n^2)\) time algorithm for the minimal permutation completion problem
This page was built for publication: Fully dynamic algorithm for recognition and modular decomposition of permutation graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5961976)
