Constant-factor approximation algorithms for domination problems on circle graphs

Graph representations (geometric and intersection representations, etc.) (05C62) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Review text

A circle graph is a graph whose vertex set is a set of chords of a circle and in which two vertices are adjacent if and only if they intersect each other. A subset \(D\) of the vertex set \(V(G)\) of a graph \(G\) is dominating in \(G\), if each vertex of \(G\) either is in \(D\), or is adjacent to a vertex of \(D\). If moreover the subgraph of \(G\) induced by \(D\) is connected, then \(D\) is a connected dominating set of \(G\). If that subgraph has no isolated vertex, then \(D\) is a total dominating set of \(G\). In the paper these concepts are treated from the viewpoint of computational complexity. The minimum dominating set problems (MDS), the minimum connected domination set problem (MCDS) and the minimum total dominating set problem (MTDS) are considered for circle graphs. All of them are NP-complete even for circle graphs. Approximating algorithms for all those problems are presented, each running in time \(O(n^2+ nm)\), where \(n\) is the number of vertices and \(m\) is the number of edges of \(G\). For the entire collection see [Zbl 0933.00045].

Recommendations

Cited in

(7)

This page was built for publication: Constant-factor approximation algorithms for domination problems on circle graphs

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