Optimal Algorithm for Paired-Domination in Distance-Hereditary Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910719971164160 |
|---|---|
| author | Mu, Ta-Yu Lin, Ching-Chi |
| author_facet | Mu, Ta-Yu Lin, Ching-Chi |
| contents | The domination problem and its variants represent a classical domain within algorithmic graph theory. Among these variants, the paired-domination problem holds particular prominence due to its real-world implications in security and surveillance domains. Given an input graph $G$, the paired-domination problem involves identifying a minimum dominating set $D$ that induces a subgraph of $G$ with a perfect matching. Lin et al.~[\emph{Paired-domination problem on distance-hereditary graphs}, Algorithmica, 2020] previously presented a solution to this problem with a time complexity of $O(n^2)$. This paper significantly enhances their findings by introducing an $O(n+m)$-time algorithm. Furthermore, the time complexity of this algorithm can be reduced to $O(n)$ when provided with a decomposition tree for the graph $G$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_19476 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Optimal Algorithm for Paired-Domination in Distance-Hereditary Graphs Mu, Ta-Yu Lin, Ching-Chi Data Structures and Algorithms Combinatorics The domination problem and its variants represent a classical domain within algorithmic graph theory. Among these variants, the paired-domination problem holds particular prominence due to its real-world implications in security and surveillance domains. Given an input graph $G$, the paired-domination problem involves identifying a minimum dominating set $D$ that induces a subgraph of $G$ with a perfect matching. Lin et al.~[\emph{Paired-domination problem on distance-hereditary graphs}, Algorithmica, 2020] previously presented a solution to this problem with a time complexity of $O(n^2)$. This paper significantly enhances their findings by introducing an $O(n+m)$-time algorithm. Furthermore, the time complexity of this algorithm can be reduced to $O(n)$ when provided with a decomposition tree for the graph $G$. |
| title | Optimal Algorithm for Paired-Domination in Distance-Hereditary Graphs |
| topic | Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2411.19476 |