direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Es gibt keine deutsche Übersetzung dieser Webseite.

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.

 

 

Date
Speaker
Location
Language
02.11.2017
16:15
Marcelo Garlet Millani
TEL 512
English

Back to the research colloquium site.

Nach oben

Zusatzinformationen / Extras