Halldórsson, Magnús M. Approximations of weighted independent set and hereditary subset problems. (English) Zbl 0945.68146 Asano, Takao (ed.) et al., Computing and combinatorics. 5th annual international conference. COCOON ’99, Tokyo, Japan, July 26-28, 1999. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1627, 261-270 (1999). Summary: The focus of this study is to clarify the approximability of the important versions of the maximum independent set problem, and to apply, where possible, the technique to related hereditary subgraph and subset problem. We report improved performance ratios for the independent set problem in weighted general graphs, weighted bounded-degree graphs, and in sparse graphs. Other problems with better than previously reported ratios include weighted set packing, longest subsequence, maximum independent sequence, and independent set in hypergraphs.For the entire collection see [Zbl 0918.00033]. Cited in 5 Documents MSC: 68R10 Graph theory (including graph drawing) in computer science 68Q25 Analysis of algorithms and problem complexity Keywords:maximum independent set problem PDFBibTeX XMLCite \textit{M. M. Halldórsson}, Lect. Notes Comput. Sci. 1627, 261--270 (1999; Zbl 0945.68146)