A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs

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)

zbMATH Keywords

cographs; distance hereditary graphs; recognition algorithms

Mathematics Subject Classification ID

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Unnamed Item, Dynamic Distance Hereditary Graphs Using Split Decomposition, Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs, Eccentricity function in distance-hereditary graphs, A parity domination problem in graphs with bounded treewidth and distance-hereditary graphs, Laminar structure of ptolemaic graphs with applications, 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, Simple linear-time algorithms for counting independent sets in distance-hereditary graphs, A simple linear time algorithm for cograph recognition, Labelled packing functions in graphs, Injective hulls of various graph classes, From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats, On computing the Galois lattice of bipartite distance hereditary graphs, Finding a minimum path cover of a distance-hereditary graph in polynomial time, Equistable distance-hereditary graphs, Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs, Computing maximum stable sets for distance-hereditary graphs, The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes, Distance-Hereditary Comparability Graphs, On Strong Tree-Breadth, Linear-time algorithm for the matched-domination problem in cographs

Cites Work

• Unnamed Item
• 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