A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs
From MaRDI portal
Publication:5941505
DOI10.1016/S0304-3975(00)00234-6zbMATH Open0972.05046WikidataQ127220169 ScholiaQ127220169MaRDI QIDQ5941505FDOQ5941505
Authors: Guillaume Damiand, Michel Habib, Christophe Paul 
Publication date: 20 August 2001
Published in: Theoretical Computer Science (Search for Journal in Brave)
Recommendations
Cites Work
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- Distance-hereditary graphs
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- Efficient parallel recognition algorithms of cographs and distance hereditary graphs
- A Linear Recognition Algorithm for Cographs
- Title not available (Why is that?)
- Completely separable graphs
Cited In (28)
- Title not available (Why is that?)
- Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
- The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes
- Injective hulls of various graph classes
- Dynamic Distance Hereditary Graphs Using Split Decomposition
- Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
- A New Approach to Graph Recognition and Applications to Distance-Hereditary Graphs
- Labelled packing functions in graphs
- Distance-hereditary comparability graphs
- Fast FPT-approximation of branchwidth
- Recognizing cographs and threshold graphs through a classification of their edges
- Make a graph singly connected by edge orientations
- Complexity of \(k\)-tuple total and total \(\{k\}\)-dominations for some subclasses of bipartite graphs
- Total dominating sequences in trees, split graphs, and under modular decomposition
- Title not available (Why is that?)
- Finding a minimum path cover of a distance-hereditary graph in polynomial time
- Equistable distance-hereditary graphs
- Linear-time algorithm for the matched-domination problem in cographs
- From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats
- On Strong Tree-Breadth
- Eccentricity function in distance-hereditary graphs
- On computing the Galois lattice of bipartite distance hereditary graphs
- A simple linear time algorithm for cograph recognition
- Compact Distributed Interactive Proofs for the Recognition of Cographs and Distance-Hereditary Graphs
- A parity domination problem in graphs with bounded treewidth and distance-hereditary graphs
- Simple linear-time algorithms for counting independent sets in distance-hereditary graphs
- Laminar structure of ptolemaic graphs with applications
- Computing maximum stable sets for distance-hereditary graphs
This page was built for publication: A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5941505)
