×

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].

MSC:

68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite