Weighted upper edge cover: complexity and approximability
DOI10.7155/JGAA.00519zbMATH Open1433.05261OpenAlexW3005486246MaRDI QIDQ5216282FDOQ5216282
Authors: Kaveh Khoshkhah, Mehdi Khosravian Ghadikolaei, Jérôme Monnot, Florian Sikora 
Publication date: 17 February 2020
Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.7155/jgaa.00519
Recommendations
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Signed and weighted graphs (05C22) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Title not available (Why is that?)
- Some APX-completeness results for cubic graphs
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- Complexity of approximating bounded variants of optimization problems
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Non-approximability results for optimization problems on bounded degree instances
- Enclaveless sets and MK-Systems
- Dominating sets for split and bipartite graphs
- Domination in convex and chordal bipartite graphs
- Domination, independent domination, and duality in strongly chordal graphs
- Edge Dominating Sets in Graphs
- Dominating Sets in Chordal Graphs
- On the algorithmic complexity of twelve covering and independence parameters of graphs
- Fast algorithms for min independent dominating set
- SOFSEM 2006: Theory and Practice of Computer Science
- Independent domination in chordal graphs
- The weighted independent domination problem is NP-complete for chordal graphs
- Energy-Efficient Communication in Multi-interface Wireless Networks
- Improved approximation algorithms for the spanning star forest problem
- An Improved Approximation Bound for Spanning Star Forest and Color Saving
- Approximating the Spanning Star Forest Problem and Its Application to Genomic Sequence Alignment
- On the max min vertex cover problem
- On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP
- A Dynamic Programming Approach to the Dominating Set Problem on k-Trees
- A boundary property for upper domination
- Improved Approximation Algorithms for the Spanning Star Forest Problem
- The many facets of upper domination
- On lazy bureaucrat scheduling with common deadlines
- The Lazy Matroid Problem
- Extended spanning star forest problems
- The maximum weight spanning star forest problem on cactus graphs
- Improved approximation for spanning star forest in dense graphs
- Weighted upper edge cover: complexity and approximability
- Weighted upper domination number
- Maximum minimal vertex cover parameterized by vertex cover
- Complexity and approximability of extended spanning star forest problems in general and complete graphs
- More results on weighted independent domination
- On variants of the spanning star forest problem
Cited In (6)
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)
