Electronic Colloquium on Computational Complexity
Login | Register | Classic Style

Reports tagged with independence number:
TR03-052 | 13th May 2003
Stanislav Busygin, Dmitrii V. Pasechnik

On ~chi(G)-alpha(G)>0 gap recognition and alpha(G)-upper bounds

We show that for a graph G it is NP-hard to decide whether its independence number alpha(G) equals its clique partition number ~chi(G) even when some minimum clique partition of G is given. This implies that any alpha(G)-upper bound provably better than ~chi(G) is NP-hard to compute.

To establish this ... more >>>

TR03-077 | 4th September 2003
Till Tantau

Logspace Optimisation Problems and their Approximation Properties

This paper introduces logspace optimisation problems as
analogues of the well-studied polynomial-time optimisation
problems. Similarly to them, logspace
optimisation problems can have vastly different approximation
properties, even though the underlying existence and budget problems
have the same computational complexity. Numerous natural problems
are presented that exhibit such a varying ... more >>>

ISSN 1433-8092 | Imprint