TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 09.02.2012


Page Content

to Navigation

Scheduling and Colorful Independent Sets

Mathias Weller (TU Berlin)

The Independent Set problem is a widely known NP-hard problem with applications in multiple fields. In this work, we consider Independent Set in the context of scheduling, in particular, we consider 2-union graphs, that is, edge-wise unions of two interval graphs on the same vertex set, and strip graphs (a subclass of 2-union graphs where one of the interval graphs consists of disjoint cliques).

Assuming the input is given as two interval graphs G_1 and G_2 , we give a polynomial-size kernel for the parameter max_i{number of maximal cliques in G_i}. For strip graphs, we show nonexistance of polynomial kernels for a variety of parameters. However, restricting the input to unit intervals allows us to show a kernel containing at most O(k · ω) vertices, where k is the solution size and ω is the size of the largest maximal clique in the input.

09.02.2012 16:15
Mathias Weller
FR 6510

* Language is depending on the audience.

Back to the research colloquium site.


Quick Access

Schnellnavigation zur Seite über Nummerneingabe