The search session has expired. Please query the service again.

Currently displaying 1 – 2 of 2

Showing per page

Order by Relevance | Title | Year of publication

Constrained Steiner trees in Halin graphs

Guangting Chen;  Rainer E. Burkard — 2003

RAIRO - Operations Research - Recherche Opérationnelle

In this paper, we study the problem of computing a minimum cost Steiner tree subject to a weight constraint in a Halin graph where each edge has a nonnegative integer cost and a nonnegative integer weight. We prove the NP-hardness of this problem and present a fully polynomial time approximation scheme for this NP-hard problem.

Constrained Steiner trees in Halin graphs

Guangting Chen;  Rainer E. Burkard — 2010

RAIRO - Operations Research

In this paper, we study the problem of computing a minimum cost Steiner tree subject to a weight constraint in a Halin graph where each edge has a nonnegative integer cost and a nonnegative integer weight. We prove the NP-hardness of this problem and present a fully polynomial time approximation scheme for this NP-hard problem.

Page 1

Download Results (CSV)