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

DOI10.1142/S1793830921500993zbMATH Open1491.68269OpenAlexW3127729520MaRDI QIDQ5063275FDOQ5063275

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

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

zbMATH Keywords

approximation algorithmsNP-completenesspackinginterval filament graphsmaximum-weight coveringvertex hereditary

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (7)

• Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs
• Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs
• Algorithms for finding an independent \(\{K_1,K_2\}\)-packing of maximum weight in a graph
• 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 \(\mathcal{GA}\mathrm{-}\mathcal H\) reduced graphs
• New insights on \(\mathbf{GA}\)-\(\mathbf H\) reduced graphs
• Title not available (Why is that?)

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)