Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Node Cover:
TR98-065 | 6th November 1998
Piotr Berman, Marek Karpinski

On Some Tighter Inapproximability Results, Further Improvements

Improved inaproximability results are given, including the
best up to date explicit approximation thresholds for bounded
occurence satisfiability problems, like MAX-2SAT and E2-LIN-2,
and problems in bounded degree graphs, like MIS, Node Cover
and MAX CUT. We prove also for the first time inapproximability
more >>>

TR01-042 | 31st May 2001
Marek Karpinski

Approximating Bounded Degree Instances of NP-Hard Problems

We present some of the recent results on computational complexity
of approximating bounded degree combinatorial optimization problems. In
particular, we present the best up to now known explicit nonapproximability
bounds on the very small degree optimization problems which are of
particular importance on the intermediate stages ... more >>>

TR03-026 | 20th February 2003
Janka Chlebíková, Miroslav Chlebik

Inapproximability results for bounded variants of optimization problems

We study small degree graph problems such as Maximum Independent Set
and Minimum Node Cover and improve approximation lower bounds for
them and for a number of related problems, like Max-B-Set Packing,
Min-B-Set Cover, Max-Matching in B-uniform 2-regular hypergraphs.
For example, we prove NP-hardness factor of 95/94
more >>>

ISSN 1433-8092 | Imprint