Dominating cliques in distance-hereditary graphs

DOI10.1007/3-540-58218-5_34MaRDI QIDQ5054776zbMATH OpenOpenAlexFDO

Authors Feodor F. Dragan

Publication date 9 December 2022

Published in Algorithm Theory — SWAT '94 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-58218-5_34

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40)

Recommendations

• Weighted connected k-domination and weighted k-dominating clique in distance-hereditary graphs
• A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs
• Homogeneous sets and domination: A linear time algorithm for distance-hereditary graphs
• Fast and simple algorithms for counting dominating sets in distance-hereditary graphs
• Distance-hereditary graphs are clique-perfect

Cites work

• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• Centers of chordal graphs
• Completely separable graphs
• Distance-hereditary graphs
• Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
• Dominating cliques in chordal graphs
• Dually Chordal Graphs
• Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 23019 (Why is no real title available?)
• scientific article; zbMATH DE number 1414320 (Why is no real title available?)
• On domination problems for permutation and other graphs
• Powers of distance-hereditary graphs
• Pseudo-modular graphs
• Topics on domination

Cited in

(30)

• The path-partition problem in bipartite distance-hereditary graphs
• Weighted efficient domination problem on some perfect graphs
• \(r\)-dominating cliques in graphs with hypertree structure
• A note on \(r\)-dominating cliques
• Homogeneously orderable graphs
• Finding a central vertex in an HHD-free graph
• LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem
• Dualizing distance-hereditary graphs
• Equistable distance-hereditary graphs
• The Hamiltonian problem on distance-hereditary graphs
• Distance-hereditary graphs are clique-perfect
• Helly-gap of a graph and vertex eccentricities
• Homogeneous sets and domination: A linear time algorithm for distance-hereditary graphs
• Clique cycle-transversals in distance-hereditary graphs
• A note on connected dominating sets of distance-hereditary graphs
• Fast and simple algorithms for counting dominating sets in distance-hereditary graphs
• r-Domination problems on homogeneously orderable graphs
• Dominating cliques in graphs
• Graphs with bounded induced distance
• Weighted connected k-domination and weighted k-dominating clique in distance-hereditary graphs
• Diameter determination on restricted graph families
• Domination in distance-hereditary graphs
• LexBFS-orderings and powers of graphs
• _i-metric graphs: radius, diameter and all eccentricities
• Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
• The complexity of diameter on H-free graphs
• The complexity of diameter on \(H\)-free graphs
• Eccentricity function in distance-hereditary graphs
• Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
• Networks with small stretch number

This page was built for publication: Dominating cliques in distance-hereditary graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5054776)