Cover Image

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

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kobayashi, Yasuaki, Kurita, Kazuhiro, Mann, Kevin, Matsui, Yasuko, Ono, Hirotaka
Format:	Preprint
Published:	2023
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Efficient Constant-Factor Approximate Enumeration of Minimal Subsets for Monotone Properties with Weight Constraints
by: Kobayashi, Yasuaki, et al.
Published: (2020)

On the complexity of finding a spanning even tree in a graph
by: Hanaka, Tesshu, et al.
Published: (2024)

Polynomial-Delay Enumeration of Large Maximal Common Independent Sets in Two Matroids and Beyond
by: Kobayashi, Yasuaki, et al.
Published: (2023)

On the Complexity of Hyperpath and Minimal Separator Enumeration in Directed Hypergraphs
by: Kurita, Kazuhiro, et al.
Published: (2025)

The Complexity of Maximal Common Subsequence Enumeration
by: Buzzega, Giovanni, et al.
Published: (2025)

The Complexity of Maximal/Closed Frequent Tree Mining for Bounded Height Trees
by: Komoto, Kenta, et al.
Published: (2026)

Enumerating Graphlets with Amortized Time Complexity Independent of Graph Size
by: Conte, Alessio, et al.
Published: (2024)

Finding One Local Optimum Is Easy -- but What About Two?
by: Kobayashi, Yasuaki, et al.
Published: (2025)

Algorithms for Optimally Shifting Intervals under Intersection Graph Models
by: Honorato-Droguett, Nicolás, et al.
Published: (2023)

On the Complexity of Minimising the Moving Distance for Dispersing Objects
by: Honorato-Droguett, Nicolás, et al.
Published: (2025)

An Approximation Algorithm for $K$-best Enumeration of Minimal Connected Edge Dominating Sets with Cardinality Constraints
by: Kurita, Kazuhiro, et al.
Published: (2022)

Computing diverse pair of solutions for tractable SAT
by: Gima, Tatsuya, et al.
Published: (2024)

Structural Parameterizations of Vertex Integrity
by: Gima, Tatsuya, et al.
Published: (2023)

Enumerating minimal dominating sets and variants in chordal bipartite graphs
by: Castelo, Emanuel, et al.
Published: (2025)

Enumerating minimal dominating sets in the (in)comparability graphs of bounded dimension posets
by: Bonamy, Marthe, et al.
Published: (2020)

Enumerating all minimal hitting sets in polynomial total time
by: Wild, Marcel
Published: (2023)

Fast and Practical Single-Exponential Algorithms for Branchwidth
by: Kaneda, Taiki, et al.
Published: (2026)

Structural Parameterizations of $k$-Planarity
by: Gima, Tatsuya, et al.
Published: (2025)

Parameterized Complexity of Finding Dissimilar Shortest Paths
by: Funayama, Ryo, et al.
Published: (2024)

Enumerating minimal solution sets for metric graph problems
by: Bergougnoux, Benjamin, et al.
Published: (2023)

Minimum sum vertex cover: kernelization and parameterized algorithms
by: Cao, Yixin, et al.
Published: (2024)

2-Layer Fan-Planarity in Polynomial Time
by: Kobayashi, Yasuaki, et al.
Published: (2025)

Forcing a unique minimum spanning tree and a unique shortest path
by: Gima, Tatsuya, et al.
Published: (2025)

Algorithmic study on liar's vertex-edge domination problem
by: Bhattacharya, Debojyoti, et al.
Published: (2023)

Liar's vertex-edge domination in unit disk graph
by: Bhattacharya, Debojyoti, et al.
Published: (2025)

Liar's vertex-edge domination in subclasses of chordal graphs
by: Bhattacharya, Debojyoti, et al.
Published: (2025)

Dichotomies for Tree Minor Containment with Structural Parameters
by: Gima, Tatsuya, et al.
Published: (2023)

Sequentially Swapping Tokens: Further on Graph Classes
by: Kiya, Hironori, et al.
Published: (2022)

Self-referential instances of the dominating set problem are irreducible
by: Zhou, Guangyan
Published: (2026)

Pre-assignment problem for unique minimum vertex cover on bounded clique-width graphs
by: An, Shinwoo, et al.
Published: (2024)

Hitting Geodesic Intervals in Structurally Restricted Graphs
by: Gima, Tatsuya, et al.
Published: (2025)

Kernelization for list $H$-coloring for graphs with small vertex cover
by: Piecyk, Marta, et al.
Published: (2025)

A polynomial delay algorithm generating all potential maximal cliques in triconnected planar graphs
by: Grigoriev, Alexander, et al.
Published: (2025)

Finding a Minimum Spanning Tree with a Small Non-Terminal Set
by: Hanaka, Tesshu, et al.
Published: (2023)

Data reduction for directed feedback vertex set on graphs without long induced cycles
by: Dirks, Jona, et al.
Published: (2023)

Improved approximation ratio for covering pliable set families
by: Nutov, Zeev
Published: (2024)

Approximation and parameterized algorithms for covering disjointness-compliable set families
by: Nutov, Zeev, et al.
Published: (2025)

A Critical Pair Enumeration Algorithm for String Diagram Rewriting
by: Matsui, Anna, et al.
Published: (2026)

The connectivity carcass of a vertex subset in a graph: both odd and even case
by: Baswana, Surender, et al.
Published: (2025)

Transversal Rank, Conformality and Enumeration
by: Schirneck, Martin
Published: (2026)