Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

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)
What and Who
Title:Enumeration of ({0}, {2})-Dominations
Speaker:Oussam Mustapha Larkem
coming from:University of Lorraine – France
Speakers Bio:Master of Science
Event Type:PhD Application Talk
Visibility:D1, D2, D3, D4, D5, SWS, RG1, MMCI
We use this to send out email in the morning.
Level:Public Audience
Date, Time and Location
Date:Monday, 10 February 2014
Duration:90 Minutes
Building:E1 4
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
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Created:Aaron Alsancak/MPI-INF, 02/06/2014 10:41 AM Last modified:Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM
  • Aaron Alsancak, 02/06/2014 10:50 AM
  • Aaron Alsancak, 02/06/2014 10:48 AM -- Created document.