Constrained Steiner trees in Halin graphs

Issue		RAIRO Oper. Res. Volume 37, Number 3, July-September 2003


Page(s)		179 - 194
DOI		10.1051/ro:2003020

RAIRO Oper. Res. 37 (2003) 179-194
DOI: 10.1051/ro:2003020

Constrained Steiner trees in Halin graphs

Guangting Chen¹ and Rainer E. Burkard²

¹ The School of Science, Hangzhou Institute of Electronics Engineering, Hangzhou 310037, P.R. China; gtchen@sci.hziee.edu.cn.
² Technische Universität Graz, Institut für Mathematik, Steyrergasse 30, A-8010 Graz, Austria; burkard@tugraz.at.

(Received February 28, 2003.)

Abstract
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.

Key words: Steiner trees, Halin graph, approximation scheme.

© EDP Sciences 2003

What is OpenURL?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.

If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.