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

DOI10.1016/J.IPL.2018.08.002zbMATH Open1478.68204OpenAlexW2888513371WikidataQ129360340 ScholiaQ129360340MaRDI QIDQ1799604FDOQ1799604

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

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

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)

Cites Work

• Perfect codes in graphs
• Title not available (Why is that?)
• Independence and efficient domination on \(P_6\)-free graphs
• The weighted perfect domination problem and its variants
• New polynomial cases of the weighted efficient domination problem
• Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs
• 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)