A linear time algorithm to solve the weighted perfect domination problem in series-parallel graphs

DOI10.1016/0377-2217(94)90163-5MaRDI QIDQ1328622zbMATH OpenOpenAlexFDO

Authors Chain-Chin Yen, R. C. T. Lee

Publication date 1994

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0377-2217(94)90163-5

zbMATH Keywords

linear time algorithmNP-completeparsing treeseries-parallel graphsweighted perfect domination problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Dynamic programming (90C39)

Recommendations

• The weighted perfect domination problem
• The weighted perfect domination problem and its variants
• Polynomial algorithms for the weighted perfect domination problems on chordal graphs and split graphs
• Perfect edge domination and efficient edge domination in graphs
• On domination problems for permutation and other graphs

Cites work

• A linear algorithm for the domination number of a series-parallel graph
• scientific article; zbMATH DE number 3906530 (Why is no real title available?)
• scientific article; zbMATH DE number 3747181 (Why is no real title available?)
• scientific article; zbMATH DE number 3596896 (Why is no real title available?)
• Labeling algorithms for domination problems in sun-free chordal graphs
• Steiner trees, connected domination and strongly chordal graphs
• The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
• The weighted perfect domination problem
• Topology of series-parallel networks
• Towards a theory of domination in graphs

Cited in

(12)

• Solving the weighted efficient edge domination problem on bipartite permutation graphs
• Weighted efficient domination problem on some perfect graphs
• A linear time algorithm for a variant of the MAX CUT problem in series parallel graphs
• Weighted independent perfect domination on cocomparability graphs
• The weighted perfect domination problem and its variants
• A linear time algorithm for weighted \(k\)-fair domination problem in cactus graphs
• Risk models for the prize collecting Steiner tree problems with interval data
• Hereditary efficiently dominatable graphs
• Perfect domination and small cycles
• A linear time algorithm for the minimum-weight feedback vertex set problem in series-parallel graphs
• The weighted perfect domination problem
• A parity domination problem in graphs with bounded treewidth and distance-hereditary graphs

This page was built for publication: A linear time algorithm to solve the weighted perfect domination problem in series-parallel graphs

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