Jochen Rethmann, Hochschule Niederrhein, FB Elektrotechnik und Informatik, Reinarzstraße 49, 47805 Krefeld
Computing Directed Steiner Path Covers for Directed Co-Graphs
SOFSEM 2020 (LNCS 12011, Springer Verlag, pp. 556-565)
Abstract
| We consider the Directed Steiner Path Cover problem on directed co-graphs. Given a directed graph G = (V(G), E(G)) and a set T ⊆ V(G) of so-called terminal vertices, the problem is to find a minimum number of directed vertex-disjoint paths, which contain all terminal vertices and a minimum number of non-terminal vertices (Steiner vertices). The primary minimization criteria is the number of paths. We show how to compute a minimum Steiner path cover for directed co-graphs in linear time. For T = V(G) the algorithm computes a directed Hamiltonian path if such a path exists. |
| Keywords: directed co-graphs, directed Steiner path cover problem |