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

DOI10.1016/0377-2217(94)90163-5zbMATH Open0806.90124OpenAlexW2059231566MaRDI QIDQ1328622FDOQ1328622

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

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

zbMATH Keywords

NP-completelinear time algorithmseries-parallel graphsparsing treeweighted perfect domination problem

Mathematics Subject Classification ID

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

Cites Work

• Towards a theory of domination in graphs
• The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
• The weighted perfect domination problem
• Topology of series-parallel networks
• Steiner trees, connected domination and strongly chordal graphs
• Labeling algorithms for domination problems in sun-free chordal graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• A linear algorithm for the domination number of a series-parallel graph
• Title not available (Why is that?)

Cited In (12)

• 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
• Perfect domination and small cycles
• A linear time algorithm for the minimum-weight feedback vertex set problem in series-parallel graphs
• A linear time algorithm for a variant of the MAX CUT problem in series parallel graphs
• The weighted perfect domination problem
• Solving the weighted efficient edge domination problem on bipartite permutation graphs
• Weighted efficient domination problem on some perfect graphs
• Hereditary efficiently dominatable graphs
• The weighted perfect domination problem and its variants
• Weighted independent perfect domination on cocomparability graphs
• 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)