Weighted Upper Edge Cover: Complexity and Approximability

DOI10.7155/jgaa.00519zbMath1433.05261MaRDI 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 set; upper edge cover; weighted version of maximum minimal edge cover

Mathematics Subject Classification ID

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

05C22: Signed and weighted graphs

Related Items

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