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

DOI10.1016/0377-2217(94)90163-5zbMath0806.90124OpenAlexW2059231566MaRDI QIDQ1328622

Chain-Chin Yen, Richard Chia-Tung 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-completeseries-parallel graphsparsing treeweighted perfect domination problem

Mathematics Subject Classification ID

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

Related Items (8)

Weighted efficient domination problem on some perfect graphs ⋮ Weighted independent perfect domination on cocomparability graphs ⋮ The weighted perfect domination problem and its variants ⋮ Hereditary Efficiently Dominatable Graphs ⋮ Risk models for the prize collecting Steiner tree problems with interval data ⋮ Perfect domination and small cycles ⋮ A linear time algorithm for a variant of the MAX CUT problem in series parallel graphs ⋮ Solving the weighted efficient edge domination problem on bipartite permutation graphs

Cites Work

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

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