Currently displaying 1 – 6 of 6

Showing per page

Order by Relevance | Title | Year of publication

Constrained Steiner trees in Halin graphs

Guangting ChenRainer 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 ChenRainer 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.

Bottleneck capacity expansion problems with general budget constraints

Rainer E. BurkardBettina KlinzJianzhong Zhang — 2001

RAIRO - Operations Research - Recherche Opérationnelle

This paper presents a unified approach for bottleneck capacity expansion problems. In the bottleneck capacity expansion problem, BCEP, we are given a finite ground set E , a family of feasible subsets of E and a nonnegative real capacity c ^ e for all e E . Moreover, we are given monotone increasing cost functions f e for increasing the capacity of the elements e E as well as a budget B . The task is to determine new capacities c e c ^ e such that the objective function given by max F min e F c e is maximized under the side constraint...

Bottleneck Capacity Expansion Problems with General Budget Constraints

Rainer E. BurkardBettina KlinzJianzhong Zhang — 2010

RAIRO - Operations Research

This paper presents a unified approach for bottleneck capacity expansion problems. In the bottleneck capacity expansion problem, BCEP, we are given a finite ground set , a family of feasible subsets of and a nonnegative real capacity ĉ for all . Moreover, we are given monotone increasing cost functions for increasing the capacity of the elements as well as a budget . The task is to determine new capacities c ≥ ĉ such that the objective function given by maxminc is...

Page 1

Download Results (CSV)