Efficient constant-factor approximate enumeration of minimal subsets for monotone properties with weight constraints

Exact enumeration problems, generating functions (05A15) Combinatorial optimization (90C27) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Generating cut conjunctions in graphs and related problems
Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties
A new approach for approximating node deletion problems
Graph minors. V. Excluding a planar graph
On generating all maximal independent sets
On enumerating all minimal solutions of feedback problems
Optimal aggregation algorithms for middleware.
Reverse search for enumeration
Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
Paradigms for parameterized enumeration
The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
A Faster FPT Algorithm and a Smaller Kernel for Block Graph Vertex Deletion
A Quartic Kernel for Pathwidth-One Vertex Deletion
Enumeration of Minimal Dominating Sets and Variants
The Design of Arbitrage-Free Data Pricing Schemes
A Method for the Solution of the N th Best Path Problem
Easy problems for tree-decomposable graphs
Polynomial Delay Algorithm for Listing Minimal Edge Dominating Sets in Graphs
On the Complexity of Dualization of Monotone Disjunctive Normal Forms
A Greedy Heuristic for the Set-Covering Problem
A linear-time approximation algorithm for the weighted vertex cover problem
Two Algorithms for Generating Weighted Spanning Trees in Order
A New Algorithm for Generating All the Maximal Independent Sets
On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
Submodular Function Minimization under Covering Constraints
Suboptimal cuts: Their enumeration, weight and number
New polynomial delay bounds for maximal subgraph enumeration by proximity search
Approximating Bounded Degree Deletion via Matroid Matching
Steiner Tree Approximation via Iterative Randomized Rounding
Database Programming Languages
Parameterized Algorithms
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
Integer Programming and Combinatorial Optimization
Polylogarithmic Approximation Algorithms for Weighted-ℱ-deletion Problems
LATIN 2004: Theoretical Informatics
A tight approximation algorithm for the cluster vertex deletion problem
Polynomial-delay and polynomial-space enumeration of large maximal matchings
Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes
A simple \((2 + \epsilon)\)-approximation algorithm for split vertex deletion
Enumerating maximal induced subgraphs

This page was built for publication: Efficient constant-factor approximate enumeration of minimal subsets for monotone properties with weight constraints