Dual parameterization and parameterized approximability of subset graph problems

DOI10.1051/RO/2016018MaRDI QIDQ2969972zbMATH OpenOpenAlexFDO

Authors Édouard Bonnet, Vangelis Th. Paschos

Publication date 24 March 2017

Published in RAIRO - Operations Research (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/2d9a6cec33bc8c0af3a92fa6e3c3d8c2e0151667

zbMATH Keywords

polynomial approximationsubset problemsparameterized approximation

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Parameterized (in)approximability of subset problems
• Parameterized approximation of dominating set problems
• On the parameterized complexity of approximating dominating set
• On the Parameterized Complexity of Approximating Dominating Set
• On Parameterized Approximability

Cites work

• scientific article; zbMATH DE number 2086260 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 1953201 (Why is no real title available?)
• Approximating the minimum maximal independence number
• Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness
• Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
• Linear degree extractors and the inapproximability of max clique and chromatic number
• On Parameterized Approximability
• On an approximation measure founded on the links between optimization and polynomial approximation theory
• On dependent randomized rounding algorithms
• Parameterized Approximation Problems
• Parameterized complexity of finding subgraphs with hereditary properties.
• Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
• The Turing way to parameterized complexity

Cited in

(6)

• Dual parameterization of weighted coloring
• Dual parameterization of weighted coloring
• An efficient graph technique based dual-type algorithm for NMNF problems with large capacity constraints
• Parameterized (in)approximability of subset problems
• Sublinear-time algorithms for approximating graph parameters
• Parameterized and approximation complexity of the detection pair problem in graphs

This page was built for publication: Dual parameterization and parameterized approximability of subset graph problems

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