Anzeige
Erschienen in:
2019 | OriginalPaper | Buchkapitel
Approximating Minimum Dominating Set on String Graphs
verfasst von : Dibyayan Chakraborty, Sandip Das, Joydeep Mukherjee
Erschienen in: Graph-Theoretic Concepts in Computer Science
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
A string graph is an intersection graph of simple curves on the plane. For \(k\ge 0\), \(B_k\)-VPG graphs are intersection graphs of simple rectilinear curves having at most k cusps (bends). It is well-known that any string graph is a \(B_k\)-VPG graph for some value of k. For \(k\ge 0\), unit \(B_k\)-VPG graphs are intersection graphs of simple rectilinear curves having at most k cusps (bends) and each segment of the curve being unit length. Any string graph is a unit-\(B_k\)-VPG graph for some value of k.
In this article, we show that the Minimum Dominating Set (MDS) problem for unit \(B_k\)-VPG graphs is NP-Hard for all \(k \ge 1\) and provide an \(O(k^4)\)-approximation algorithm for all \(k\ge 0\). Furthermore, we also provide an 8-approximation for the MDS problem for the vertically-stabbed L-graphs, intersection graphs of L-paths intersecting a common vertical line. The same problem is known to be APX-Hard (MFCS, 2018). As a by-product of our proof, we obtained a 2-approximation algorithm for the stabbing segment with rays (SSR) problem introduced and studied by Katz et al. (Comput. Geom. 2005).