𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On approximation problems related to the independent set and vertex cover problems

✍ Scribed by R. Bar-Yehuda; S. Moran

Publisher
Elsevier Science
Year
1984
Tongue
English
Weight
549 KB
Volume
9
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On the nonseparating independent set pro
On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
✍ Shuichi Ueno; Yoji Kajitani; Shin'ya Gotoh πŸ“‚ Article πŸ“… 1988 πŸ› Elsevier Science 🌐 English βš– 350 KB

This paper shows that both the nonseparating independent set problem and feedback set problem can be solved in polynomial time for graphs with no vertex degree exceeding 3 by reducing the problems to the matroid parity problem.

On the approximability of clique and rel
On the approximability of clique and related maximization problems
✍ Aravind Srinivasan πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 247 KB

We consider approximations of the form n 1Γ€oΓ°1Þ for the Maximum Clique problem, where n is the number of vertices in the input graph and where the ''oΓ°1Þ'' term goes to zero as n increases. We show that sufficiently strong negative results for such problems, which we call strong inapproximability re

On easy and hard hereditary classes of g
On easy and hard hereditary classes of graphs with respect to the independent set problem
✍ Vladimir E. Alekseev πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 162 KB

In this paper we introduce the concept of a boundary class, which is a helpful tool for classiΓΏcation of hereditary classes of graphs according to the complexity of the independent set problem. It is shown that in a class X deΓΏned by a ΓΏnite set of forbidden induced subgraphs, the problem is NP-hard