Cover Image

An Approximation Algorithm for $K$-best Enumeration of Minimal Connected Edge Dominating Sets with Cardinality Constraints

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kurita, Kazuhiro, Wasa, Kunihiro
Format:	Preprint
Published:	2022
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)

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

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

Reconfiguration and Enumeration of Optimal Cyclic Ladder Lotteries
by: Nozaki, Yuta, et al.
Published: (2024)

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

Enumerating minimal vertex covers and dominating sets with capacity and/or connectivity constraints
by: Kobayashi, Yasuaki, et al.
Published: (2023)

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

Dynamic $((1+ε)\ln n)$-Approximation Algorithms for Minimum Set Cover and Dominating Set
by: Solomon, Shay, et al.
Published: (2023)

Enumeration of Minimal Hitting Sets Parameterized by Treewidth
by: Kenig, Batya, et al.
Published: (2024)

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

Connected Partitions via Connected Dominating Sets
by: Niklanovits, Aikaterini, et al.
Published: (2025)

Dominating Set with Quotas: Balancing Coverage and Constraints
by: Chatterjee, Sobyasachi, et al.
Published: (2026)

Stable Approximation Algorithms for Dominating Set and Independent Set
by: de Berg, Mark, et al.
Published: (2024)

An Approximation Algorithm for 2-Vertex-Connectivity via Cycle-Restricted 2-Edge-Covers
by: Kobayashi, Yusuke, et al.
Published: (2026)

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

Approximation Algorithms for Connected Maximum Coverage, Minimum Connected Set Cover, and Node-Weighted Group Steiner Tree
by: D'Angelo, Gianlorenzo, et al.
Published: (2025)

Max-Cut with Multiple Cardinality Constraints
by: Makarychev, Yury, et al.
Published: (2025)

9/7-Approximation for Two-Edge-Connectivity and Two-Vertex-Connectivity
by: Çivril, Ali
Published: (2024)

Approximation Algorithms for Steiner Connectivity Augmentation
by: Hathcock, Daniel, et al.
Published: (2023)

Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints
by: Im, Sungjin, et al.
Published: (2025)

Simple Algorithms for Fully Dynamic Edge Connectivity
by: Kenneth-Mordoch, Yotam, et al.
Published: (2025)

An Optimal Algorithm for Cardinality-Constrained Diameter Partitioning
by: Xu, Chao, et al.
Published: (2026)

Approximate Spanning Tree Counting from Uncorrelated Edge Sets
by: Liu, Yang P., et al.
Published: (2025)

A Better-Than-$5/4$-Approximation for Two-Edge Connectivity
by: Hommelsheim, Felix, et al.
Published: (2025)

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

An Enumerative Perspective on Connectivity
by: Akmal, Shyan
Published: (2023)

Enumeration kernels for Vertex Cover and Feedback Vertex Set
by: Bougeret, Marin, et al.
Published: (2025)

A Radius-Sensitive Approximation Algorithm for Connected Submodular Maximization
by: Cervenjak, Philip, et al.
Published: (2026)

Confluence of the Node-Domination and Edge-Domination Hypergraph Rewrite Rules
by: Amarilli, Antoine, et al.
Published: (2025)

Matching (Multi)Cut: Algorithms, Complexity, and Enumeration
by: Gomes, Guilherme C. M., et al.
Published: (2024)

A Unified Approach for Approximating 2-Edge-Connected Spanning Subgraph and 2-Vertex-Connected Spanning Subgraph
by: Çivril, Ali
Published: (2023)

Gabow's Cardinality Matching Algorithm in General Graphs: Implementation and Experiments
by: Ansaripour, Matin, et al.
Published: (2024)

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

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

Efficient Approximation Algorithms for Fair Influence Maximization under Maximin Constraint
by: Rui, Xiaobin, et al.
Published: (2025)

Distributed Approximation Algorithms for Minimum Dominating Set in Locally Nice Graphs
by: Bonamy, Marthe, et al.
Published: (2025)

Exact Optimization for Minimum Dominating Sets
by: Zhu, Enqiang, et al.
Published: (2025)

Enumeration Algorithms for Conjunctive Queries with Projection
by: Deep, Shaleen, et al.
Published: (2021)

Gabow's $O(\sqrt{n}m)$ Maximum Cardinality Matching Algorithm, Revisited
by: Mehlhorn, Kurt, et al.
Published: (2026)

On the (In)Approximability of the Monitoring Edge Geodetic Set Problem
by: Bilò, Davide, et al.
Published: (2025)