Polynomial-time algorithm for weighted efficient domination problem on diameter three planar graphs

DOI10.1016/J.IPL.2018.08.002MaRDI QIDQ1799604zbMATH OpenOpenAlexWikidataFDO

Authors G. Abrishami, F. Rahbarnia

Publication date 19 October 2018

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2018.08.002

zbMATH Keywords

diametergraph algorithmsplanar graphefficient dominationweighted efficient domination

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• New polynomial cases of the weighted efficient domination problem
• Weighted efficient domination for some classes of \(H\)-free and of \((H_1, H_2)\)-free graphs
• Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs
• On efficient domination for some classes of \(H\)-free chordal graphs
• A dichotomy for weighted efficient dominating sets with bounded degree vertices

Cites work

• scientific article; zbMATH DE number 4085682 (Why is no real title available?)
• Independence and efficient domination on \(P_6\)-free graphs
• New polynomial cases of the weighted efficient domination problem
• Perfect codes in graphs
• Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs
• The weighted perfect domination problem and its variants
• Weighted efficient domination for \(P_5\)-free and \(P_6\)-free graphs

Cited in

(5)

• On efficient domination for some classes of \(H\)-free bipartite graphs
• A dichotomy for weighted efficient dominating sets with bounded degree vertices
• Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs
• New polynomial cases of the weighted efficient domination problem
• Polynomial algorithms for the weighted perfect domination problems on chordal graphs and split graphs

This page was built for publication: Polynomial-time algorithm for weighted efficient domination problem on diameter three planar graphs

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