Inhalt des Dokuments
Finding Consistent Paths Across Two Networks
Dr. Christian Komusiewicz (TU Berlin)
We study the following problem: Given a directed graph D=(V,A) and an undirected graph G=(V,E) find a directed path P of length at least one in D such that G[V(P)] is connected; we call such paths consistent. We study three different variants of this problem: deciding whether there is a any consistent path, finding a longest consistent path, and finding a shortest consistent path.
We show for example that the decision version of the problem is NP-hard even if G is a tree with three vertices of degree at least three. We also study the parameterized complexity of the problem with respect to the parameter path length k and show that the problem is W[1]-hard for k even if G is a tree and D is acyclic.
Date | Speaker | Location | Language |
---|---|---|---|
04.12.2014 16:15 | Christian Komusiewicz | TEL 512 | english |