On the max min vertex cover problem
type: Item
instance of: scholarly article
title: On the max min vertex cover problem
zbMATH Open document ID: 1321.05177
author: Nicolas Boria
author: Vangelis Th. Paschos
author: F. Della Croce
published in: Discrete Applied Mathematics
publication date: 2015-09-30T00:00:00Z
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 6487384
zbMATH Keywords: max min vertex cover
zbMATH Keywords: min independent dominating set
zbMATH Keywords: polynomial approximation
zbMATH Keywords: inapproximability
zbMATH Keywords: parametric complexity
MaRDI profile type: Publication
full work available at URL: j.dam.2014.06.001
OpenAlex ID: W1968988491
cites work: On Turan's theorem for sparse graphs
cites work: Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
cites work: Linear time algorithms for NP-hard problems restricted to partial k- trees
cites work: Q4258216
cites work: Q4734761
cites work: Fast algorithms for min independent dominating set
cites work: Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
cites work: Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
cites work: On Parameterized Approximability
cites work: Q4511217
cites work: Q4393480
cites work: Parameterized Approximation Problems
cites work: New Results on Polynomial Inapproximability and Fixed Parameter Approximability of edge dominating set
cites work: Domination, independent domination, and duality in strongly chordal graphs
cites work: Parameterized Approximation via Fidelity Preserving Transformations
cites work: Exponential Time Algorithms for the Minimum Dominating Set Problem on Some Graph Classes
cites work: A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set in Graphs
cites work: Approximating the minimum maximal independence number
cites work: Low-degree Graph Partitioning via Local Search with Applications to Constraint Satisfaction, Max Cut, and Coloring
cites work: The approximation of maximum subgraph problems
cites work: Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
cites work: Linear degree extractors and the inapproximability of max clique and chromatic number
DOI: 10.1016/J.DAM.2014.06.001
description: scientific article; zbMATH DE number 6487384