Approximation algorithms for maximum weight k-coverings of graphs by packings

DOI10.1142/S1793830921500993MaRDI QIDQ5063275zbMATH OpenOpenAlexFDO

Authors Fanica Gavril, Mordechai Shalom, Shmuel Zaks

Publication date 17 March 2022

Published in Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s1793830921500993

zbMATH Keywords

approximation algorithmsinterval filament graphsmaximum-weight coveringNP-completenesspackingvertex hereditary

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Recommendations

• Primal-dual approximation algorithms for a packing-covering pair of problems
• scientific article; zbMATH DE number 125473
• Approximation algorithms and hardness results for the clique packing problem
• Approximation algorithms and hardness results for the clique packing problem
• On local search for weighted \(k\)-set packing
• Equivalence between the minimum covering problem and the maximum matching problem
• A simple LP-free approximation algorithm for the minimum weight vertex cover problem
• A note on the set union knapsack problem
• scientific article; zbMATH DE number 1263280
• Algorithms – ESA 2004

Cites work

• 3D-interval-filament graphs
• Algorithms for \(\mathcal{GA}\mathrm{-}\mathcal H\) reduced graphs
• Algorithms for induced biclique optimization problems
• Algorithms for maximum weight induced paths
• Algorithms on subgraph overlap graphs
• Algorithms on Subtree Filament Graphs
• An analysis of approximations for maximizing submodular set functions—I
• Approximating the minimum clique cover and other hard problems in subtree filament graphs
• Approximating the throughput of multiple machines under real-time scheduling
• Brambles and independent packings in chordal graphs
• Covering and coloring polygon-circle graphs
• scientific article; zbMATH DE number 1303779 (Why is no real title available?)
• scientific article; zbMATH DE number 1323125 (Why is no real title available?)
• Impact of the energy model on the complexity of RNA folding with pseudoknots
• Independent packings in structured graphs
• Induced matchings in intersection graphs.
• Intersection graphs of Helly families of subtrees
• Maximum weight independent sets and cliques in intersection graphs of filaments
• New insights on \(\mathbf{GA}\)-\(\mathbf H\) reduced graphs
• Packing \(r\)-cliques in weighted chordal graphs
• Partitioning chordal graphs into independent sets and cliques
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The maximum k-colorable subgraph problem for chordal graphs
• Trapezoid graphs and generalizations, geometry and algorithms

Cited in

(7)

• Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs
• New insights on \(\mathbf{GA}\)-\(\mathbf H\) reduced graphs
• On the asymptotic optimality of a solution of the Euclidean problem of covering a graph by \(m\) nonadjacent cycles of maximum total weight
• Algorithms for finding an independent \(\{K_1,K_2\}\)-packing of maximum weight in a graph
• scientific article; zbMATH DE number 1405806 (Why is no real title available?)
• Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs
• Algorithms for \(\mathcal{GA}\mathrm{-}\mathcal H\) reduced graphs

This page was built for publication: Approximation algorithms for maximum weight k-coverings of graphs by packings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5063275)