Enumerating minimal vertex covers and dominating sets with capacity and/or connectivity constraints
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913577507487744 |
|---|---|
| author | Kobayashi, Yasuaki Kurita, Kazuhiro Mann, Kevin Matsui, Yasuko Ono, Hirotaka |
| author_facet | Kobayashi, Yasuaki Kurita, Kazuhiro Mann, Kevin Matsui, Yasuko Ono, Hirotaka |
| contents | In this paper, we consider the problems of enumerating minimal vertex covers and minimal dominating sets with capacity and/or connectivity constraints. We develop polynomial-delay enumeration algorithms for these problems on bounded-degree graphs. For the case of minimal connected vertex covers, our algorithms run in polynomial delay even on the class of $d$-claw free graphs, extending the result on bounded-degree graphs, and in output quasi-polynomial time on general graphs. To complement these algorithmic results, we show that the problems of enumerating minimal connected vertex covers, minimal connected dominating sets, and minimal capacitated vertex covers in $2$-degenerated bipartite graphs are at least as hard as enumerating minimal transversals in hypergraphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_16426 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Enumerating minimal vertex covers and dominating sets with capacity and/or connectivity constraints Kobayashi, Yasuaki Kurita, Kazuhiro Mann, Kevin Matsui, Yasuko Ono, Hirotaka Data Structures and Algorithms In this paper, we consider the problems of enumerating minimal vertex covers and minimal dominating sets with capacity and/or connectivity constraints. We develop polynomial-delay enumeration algorithms for these problems on bounded-degree graphs. For the case of minimal connected vertex covers, our algorithms run in polynomial delay even on the class of $d$-claw free graphs, extending the result on bounded-degree graphs, and in output quasi-polynomial time on general graphs. To complement these algorithmic results, we show that the problems of enumerating minimal connected vertex covers, minimal connected dominating sets, and minimal capacitated vertex covers in $2$-degenerated bipartite graphs are at least as hard as enumerating minimal transversals in hypergraphs. |
| title | Enumerating minimal vertex covers and dominating sets with capacity and/or connectivity constraints |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2308.16426 |