Enumerating Minimal Vertex Covers and Dominating Sets with Capacity and/or Connectivity Constraints

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...

Full description

Saved in:
Bibliographic Details
Main Authors: Yasuaki Kobayashi, Kazuhiro Kurita, Kevin Mann, Yasuko Matsui, Hirotaka Ono
Format: Article
Language:English
Published: MDPI AG 2025-02-01
Series:Algorithms
Subjects:
polynomial-delay enumeration
connected vertex cover
connected dominating set
capacitated vertex cover
capacitated dominating set
Online Access:https://www.mdpi.com/1999-4893/18/2/112
Tags: Add Tag
No Tags, Be the first to tag this record!

Internet

https://www.mdpi.com/1999-4893/18/2/112

Similar Items