Dual parameterization and parameterized approximability of subset graph problems

DOI10.1051/RO/2016018zbMATH Open1362.68290OpenAlexW2319388310MaRDI QIDQ2969972FDOQ2969972

Vangelis Th. Paschos, Édouard Bonnet

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

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

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)

Cites Work

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

Cited In (5)

• 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
• 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)