Premium
Steiner type problems for digraphs that are locally semicomplete or extended semicomplete
Author(s) -
BangJensen Jørgen,
Gutin Gregory,
Yeo Anders
Publication year - 2003
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.10140
Subject(s) - digraph , mathematics , combinatorics , graph , polynomial , directed graph , discrete mathematics , mathematical analysis
We consider the following three problems: (P1) Let D be a strong digraph and let X be a non‐empty subset of its vertices. Find a strong subdigraph D ′ of D which contains all vertices of X and has as few arcs as possible. This problem is also known under the name the directed Steiner problem. (P2) Let D be a strong digraph with real‐valued costs on the vertices. Find a strong subdigraph of D of minimum cost. (P3) Let D be a strong digraph with real‐valued costs on the vertices. Find a cycle of minimum cost in D . All three problems are NP‐hard for general digraphs. The second problem generalizes the problem of finding a smallest strong subdigraph (measured in the number of vertices) which covers a given non‐empty set X of vertices. We describe polynomial algorithms for the problems (P1) and (P2) in the case when D is either locally semicomplete or extended semicomplete and for (P3) in the case of locally semicomplete digraphs. A polynomial algorithm for (P3) in the case of extended semicomplete digraphs was given by Bang‐Jensen et al., 2002. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 193–207, 2003