A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs
From MaRDI portal
Publication:5941505
DOI10.1016/S0304-3975(00)00234-6zbMath0972.05046WikidataQ127220169 ScholiaQ127220169MaRDI QIDQ5941505
No author found.
Publication date: 20 August 2001
Published in: Theoretical Computer Science (Search for Journal in Brave)
Related Items (23)
On computing the Galois lattice of bipartite distance hereditary graphs ⋮ Injective hulls of various graph classes ⋮ 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 ⋮ The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes ⋮ From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats ⋮ On Strong Tree-Breadth ⋮ Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs ⋮ Make a graph singly connected by edge orientations ⋮ Simple linear-time algorithms for counting independent sets in distance-hereditary graphs ⋮ Dynamic Distance Hereditary Graphs Using Split Decomposition ⋮ Finding a minimum path cover of a distance-hereditary graph in polynomial time ⋮ A parity domination problem in graphs with bounded treewidth and distance-hereditary graphs ⋮ Equistable distance-hereditary graphs ⋮ A simple linear time algorithm for cograph recognition ⋮ Labelled packing functions in graphs ⋮ Unnamed Item ⋮ Laminar structure of ptolemaic graphs with applications ⋮ Linear-time algorithm for the matched-domination problem in cographs ⋮ Distance-Hereditary Comparability Graphs ⋮ Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs ⋮ Eccentricity function in distance-hereditary graphs ⋮ Computing maximum stable sets for distance-hereditary graphs
Cites Work
- Completely separable graphs
- Distance-hereditary graphs
- Efficient parallel recognition algorithms of cographs and distance hereditary graphs
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- A Linear Recognition Algorithm for Cographs
- Algorithmic Aspects of Vertex Elimination on Graphs
- Unnamed Item
This page was built for publication: A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs
