On approximation properties of the independent set problem for low degree graphs

DOI10.1007/s002240000113zbMath0916.68109OpenAlexW42852446MaRDI QIDQ1281930

Piotr Berman, Toshihiro Fujito

Publication date: 22 March 1999

Published in: Theory of Computing Systems (Search for Journal in Brave)

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

zbMATH Keywords

independent set problembounded node degree graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (23)

Approximation algorithms for the maximum vertex coverage problem on bounded degree graphs ⋮ Complexity of approximating bounded variants of optimization problems ⋮ Minimizing the tracking error of cardinality constrained portfolios ⋮ Maximum 0-1 timed matching on temporal graphs ⋮ A primal-dual approximation algorithm for \textsc{minsat} ⋮ Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs ⋮ Mixed hypergraphs with bounded degree: Edge-coloring of mixed multigraphs. ⋮ A probabilistic algorithm for vertex cover ⋮ Approximation algorithms for maximum independent set of pseudo-disks ⋮ Approximation Algorithm for the Distance-3 Independent Set Problem on Cubic Graphs ⋮ Recoverable Values for Independent Sets ⋮ Crown reductions for the minimum weighted vertex cover problem ⋮ Packing triangles in low degree graphs and indifference graphs ⋮ On approximating minimum vertex cover for graphs with perfect matching ⋮ A \((1.4+\epsilon)\)-approximation algorithm for the 2-\textsc{Max-Duo} problem ⋮ Simple and local independent set approximation ⋮ Algorithms and Complexity of Signed, Minus, and Majority Domination ⋮ Independent sets in bounded-degree hypergraphs ⋮ Approximation algorithms for the weighted independent set problem in sparse graphs ⋮ Some APX-completeness results for cubic graphs ⋮ On the Independence Number of Graphs with Maximum Degree 3 ⋮ Large independent sets in random regular graphs ⋮ A (1.4 + epsilon)-Approximation Algorithm for the 2-Max-Duo Problem

This page was built for publication: On approximation properties of the independent set problem for low degree graphs