Anzeige
Erschienen in:
2018 | OriginalPaper | Buchkapitel
Approximating Domination on Intersection Graphs of Paths on a Grid
verfasst von : Saeed Mehrabi
Erschienen in: Approximation and Online Algorithms
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 graph G is called \({B}_k\)-EPG (resp., \({B}_k\)-VPG), for some constant \(k\ge 0\), if it has a string representation on an axis-parallel grid such that each vertex is a path with at most k bends and two vertices are adjacent in G if and only if the corresponding strings share at least one grid edge (resp., the corresponding strings intersect each other). If two adjacent strings of a B\(_k\)-VPG graph intersect each other exactly once, then the graph is called a one-string B\(_k\)-VPG graph.
In this paper, we study the Minimum Dominating Set problem on \(\textsc {B}_1\text {-}{\textsc {EPG}}\) and \(\textsc {B}_1\text {-}{\textsc {VPG}}\) graphs. We first give an O(1)-approximation algorithm on one-string \(\textsc {B}_1\text {-}{\textsc {VPG}}\) graphs, providing the first constant-factor approximation algorithm for this problem. Moreover, we show that the Minimum Dominating Set problem is APX-hard on \(\textsc {B}_1\text {-}{\textsc {EPG}}\) graphs, ruling out the possibility of a PTAS unless P = NP. Finally, to complement our APX-hardness result, we give constant-factor approximation algorithms for the Minimum Dominating Set problem on two non-trivial subclasses of \(\textsc {B}_1\text {-}{\textsc {EPG}}\) graphs.