Master of Science

AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, MMCI   Info

Public Audience

English

90 Minutes

Saarbrücken

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.

--email hidden

passcode not visible

logged in users only