An Approximation Algorithm for $K$-best Enumeration of Minimal Connected Edge Dominating Sets with Cardinality Constraints
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911873296760832 |
|---|---|
| author | Kurita, Kazuhiro Wasa, Kunihiro |
| author_facet | Kurita, Kazuhiro Wasa, Kunihiro |
| contents | \emph{$K$-best enumeration}, which asks to output $k$-best solutions without duplication, is a helpful tool in data analysis for many fields. In such fields, graphs typically represent data. Thus subgraph enumeration has been paid much attention to such fields. However, $k$-best enumeration tends to be intractable since, in many cases, finding one optimum solution is \NP-hard. To overcome this difficulty, we combine $k$-best enumeration with a concept of enumeration algorithms called \emph{approximation enumeration algorithms}. As a main result, we propose a $4$-approximation algorithm for minimal connected edge dominating sets which outputs $k$ minimal solutions with cardinality at most $4\cdot\OPT$, where $\OPT$ is the cardinality of a minimum solution which is \emph{not} outputted by the algorithm. Our proposed algorithm runs in $\order{nm^2Δ}$ delay, where $n$, $m$, $Δ$ are the number of vertices, the number of edges, and the maximum degree of an input graph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2201_08647 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | An Approximation Algorithm for $K$-best Enumeration of Minimal Connected Edge Dominating Sets with Cardinality Constraints Kurita, Kazuhiro Wasa, Kunihiro Data Structures and Algorithms \emph{$K$-best enumeration}, which asks to output $k$-best solutions without duplication, is a helpful tool in data analysis for many fields. In such fields, graphs typically represent data. Thus subgraph enumeration has been paid much attention to such fields. However, $k$-best enumeration tends to be intractable since, in many cases, finding one optimum solution is \NP-hard. To overcome this difficulty, we combine $k$-best enumeration with a concept of enumeration algorithms called \emph{approximation enumeration algorithms}. As a main result, we propose a $4$-approximation algorithm for minimal connected edge dominating sets which outputs $k$ minimal solutions with cardinality at most $4\cdot\OPT$, where $\OPT$ is the cardinality of a minimum solution which is \emph{not} outputted by the algorithm. Our proposed algorithm runs in $\order{nm^2Δ}$ delay, where $n$, $m$, $Δ$ are the number of vertices, the number of edges, and the maximum degree of an input graph. |
| title | An Approximation Algorithm for $K$-best Enumeration of Minimal Connected Edge Dominating Sets with Cardinality Constraints |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2201.08647 |