Efficient and perfect domination on circular-arc graphs

DOI10.1016/J.ENDM.2015.07.051zbMATH Open1347.05146arXiv1502.01523OpenAlexW1487951463MaRDI QIDQ324824FDOQ324824

Authors: Min Chih Lin, Michel J. Mizrahi, Jayme L. Szwarcfiter 

Publication date: 17 October 2016

Abstract: Given a graph $G=(V,E)$, a emph{perfect dominating set} is a subset of vertices $V^{\prime }subseteqV(G)$ such that each vertex $vinV(G)setminus{V}^{\prime }$ is dominated by exactly one vertex $v^{\prime }in{V}^{\prime }$. An emph{efficient dominating set} is a perfect dominating set $V^{\prime }$ where $V^{\prime }$ is also an independent set. These problems are usually posed in terms of edges instead of vertices. Both problems, either for the vertex or edge variant, remains NP-Hard, even when restricted to certain graphs families. We study both variants of the problems for the circular-arc graphs, and show efficient algorithms for all of them.

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

Recommendations

• Weighted efficient domination problem on some perfect graphs
• Perfect edge domination and efficient edge domination in graphs
• Efficient domination and efficient edge domination: a brief survey
• The weighted perfect domination problem and its variants
• Efficient dominating and edge dominating sets for graphs and hypergraphs

zbMATH Keywords

circular-arc graphsefficient dominationperfect domination

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Efficient graph representations
• Linear-time recognition of circular-arc graphs
• Perfect edge domination and efficient edge domination in graphs
• Fast algorithms for some dominating induced matching problems
• Efficient dominating and edge dominating sets for graphs and hypergraphs
• Algorithms for clique-independent sets on subclasses of circular-arc graphs
• Efficient and perfect domination on circular-arc graphs
• On cliques of Helly Circular-arc Graphs
• Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs

Cited In (10)

• Parameterized domination in circle graphs
• Perfect edge domination: hard and solvable cases
• Efficient and perfect domination on circular-arc graphs
• Modelling and solving the perfect edge domination problem
• Weighted efficient domination problem on some perfect graphs
• Title not available (Why is that?)
• Graphs whose vertices of degree at least 2 lie in a triangle
• A constant factor approximation algorithm for boxicity of circular arc graphs
• Efficient reduction for path problems on circular-arc graphs
• Parameterized Domination in Circle Graphs

This page was built for publication: Efficient and perfect domination on circular-arc graphs

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