EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

On Variants of the Group Steiner Tree Problem: Considering Connected Groups of Vertices or Edges

Christoph Geis, Sven O. Krumke

Networks · 13.11.2026

DOI: 10.1002/net.70086 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Networks, online erschienen am 13.11.2026. Verfasst von Christoph Geis und 1 weiteren Autor:innen. Die Arbeit nennt 15 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The min‐cost group Steiner tree problem ( GSTP ) is a well‐known problem in graph theory, not only being NP‐complete but also not admitting a constant‐factor approximation even under strong restrictions. Given a graph and groups of vertices in , the problem GSTP asks for a minimum‐cost subtree of that contains at least one vertex from each group. In this paper, we address two variants of the GSTP : First, we consider groups of edges rather than vertices. Perhaps surprisingly, this problem is not equivalent to the vertex group variant. For instance, in the edge version it is even NP‐complete to decide whether there exists a feasible solution. Next, we consider the restriction that all of the (vertex or edge) groups are connected. We show that these variants can be solved in polynomial time, provided both the treewidth of and the vertex frequency (the number of groups a vertex is contained in) are bounded. However, the problems remain NP‐complete when only one of these parameters is bounded. Furthermore, we give various approximation algorithms for the connected edge GSTP on trees.

Zitieren

APA

Geis, C., & Krumke, S. O. (2026). On Variants of the Group Steiner Tree Problem: Considering Connected Groups of Vertices or Edges. Networks. https://doi.org/10.1002/net.70086

Vancouver

Geis C, Krumke SO. On Variants of the Group Steiner Tree Problem: Considering Connected Groups of Vertices or Edges. Networks. 2026. doi:10.1002/net.70086

BibTeX
@article{Geis2026,
  author = {Geis, Christoph and Krumke, Sven O.},
  title = {On Variants of the Group Steiner Tree Problem: Considering Connected Groups of Vertices or Edges},
  journal = {Networks},
  year = {2026},
  doi = {10.1002/net.70086}
}
Kostenlos starten →