Mathematical Foundations of Computer Science 2004

DOI10.1007/b99679zbMath1096.68061OpenAlexW2488008928MaRDI QIDQ5311102

Janka Chlebíková, Miroslav Chlebík

Publication date: 22 August 2005

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/b99679

zbMATH Keywords

approximation algorithmsatisfiabilityperfect matchingcombinatorial optimization problemsvertex coverinapproximabilityNemhauser-Trotter Theorem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (4)

On the complexity of minimum \(q\)-domination partization problems ⋮ Affine reductions for LPs and SDPs ⋮ Approximation Algorithms for CSPs ⋮ On approximating minimum vertex cover for graphs with perfect matching

This page was built for publication: Mathematical Foundations of Computer Science 2004