Dual parameterization and parameterized approximability of subset graph problems

DOI10.1051/ro/2016018zbMath1362.68290OpenAlexW2319388310MaRDI QIDQ2969972

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

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)

Related Items (2)

Dual parameterization of Weighted Coloring ⋮ Dual parameterization of weighted coloring

Cites Work

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

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