Data reductions and combinatorial bounds for improved approximation algorithms
From MaRDI portal
Publication:899583
DOI10.1016/J.JCSS.2015.11.010zbMath1333.68290arXiv1409.3742OpenAlexW135432853WikidataQ59864893 ScholiaQ59864893MaRDI QIDQ899583
Faisal N. Abu-Khzam, Henning Fernau, Morgan Chopin, Cristina Bazgan
Publication date: 30 December 2015
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1409.3742
Related Items (6)
Domination chain: characterisation, classical complexity, parameterised complexity and approximability ⋮ Minimal Roman dominating functions: extensions and enumeration ⋮ Parameterized approximation via fidelity preserving transformations ⋮ Knapsack problems: a parameterized point of view ⋮ The many facets of upper domination ⋮ Algorithmic Aspects of Upper Domination: A Parameterised Perspective
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- A novel parameterised approximation algorithm for \textsc{minimum vertex cover}
- Combinatorics for smaller kernels: the differential of a graph
- Lower bounds on the differential of a graph
- Upper bounds on Roman domination numbers of graphs
- A note on the k-domination number of a graph
- Approximation hardness of dominating set problems in bounded degree graphs
- Upper bounds on the \(k\)-domination number and the \(k\)-Roman domination number
- Generalized independence and domination in graphs
- Improved approximation algorithms for the spanning star forest problem
- Computing the differential of a graph: hardness, approximability and exact algorithms
- Parameterized Approximation Algorithms for Hitting Set
- Roman Domination on 2-Connected Graphs
- The Robust Set Problem: Parameterized Complexity and Approximation
- Relations between the Roman k-domination and Roman domination numbers in graphs
- Approximation Algorithms Inspired by Kernelization Methods
- The differential and the roman domination number of a graph
- An Improved Approximation Bound for Spanning Star Forest and Color Saving
- Domination in graphs with minimum degree two
- Extremal Problems for Roman Domination
- Approximating the Spanning Star Forest Problem and Its Application to Genomic Sequence Alignment
- ROMAN k-DOMINATION IN GRAPHS
- An upper bound for thek-domination number of a graph
- Enclaveless sets and MK-Systems
- Paths, Stars and the Number Three
- Total Domination in Graphs
- R<scp>OMAN DOMINATION</scp>: a parameterized perspective†
- On the Equivalence between the Primal-Dual Schema and the Local Ratio Technique
- COMPLETENESS IN DIFFERENTIAL APPROXIMATION CLASSES
- SOFSEM 2006: Theory and Practice of Computer Science
This page was built for publication: Data reductions and combinatorial bounds for improved approximation algorithms
