Weighted independent perfect domination on cocomparability graphs

DOI10.1016/0166-218X(94)00067-3zbMath0848.05039MaRDI QIDQ1917231

Satyan Coorg, C. Pandu Rangan, Gerard Jennhwa Chang

Publication date: 5 August 1996

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

zbMATH Keywords

labellingcocomparability graphperfect dominationcocomparability ordering

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (21)

Perfect edge domination and efficient edge domination in graphs ⋮ A dichotomy for weighted efficient dominating sets with bounded degree vertices ⋮ Weighted efficient domination problem on some perfect graphs ⋮ Efficient domination through eigenvalues ⋮ A Taxonomy of Perfect Domination ⋮ Hereditary Efficiently Dominatable Graphs ⋮ Weighted domination of cocomparability graphs ⋮ Efficient minus and signed domination in graphs ⋮ On weighted efficient total domination ⋮ Weighted efficient domination in two subclasses of \(P_6\)-free graphs ⋮ Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs ⋮ Counting independent sets in a tolerance graph ⋮ Efficient domination for classes of \(P_6\)-free graphs ⋮ Unnamed Item ⋮ The \(k\)-power domination problem in weighted trees ⋮ Weighted efficient domination for some classes of \(H\)-free and of \((H_1, H_2)\)-free graphs ⋮ Algorithms for unipolar and generalized split graphs ⋮ On efficient domination for some classes of \(H\)-free chordal graphs ⋮ Solving the weighted efficient edge domination problem on bipartite permutation graphs ⋮ Weighted connected domination and Steiner trees in distance-hereditary graphs ⋮ New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs

Cites Work

• The weighted perfect domination problem
• On the domatic number of interval graphs
• A unified approach to domination problems on interval graphs
• Total domination in interval graphs revisited
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Linear algorithm for domatic number problem on interval 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
• Efficient parallel algorithms for permutation graphs
• The weighted perfect domination problem and its variants
• Perfect codes in graphs
• Domination on Cocomparability Graphs
• Total Domination and Irredundance in Weighted Interval Graphs
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• The Domatic Number Problem in Interval Graphs
• Total domination in interval graphs
• Total domination in interval graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Weighted independent perfect domination on cocomparability graphs