Enumerating Minimal Vertex Covers and Dominating Sets with Capacity and/or Connectivity Constraints
In this paper, we consider the minimal vertex cover and minimal dominating sets with capacity and/or connectivity constraint enumeration problems. We develop polynomial-delay enumeration algorithms for these problems on bounded-degree graphs. For the case of minimal connected vertex covers, our algo...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-02-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/18/2/112 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | In this paper, we consider the minimal vertex cover and minimal dominating sets with capacity and/or connectivity constraint enumeration problems. 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 <i>d</i>-claw free graphs. This result is extended for bounded-degree graphs and outputs in quasi-polynomial time on general graphs. To complement these algorithmic results, we show that the minimal connected vertex cover, minimal connected dominating set, and minimal capacitated vertex cover enumeration problems in 2-degenerated bipartite graphs are at least as hard as enumerating minimal transversals in hypergraphs. |
|---|---|
| ISSN: | 1999-4893 |