|
|
||
|
IMADA - Department of Mathematics and Computer Science |
|
The talk introduces a graph edge-modification problem called (D, S)-Editing,
where the goal is to transform a given graph into a disjoint union of two
graphs, one from D and the other from S, using as few edge insertions and
deletions as possible. The problem generalizes the Clique Editing problem, where
D consists of all cliques and S consists of all independent sets. Similarly
to Clique Editing, we require the class D to be dense and S to be sparse. In
the first part of the talk I will discuss several approaches to these
density requirements - our aim is to restrict the classes as little as
possible while having a separation between the classes. In the second part I
will present our results on (D, S)-editing from parameterized complexity,
approximation, and online perspective. Host: Kim Skak Larsen SDU HOME | IMADA HOME | Previous Page Daniel Merkle |