Maximum bounded 3-dimensional matching is MAX SNP-complete
type: Item
instance of: scholarly article
title: Maximum bounded 3-dimensional matching is MAX SNP-complete
zbMATH Open document ID: 0711.68045
DOI: 10.1016/0020-0190(91)90246-E
author: Viggo Kann
published in: Information Processing Letters
publication date: 1991-01-01T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 03D15
zbMATH DE Number: 4170090
zbMATH Keywords: approximation
zbMATH Keywords: combinatorial problems
zbMATH Keywords: computational complexity
zbMATH Keywords: MAX SNP- complete problems
Wikidata QID: Q57255181
MaRDI profile type: Publication
cites work: On the complexity of approximating the independent set problem
cites work: Q4744064
cites work: Q4198056
full work available at URL: 0020-0190(91)90246-e
OpenAlex ID: W2071016718
DBLP publication ID: journals/ipl/Kann91
Recommended article: Maximum bounded \(H\)-matching is Max SNP-complete
Recommended article: Three-dimensional matching instances are rich in stable matchings
Recommended article: Tight bounds on maximal and maximum matchings
Recommended article: Q4474098
Recommended article: Tighter bounds on the size of a maximum \(P_{3}\)-matching in a cubic graph
Recommended article: Three-Dimensional Stabl Matching Problems
Recommended article: Bounds on maximum \(b\)-matchings
Recommended article: Parameterizing MAX SNP Problems Above Guaranteed Values
Recommended article: Q4729838
Recommended article: Q4953913
description: scientific article; zbMATH DE number 4170090