An approximation algorithm for \(K\)-best enumeration of minimal connected edge dominating sets with cardinality constraints

DOI10.1016/j.tcs.2024.114628MaRDI QIDQ6562874

Kunihiro Wasa, Kazuhiro Kurita

Publication date: 27 June 2024

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

approximate algorithmoutput-sensitive enumerationconnected edge dominating set\(K\)-best enumeration

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Approximating the tree and tour covers of a graph
• Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties
• Optimal aggregation algorithms for middleware.
• A Polynomial Delay Algorithm for Enumerating Minimal Dominating Sets in Chordal Graphs
• Enumeration of Minimal Dominating Sets and Variants
• Polynomial Delay Algorithm for Listing Minimal Edge Dominating Sets in Graphs
• Two Algorithms for Generating Weighted Spanning Trees in Order
• Enumerating Minimal Dominating Sets in Kt-free Graphs and Variants
• Approximation Methods for Multiobjective Optimization Problems: A Survey
• On the Enumeration of Minimal Dominating Sets and Related Notions
• Letter to the Editor—An Algorithm for Ranking all the Assignments in Order of Increasing Cost
• A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
• Polynomial-delay and polynomial-space enumeration of large maximal matchings
• Enumerating maximal induced subgraphs

This page was built for publication: An approximation algorithm for \(K\)-best enumeration of minimal connected edge dominating sets with cardinality constraints