direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

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.

Christian Komusiewicz
TEL 512

Back to the research colloquium site.

Zusatzinformationen / Extras