Complexity of domination in triangulated plane graphs

DOI10.2478/ausi-2019-0012zbMath1439.05064arXiv1709.00596OpenAlexW3002541291WikidataQ126305686 ScholiaQ126305686MaRDI QIDQ2178742

Dömötör Pálvölgyi

Publication date: 11 May 2020

Published in: Acta Universitatis Sapientiae. Informatica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1709.00596

zbMATH Keywords

planar graphsNP-completenessdomination

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Unnamed Item
• Domination in graphs with bounded propagation: Algorithms, formulations and hardness results
• A special planar satisfiability problem and a consequence of its NP- completeness
• Determining the thickness of graphs is NP-hard
• Domination in Graphs Applied to Electric Power Networks
• Power domination in maximal planar graphs
• OPTIMAL BINARY SPACE PARTITIONS FOR SEGMENTS IN THE PLANE
• The PMU Placement Problem