Weighted domination of cocomparability graphs

DOI10.1016/S0166-218X(97)80001-7zbMath0898.05077MaRDI QIDQ1382270

Maw-Shang Chang

Publication date: 25 March 1998

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

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

NP-completecocomparability graphscobipartite graphsweighted domination

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (16)

Perfect edge domination and efficient edge domination in graphs ⋮ The weighted independent domination problem is NP-complete for chordal graphs ⋮ Weighted efficient domination problem on some perfect graphs ⋮ Hereditary Efficiently Dominatable Graphs ⋮ Efficient algorithms for the minimum connected domination on trapezoid graphs ⋮ A width parameter useful for chordal and co-comparability graphs ⋮ Graph classes with structured neighborhoods and algorithmic applications ⋮ Efficient minus and signed domination in graphs ⋮ Linear-time algorithm for paired-domination on distance-hereditary graphs ⋮ 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 ⋮ An optimal algorithm to find minimum k-hop dominating set of interval graphs ⋮ Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs ⋮ Weighted efficient domination for some classes of \(H\)-free and of \((H_1, H_2)\)-free graphs ⋮ Linear separation of connected dominating sets in graphs ⋮ An optimal algorithm to find minimum k-hop connected dominating set of permutation graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The weighted perfect domination problem
• Perfect codes over graphs
• Independent domination in chordal graphs
• Dominating sets in perfect graphs
• Incorporating negative-weight vertices in certain vertex-search graph algorithms
• Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
• Hamiltonian cycle is polynomial on cocomparability graphs
• Polynomial algorithms for the weighted perfect domination problems on chordal graphs and split graphs
• Weighted independent perfect domination on cocomparability graphs
• The weighted perfect domination problem and its variants
• Perfect codes in graphs
• Domination on Cocomparability Graphs
• On Comparability and Permutation Graphs
• Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs

This page was built for publication: Weighted domination of cocomparability graphs