TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 02.11.2017


Page Content

to Navigation

Verbesserung einer Greedy-Heuristik für Dominating Set: Dynamische Probleme und Turbo-Charging

Marcelo Garlet Millani (TU Berlin)


We introduce a subclass of directed acyclic graphs (DAGs) which we call funnels. The purpose of this class is to keep some of the structural simplicity of directed trees without losing too much of the expressiveness of DAGs.

We first analyze this class from a graph-theoretical perspective, proving certain structural properties of funnels. Then, we apply the graph class to concrete computational problems, checking whether they become algorithmically easier (i.e., polynomial-time solvable) when the input is restricted to be a funnel. Finally, we also treat the class from a parameterized complexity point of view, defining four distance measures to funnel. For the k-Linkage problem (also known as Vertex-Disjoint Paths), we obtain positive parameterized results, with the problem becoming solvable in quadratic time when the arc-deletion distance to a funnel of the input DAG is a constant.

We conclude with an experimental evaluation where we analyze the practical usefulness of some of the algorithms described.



Marcelo Garlet Millani
TEL 512

Back to the research colloquium site.

To top


Quick Access

Schnellnavigation zur Seite über Nummerneingabe