| Item type |
SIG Technical Reports(1) |
| 公開日 |
2023-08-30 |
| タイトル |
|
|
タイトル |
Enumerating minimal vertex covers and dominating sets with capacity and/or connectivity constraints |
| タイトル |
|
|
言語 |
en |
|
タイトル |
Enumerating minimal vertex covers and dominating sets with capacity and/or connectivity constraints |
| 言語 |
|
|
言語 |
eng |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_18gh |
|
資源タイプ |
technical report |
| 著者所属 |
|
|
|
Hokkaido University |
| 著者所属 |
|
|
|
Nagoya University |
| 著者所属 |
|
|
|
Tokai University |
| 著者所属 |
|
|
|
Nagoya University |
| 著者所属(英) |
|
|
|
en |
|
|
Hokkaido University |
| 著者所属(英) |
|
|
|
en |
|
|
Nagoya University |
| 著者所属(英) |
|
|
|
en |
|
|
Tokai University |
| 著者所属(英) |
|
|
|
en |
|
|
Nagoya University |
| 著者名 |
Yasuaki, Kobayashi
Kazuhiro, Kurita
Yasuko, Matsui
Hirotaka, Ono
|
| 著者名(英) |
Yasuaki, Kobayashi
Kazuhiro, Kurita
Yasuko, Matsui
Hirotaka, Ono
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
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 cover, our algorithm runs in polynomial delay even on the class of d-claw free graphs, which extends the result on bounded-degree graphs. To complement these algorithmic results, we show that the problems of enumerating minimal connected vertex covers and minimal capacitated vertex covers in bipartite graphs are at least as hard as enumerating minimal transversals in hypergraphs. |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
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 cover, our algorithm runs in polynomial delay even on the class of d-claw free graphs, which extends the result on bounded-degree graphs. To complement these algorithmic results, we show that the problems of enumerating minimal connected vertex covers and minimal capacitated vertex covers in bipartite graphs are at least as hard as enumerating minimal transversals in hypergraphs. |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AN1009593X |
| 書誌情報 |
研究報告アルゴリズム（AL）
巻 2023-AL-194,
号 8,
p. 1-8,
発行日 2023-08-30
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
2188-8566 |
| Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-AL23194008.pdf (1.1 MB)
