Approximation algorithms for maximum weight k-coverings of graphs by packings
DOI10.1142/S1793830921500993zbMath1491.68269OpenAlexW3127729520MaRDI QIDQ5063275
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
packingNP-completenessapproximation algorithmsinterval filament graphsmaximum-weight coveringvertex hereditary
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Cites Work
- Unnamed Item
- Unnamed Item
- Maximum weight independent sets and cliques in intersection graphs of filaments
- Trapezoid graphs and generalizations, geometry and algorithms
- Packing \(r\)-cliques in weighted chordal graphs
- Algorithms for \(\mathcal{GA}\mathrm{-}\mathcal H\) reduced graphs
- Brambles and independent packings in chordal graphs
- The maximum k-colorable subgraph problem for chordal graphs
- Covering and coloring polygon-circle graphs
- Induced matchings in intersection graphs.
- Algorithms for maximum weight induced paths
- Partitioning chordal graphs into independent sets and cliques
- Intersection graphs of Helly families of subtrees
- Algorithms for induced biclique optimization problems
- New insights on \(\mathbf{GA}\)-\(\mathbf H\) reduced graphs
- 3D-interval-filament graphs
- Approximating the minimum clique cover and other hard problems in subtree filament graphs
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Independent packings in structured graphs
- Approximating the throughput of multiple machines under real-time scheduling
- ALGORITHMS ON SUBGRAPH OVERLAP GRAPHS
- Impact of the Energy Model on the Complexity of RNA Folding with Pseudoknots
- Algorithms on Subtree Filament Graphs
- An analysis of approximations for maximizing submodular set functions—I
This page was built for publication: Approximation algorithms for maximum weight k-coverings of graphs by packings
