Distance-hereditary comparability graphs

DOI10.1016/j.dam.2012.02.021zbMath1254.05155OpenAlexW2074604981MaRDI QIDQ1759843

Gabriele Di Stefano

Publication date: 22 November 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2012.02.021

zbMATH Keywords

distance-hereditary graphsrecognition algorithmscomparability graphssplit decompositionbuilding algorithmsdistance-hereditary comparability graphs

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Characterization and recognition of some opposition and coalition graph classes ⋮ Mutual visibility in graphs ⋮ On polygon numbers of circle graphs and distance hereditary graphs ⋮ Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs ⋮ The structure and metric dimension of the power graph of a finite group

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Completely separable graphs
• Solving some NP-complete problems using split decomposition
• Non-cyclic train timetabling and comparability graphs
• Treelike comparability graphs
• Distance-hereditary graphs
• Graph classes between parity and distance-hereditary graphs
• Parallel concepts in graph theory
• Sources and sinks in comparability graphs
• Track assignment
• Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
• Distance-Hereditary Comparability Graphs
• Transforming trees by successive local complementations
• Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
• A Combinatorial Decomposition Theory
• Decomposition of Directed Graphs
• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• Graph Classes: A Survey
• A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs
• The rank and size of graphs
• Dynamic Distance Hereditary Graphs Using Split Decomposition
• Transitiv orientierbare Graphen
• Graph-Theoretic Concepts in Computer Science
• Weighted connected \(k\)-domination and weighted \(k\)-dominating clique in distance-hereditary graphs
• Compact-port routing models and applications to distance-hereditary graphs