Weighted Upper Edge Cover: Complexity and Approximability

DOI10.7155/jgaa.00519zbMath1433.05261OpenAlexW3005486246MaRDI QIDQ5216282

Florian Sikora, Kaveh Khoshkhah, Jérôme Monnot, Mehdi Khosravian Ghadikolaei

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

zbMATH Keywords

maximum independent setupper edge coverweighted version of maximum minimal edge cover

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Signed and weighted graphs (05C22)

Related Items (3)

In)approximability of Maximum Minimal FVS ⋮ Algorithmic aspects of upper edge domination ⋮ (In)approximability of maximum minimal FVS

Cites Work

• Unnamed Item
• Unnamed Item
• On the max min vertex cover problem
• Domination, independent domination, and duality in strongly chordal graphs
• Dominating sets for split and bipartite graphs
• Domination in convex and chordal bipartite graphs
• Independent domination in chordal graphs
• On the algorithmic complexity of twelve covering and independence parameters of graphs
• Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
• Some APX-completeness results for cubic graphs
• Extended spanning star forest problems
• The many facets of upper domination
• The weighted independent domination problem is NP-complete for chordal graphs
• Fast algorithms for min independent dominating set
• Improved approximation for spanning star forest in dense graphs
• Weighted upper edge cover: complexity and approximability
• Complexity of approximating bounded variants of optimization problems
• Improved approximation algorithms for the spanning star forest problem
• More results on weighted independent domination
• Weighted upper domination number
• Complexity and approximability of extended spanning star forest problems in general and complete graphs
• On lazy bureaucrat scheduling with common deadlines
• A Boundary Property for Upper Domination
• On Variants of the Spanning Star Forest Problem
• On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP
• An Improved Approximation Bound for Spanning Star Forest and Color Saving
• Energy-Efficient Communication in Multi-interface Wireless Networks
• The Lazy Matroid Problem
• Improved Approximation Algorithms for the Spanning Star Forest Problem
• Approximating the Spanning Star Forest Problem and Its Application to Genomic Sequence Alignment
• A Dynamic Programming Approach to the Dominating Set Problem on k-Trees
• Enclaveless sets and MK-Systems
• Edge Dominating Sets in Graphs
• Dominating Sets in Chordal Graphs
• Maximum Minimal Vertex Cover Parameterized by Vertex Cover
• Non-approximability results for optimization problems on bounded degree instances
• The maximum weight spanning star forest problem on cactus graphs
• Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation
• SOFSEM 2006: Theory and Practice of Computer Science

This page was built for publication: Weighted Upper Edge Cover: Complexity and Approximability