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

DOI10.1016/J.TCS.2024.114628MaRDI QIDQ6562874FDOQ6562874

Authors Kazuhiro Kurita, Kunihiro Wasa

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

• A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
• A polynomial delay algorithm for enumerating minimal dominating sets in chordal graphs
• Approximating the tree and tour covers of a graph
• Approximation Methods for Multiobjective Optimization Problems: A Survey
• Enumerating maximal induced subgraphs
• Enumerating minimal dominating sets in \(K_t\)-free graphs and variants
• Enumeration of minimal dominating sets and variants
• Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties
• Letter to the Editor—An Algorithm for Ranking all the Assignments in Order of Increasing Cost
• On the enumeration of minimal dominating sets and related notions
• Optimal aggregation algorithms for middleware.
• Polynomial delay algorithm for listing minimal edge dominating sets in graphs
• Polynomial-delay and polynomial-space enumeration of large maximal matchings
• Two Algorithms for Generating Weighted Spanning Trees in Order

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

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