Enumerating minimal vertex covers and dominating sets with capacity and/or connectivity constraints

DOI10.1007/978-3-031-63021-7_18MaRDI QIDQ7021094zbMATH OpenFDO

Authors Yasuaki Kobayashi, Kazuhiro Kurita, Yasuko Matsui, Hirotaka Ono

Publication date 28 February 2025

Full work available at URL https://doi.org/10.1007/978-3-031-63021-7_18

zbMATH Keywords

capacitated dominating setcapacitated vertex coverconnected dominating setconnected vertex coverenumeration algorithms

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Cites work

• A New Algorithm for Generating All the Maximal Independent Sets
• A polynomial delay algorithm for enumerating minimal dominating sets in chordal graphs
• Algorithm 457: finding all cliques of an undirected graph
• Algorithm Theory - SWAT 2004
• An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
• Approximation algorithms for connected dominating sets
• Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
• Complexity of identification and dualization of positive Boolean functions
• Computational aspects of monotone dualization: a brief survey
• Connected domination and steiner set on asteroidal triple-free graphs
• Deterministic parameterized connected vertex cover
• Enumerating minimal connected dominating sets
• Enumerating minimal dominating sets in \(K_t\)-free graphs and variants
• Enumerating Spanning and Connected Subsets in Graphs and Matroids
• Enumeration and maximum number of minimal connected vertex covers in graphs
• Finding cliques in social networks: a new distribution-free model
• Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties
• Generating Minimal k-Vertex Connected Spanning Subgraphs
• scientific article; zbMATH DE number 1931696 (Why is no real title available?)
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• Linear delay enumeration and monadic second-order logic
• New Results on Monotone Dualization and Generating Hypergraph Transversals
• On enumerating all minimal solutions of feedback problems
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• On the enumeration of minimal dominating sets and related notions
• On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
• Polynomial delay algorithm for listing minimal edge dominating sets in graphs
• Proximity Search for Maximal Subgraph Enumeration
• Solving connected dominating set faster than \(2^n\)
• Sublinear-space and bounded-delay algorithms for maximal clique enumeration in graphs
• The worst-case time complexity for generating all maximal cliques and computational experiments

Cited in

(3)

• Enumerating minimal defensive alliances
• Enumerating minimal connected dominating sets
• Enumerating minimal dominating sets and variants in chordal bipartite graphs

This page was built for publication: Enumerating minimal vertex covers and dominating sets with capacity and/or connectivity constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7021094)