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

parameterized approximationpolynomial approximationsubset problems

Mathematics Subject Classification ID

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

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

• Approximating the minimum maximal independence number
• Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness
• Complexity and approximation. Combinatorial optimization problems and their approximability properties. Incl. 1 CD-ROM
• Exact algorithms for NP-hard problems: A survey
• Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
• Improved tree decomposition based algorithms for domination-like problems
• Linear degree extractors and the inapproximability of max clique and chromatic number
• On an approximation measure founded on the links between optimization and polynomial approximation theory
• On dependent randomized rounding algorithms
• On Parameterized Approximability
• 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)

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

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)