Fully dynamic recognition algorithm and certificate for directed cographs
From MaRDI portal
Publication:2499593
DOI10.1016/J.DAM.2006.03.005zbMATH Open1110.68096OpenAlexW2095917812MaRDI QIDQ2499593FDOQ2499593
Authors: Christophe Crespelle, Christophe Paul 
Publication date: 14 August 2006
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2006.03.005
Recommendations
- Graph-Theoretic Concepts in Computer Science
- A fully dynamic algorithm for modular decomposition and recognition of cographs.
- A fully dynamic algorithm for recognizing and representing chordal graphs
- Graph-Theoretic Concepts in Computer Science
- Fully dynamic algorithm for recognition and modular decomposition of permutation graphs
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Complement reducible graphs
- The Recognition of Series Parallel Digraphs
- A Linear Recognition Algorithm for Cographs
- Incremental modular decomposition
- A simple linear time LexBFS cograph recognition algorithm.
- Title not available (Why is that?)
- A Fully dynamic algorithm for recognizing and representing proper interval graphs
- Primitivity is hereditary for 2-structures
- A fully dynamic algorithm for modular decomposition and recognition of cographs.
- Title not available (Why is that?)
- Bipartite graphs totally decomposable by canonical decomposition
- LINEAR TIME RECOGNITION AND OPTIMIZATIONS FOR WEAK-BISPLIT GRAPHS, BI-COGRAPHS AND BIPARTITE P6-FREE GRAPHS
- Graph-Theoretic Concepts in Computer Science
- Graph-Theoretic Concepts in Computer Science
Cited In (38)
- Directed NLC-width
- A System of Interaction and Structure III: The Complexity of BV and Pomset Logic
- Acyclic coloring parameterized by directed clique-width
- Arc-disjoint paths in decomposable digraphs
- Fully dynamic algorithm for recognition and modular decomposition of permutation graphs
- Fully dynamic recognition of proper circular-arc graphs
- Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
- Twin-distance-hereditary digraphs
- Efficient computation of the oriented chromatic number of recursively defined digraphs
- Computing directed Steiner path covers
- Reconstructing gene trees from Fitch's xenology relation
- Fitch graph completion
- Computing directed Steiner path covers for directed co-graphs (extended abstract)
- Oriented coloring on recursively defined digraphs
- On characterizations for subclasses of directed co-graphs
- The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations
- The knapsack problem with special neighbor constraints on directed co-graphs
- 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
- Comparing linear width parameters for directed graphs
- Solutions for subset sum problems with special digraph constraints
- Best match graphs
- Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments
- A survey of the algorithmic aspects of modular decomposition
- Reciprocal best match graphs
- Exact-2-relation graphs
- Graph-Theoretic Concepts in Computer Science
- The knapsack problem with special neighbor constraints
- Certifying algorithms
- How to compute digraph width measures on directed co-graphs
- From modular decomposition trees to rooted median graphs
- Generalized Fitch graphs. II: Sets of binary relations that are explained by edge-labeled trees
- Generalized Fitch graphs: edge-labeled graphs that are explained by edge-labeled trees
- Miscellaneous digraph classes
- A semi-strong perfect digraph theorem
- Fully dynamic representations of interval graphs
- Linear-time minimal cograph editing
This page was built for publication: Fully dynamic recognition algorithm and certificate for directed cographs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2499593)
