Weighted upper edge cover: complexity and approximability

DOI10.7155/JGAA.00519MaRDI QIDQ5216282zbMATH OpenOpenAlexFDO

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)

Copyright license Creative Commons Attribution 4.0 International

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

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)

Recommendations

• Weighted upper edge cover: complexity and approximability
• Algorithmic aspects of upper edge domination
• On approximability of the independent/connected edge dominating set problems
• scientific article; zbMATH DE number 2080196
• scientific article; zbMATH DE number 2119674

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A Dynamic Programming Approach to the Dominating Set Problem on k-Trees
• A boundary property for upper domination
• 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 in Chordal Graphs
• 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
• 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
• 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

(6)

• Correction to: ``Weighted upper edge cover: complexity and approximability
• In)approximability of Maximum Minimal FVS
• Algorithmic aspects of upper edge domination
• Weighted upper edge cover: complexity and approximability
• (In)approximability of maximum minimal FVS
• Upper Clique Transversals in Graphs

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)