Weighted efficient domination problem on some perfect graphs

DOI10.1016/S0166-218X(01)00184-6zbMath0994.05111OpenAlexW2152792800WikidataQ128090043 ScholiaQ128090043MaRDI QIDQ1348388

Chuan Yi Tang, Chin Lung Lu

Publication date: 15 May 2002

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

Full work available at URL: https://doi.org/10.1016/s0166-218x(01)00184-6

zbMATH Keywords

bipartite graphsefficient dominating set

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Perfect graphs (05C17)

Related Items (24)

A dichotomy for weighted efficient dominating sets with bounded degree vertices ⋮ Acyclic domination on bipartite permutation graphs ⋮ Efficient domination through eigenvalues ⋮ Kernelization of edge perfect code and its variants ⋮ Structure of squares and efficient domination in graph classes ⋮ A Taxonomy of Perfect Domination ⋮ Classification of efficient dominating sets of circulant graphs of degree 5 ⋮ Hereditary Efficiently Dominatable Graphs ⋮ Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems ⋮ Colouring a dominating set without conflicts: \(q\)-subset square colouring ⋮ Efficient minus and signed domination in graphs ⋮ k-Efficient domination: Algorithmic perspective ⋮ On weighted efficient total domination ⋮ Weighted efficient domination in two subclasses of \(P_6\)-free graphs ⋮ Perfect domination and small cycles ⋮ Simple linear-time algorithms for counting independent sets in distance-hereditary graphs ⋮ Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs ⋮ Efficient domination for classes of \(P_6\)-free graphs ⋮ Weighted efficient domination for some classes of \(H\)-free and of \((H_1, H_2)\)-free graphs ⋮ On efficient domination for some classes of \(H\)-free chordal graphs ⋮ On efficient domination for some classes of \(H\)-free bipartite graphs ⋮ On \([j, k\)-sets in graphs] ⋮ Fast and simple algorithms for counting dominating sets in distance-hereditary graphs ⋮ Exact algorithms for dominating induced matching based on graph partition

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Distance regular subgraphs of a cube
• Bibliography on domination in graphs and some basic definitions of domination parameters
• Completely separable graphs
• The weighted perfect domination problem
• Distance-hereditary graphs
• Bipartite permutation graphs
• Polynomial algorithms for the weighted perfect domination problems on chordal graphs and split graphs
• A linear time algorithm to solve the weighted perfect domination problem in series-parallel graphs
• Weighted domination of cocomparability graphs
• Perfect codes in the graphs \(O_k\)
• Weighted independent perfect domination on cocomparability graphs
• The weighted perfect domination problem and its variants
• Perfect codes in graphs
• Planar 3DM is NP-complete
• Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• Graph Classes: A Survey
• Dominating sets in n‐cubes
• A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs
• Dominating cliques in distance-hereditary graphs

This page was built for publication: Weighted efficient domination problem on some perfect graphs