Hanno Lefmann (*)
Institut für Informatik II
Universit\"at Dortmund
Terça-feira, 28 de outubro de 1997, 14:00
Sala 259, Bloco A, IME-USP
Abstract: Given a graph $G = (V, E)$ with vertex set $V$ and edge-set $E$, an independent set in $G$ is a subset of the vertex set which contains no edges. An important parameter is the independence number of a graph $G$, defined as the largest size of an independent set in $G$. However, computing this number is in general a hard problem, unless $P = NP$. We discuss in this talk some inapproximability results as well as efficient algorithms for approximating the independence number of graphs and hypergraphs.
Here, we will focus on some cases, which arise from combinatorial questions concerning the existence of large structures with certain properties. For example the following problem can easily be formulated in terms of the independence number: in the $n \times n$-grid determine the maximum number of points with mutual distinct distances.
(*) Visita ao IME-USP financiada pelo projeto ``Combinatória e Teoria da Computação,'' um projeto dentro do programa ProInter da USP.