max planck institut
informatik

# MPI-INF or MPI-SWS or Local Campus Event Calendar

 << Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
Title: Enumeration of ({0}, {2})-Dominations Oussam Mustapha Larkem University of Lorraine β France Master of Science PhD Application Talk D1, D2, D3, D4, D5, SWS, RG1, MMCIWe use this to send out email in the morning. Public Audience English
Date: Monday, 10 February 2014 10:50 90 Minutes SaarbrΓΌcken E1 4 024
 Let π and π be two subsets of non-negative integers, a vertex subset S β V of an undirected graph G(V, E) is called a (π, π)-dominating set of G if |N(v) β© S| β π for v β S and |N(v) β© S| βπ for all v β V \S. The talk will begin with a quick introduction to branching algorithms and then will cover a selected result from the master thesis, namely the enumeration of all ({0}, {2})-dominations in time O*(1.2546n) and a lower bound of Ξ©(1.2009n), by giving a sequence of graphs that contains (asymptotically) that many ({0}, {2})-dominations. In our case some graph invariants that, if small, allow a good running time, can not be both high but expressing them exactly one in function of the others turns out to be too complicated, so here we use computer aided analysis of subgraphs of bounded size to obtain the low running time stated above. If the time permits it, a second enumeration result being an algorithm enumerating a generalization of Independent Set i.e. ({0,1},β)-dominations will be presented.
Video Broadcast: No
• Aaron Alsancak, 02/06/2014 10:50 AM
• Aaron Alsancak, 02/06/2014 10:48 AM -- Created document.