Kernelization algorithms for some link stream editing problems
Speaker:
Pierre MEYER, Ecole Normale Supérieure de Lyon
Date and Time:
Tuesday, October 10, 2017 - 1:55pm to 2:20pm
Location:
Fields Institute, Room 230
Abstract:
Given a link stream L and a positive integer k, the Sparse Split Link Stream Editing problem asks to transform L into a link stream which consists of a clique plus isolated vertices during an interval and is linkless outside that interval, by performing at most k edge insertions and deletions.
We present a kernelization algorithm for the sparse split link stream editing problem by adapting an algorithm for graphs (by Falk Hüffner, Christian Komusiewicz, and André Nichterlein). Further, we give ideas on how to similary adapt kernelization algorithms from graph problems to their link stream counterparts.
This is a joint work with Binh-Minh Bui-Xuan and Clémence Magnien.