Weighted upper edge cover: complexity and approximability
From MaRDI portal
Recommendations
Cites work
- A boundary property for upper domination
- A Dynamic Programming Approach to the Dominating Set Problem on k-Trees
- An Improved Approximation Bound for Spanning Star Forest and Color Saving
- Approximating the Spanning Star Forest Problem and Its Application to Genomic Sequence Alignment
- Complexity and approximability of extended spanning star forest problems in general and complete graphs
- Complexity of approximating bounded variants of optimization problems
- Dominating sets for split and bipartite graphs
- Dominating Sets in Chordal Graphs
- Domination in convex and chordal bipartite graphs
- Domination, independent domination, and duality in strongly chordal graphs
- Edge Dominating Sets in Graphs
- Enclaveless sets and MK-Systems
- Energy-Efficient Communication in Multi-interface Wireless Networks
- Extended spanning star forest problems
- Fast algorithms for min independent dominating set
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Improved Approximation Algorithms for the Spanning Star Forest Problem
- Improved approximation algorithms for the spanning star forest problem
- Improved approximation for spanning star forest in dense graphs
- Independent domination in chordal graphs
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Maximum minimal vertex cover parameterized by vertex cover
- More results on weighted independent domination
- Non-approximability results for optimization problems on bounded degree instances
- On lazy bureaucrat scheduling with common deadlines
- On the algorithmic complexity of twelve covering and independence parameters of graphs
- On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP
- On the max min vertex cover problem
- On variants of the spanning star forest problem
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- SOFSEM 2006: Theory and Practice of Computer Science
- Some APX-completeness results for cubic graphs
- The Lazy Matroid Problem
- The many facets of upper domination
- The maximum weight spanning star forest problem on cactus graphs
- The weighted independent domination problem is NP-complete for chordal graphs
- Weighted upper domination number
- Weighted upper edge cover: complexity and approximability
Cited in
(8)- Algorithmic aspects of upper edge domination
- (In)approximability of maximum minimal FVS
- Correction to: ``Weighted upper edge cover: complexity and approximability
- Weighted upper edge cover: complexity and approximability
- In)approximability of Maximum Minimal FVS
- Upper Clique Transversals in Graphs
- Minimum stable cut and treewidth
- Minimum stable cut and treewidth
This page was built for publication: Weighted upper edge cover: complexity and approximability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5216282)
