Fully dynamic recognition algorithm and certificate for directed cographs

DOI10.1016/j.dam.2006.03.005zbMath1110.68096OpenAlexW2095917812MaRDI QIDQ2499593

Christophe Paul, Christophe Crespelle

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

zbMATH Keywords

dynamic algorithmscertifying algorithmsdirected cographs

Mathematics Subject Classification ID

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

Related Items (35)

The knapsack problem with special neighbor constraints ⋮ Computing directed Steiner path covers ⋮ Acyclic coloring parameterized by directed clique-width ⋮ Linear-time minimal cograph editing ⋮ Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments ⋮ Arc-Disjoint Paths in Decomposable Digraphs ⋮ Best match graphs ⋮ Generalized Fitch graphs. II: Sets of binary relations that are explained by edge-labeled trees ⋮ Twin-distance-hereditary digraphs ⋮ Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs ⋮ A System of Interaction and Structure III: The Complexity of BV and Pomset Logic ⋮ Exact-2-relation graphs ⋮ Directed NLC-width ⋮ A fully dynamic algorithm for the recognition of \(P_4\)-sparse graphs ⋮ Fully dynamic representations of interval graphs ⋮ Solutions for subset sum problems with special digraph constraints ⋮ A survey of the algorithmic aspects of modular decomposition ⋮ Certifying algorithms ⋮ How to compute digraph width measures on directed co-graphs ⋮ Computing Directed Steiner Path Covers for Directed Co-graphs (Extended Abstract) ⋮ A certifying and dynamic algorithm for the recognition of proper circular-arc graphs ⋮ Efficient computation of the oriented chromatic number of recursively defined digraphs ⋮ Oriented coloring on recursively defined digraphs ⋮ The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations ⋮ On characterizations for subclasses of directed co-graphs ⋮ Faster and enhanced inclusion-minimal cograph completion ⋮ Reconstructing gene trees from Fitch's xenology relation ⋮ Fully dynamic algorithm for recognition and modular decomposition of permutation graphs ⋮ A semi-strong perfect digraph theorem ⋮ Reciprocal best match graphs ⋮ From modular decomposition trees to rooted median graphs ⋮ Comparing linear width parameters for directed graphs ⋮ Generalized Fitch graphs: edge-labeled graphs that are explained by edge-labeled trees ⋮ Miscellaneous Digraph Classes ⋮ Fully dynamic recognition of proper circular-arc graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Primitivity is hereditary for 2-structures
• Complement reducible graphs
• A fully dynamic algorithm for modular decomposition and recognition of cographs.
• A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs
• A Linear Recognition Algorithm for Cographs
• Incremental modular decomposition
• The Recognition of Series Parallel Digraphs
• BIPARTITE GRAPHS TOTALLY DECOMPOSABLE BY CANONICAL DECOMPOSITION
• LINEAR TIME RECOGNITION AND OPTIMIZATIONS FOR WEAK-BISPLIT GRAPHS, BI-COGRAPHS AND BIPARTITE P₆-FREE GRAPHS
• Graph-Theoretic Concepts in Computer Science
• Graph-Theoretic Concepts in Computer Science
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Fully dynamic recognition algorithm and certificate for directed cographs