Some APX-completeness results for cubic graphs
type: Item
instance of: scholarly article
title: Some APX-completeness results for cubic graphs
zbMATH Open document ID: 0939.68052
DOI: 10.1016/S0304-3975(98)00158-3
published in: Theoretical Computer Science
publication date: 2000-06-04T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1454557
zbMATH Keywords: computational complexity
zbMATH Keywords: NP-hard optimization problems
zbMATH Keywords: approximation
zbMATH Keywords: APX-completeness
zbMATH Keywords: cubic graphs
Wikidata QID: Q56032472
author: Paola Alimonti
author: Viggo Kann
MaRDI profile type: Publication
cites work: The complexity and approximability of finding maximum feasible subsystems of linear relations
cites work: Q4230321
cites work: Q4258216
cites work: Q4252727
cites work: On approximation properties of the independent set problem for low degree graphs
cites work: Q3128896
cites work: Structure in Approximation Classes
cites work: Completeness in approximation classes
cites work: Q4198056
cites work: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
cites work: Approximating the minimum maximal independence number
cites work: Maximum bounded 3-dimensional matching is MAX SNP-complete
cites work: Q4764626
cites work: On the hardness of approximating minimization problems
cites work: Optimization, approximation, and complexity classes
cites work: Q3221403
cites work: Greedy approximations of independent sets in low degree graphs
full work available at URL: s0304-3975(98)00158-3
OpenAlex ID: W2012391569
DBLP publication ID: journals/tcs/AlimontiK00
description: scientific article; zbMATH DE number 1454557