Keyword: Steiner problem

Found 72 papers in total
Computing Optimal Steiner Trees in Polynomial Space
Computing Optimal Steiner Trees in Polynomial Space
2013,
Given an n ‐node edge‐weighted graph and a subset of k terminal nodes,...
A branch‐and‐cut algorithm for the Steiner tree problem with delays
A branch‐and‐cut algorithm for the Steiner tree problem with delays
2012,
In this paper, we investigate the Steiner tree problem with delays, which is a...
Steiner Minimal Trees with One Polygonal Obstacle
Steiner Minimal Trees with One Polygonal Obstacle
2001,
In this paper we study the Steiner minimal tree T problem for a point set Z with...
Minimum Weight Convex Steiner Partitions
Minimum Weight Convex Steiner Partitions
2011,
New tight bounds are presented on the minimum length of planar straight line graphs...
Simple and fast reoptimizations for the Steiner tree problem
Simple and fast reoptimizations for the Steiner tree problem
2009,
We address reoptimization issues for the Steiner tree problem. We assume that an...
On the Steiner 2-edge connected subgraph polytope
On the Steiner 2-edge connected subgraph polytope
2008,
In this paper, we study the Steiner 2–edge connected subgraph polytope. We...
Reduction tests for the prize-collecting Steiner problem
Reduction tests for the prize-collecting Steiner problem
2006,
This article introduces a proper redifinition of the concept of bottleneck Steiner...
Variations of the prize-collecting Steiner tree problem
Variations of the prize-collecting Steiner tree problem
2006,
The prize-collecting Steiner tree problem is well known to be NP-hard. We consider...
Steiner trees and 3-D macromolecular conformation
Steiner trees and 3-D macromolecular conformation
2004,
One of the key issues in biochemistry and molecular modelling is the determination of...
The rectilinear Steiner ratio
The rectilinear Steiner ratio
2005,
The rectilinear Steiner ratio was shown to be 3/2 by Hwang. We use continuity and...
Approximation algorithms for a capacitated network design problem
Approximation algorithms for a capacitated network design problem
2003,
We study a capacitated network design problem with applications in local access...
Constrained Steiner trees in Halin graphs
Constrained Steiner trees in Halin graphs
2003,
In this paper, we study the problem of computing a minimum cost Steiner tree subject...
Rectilinear group Steiner trees and applications in very large scale integration design
Rectilinear group Steiner trees and applications in very large scale integration design
2003,
Given a set of disjoint groups of points in the plane, the rectilinear group Steiner...
A greedy algorithm for multicut and integral multiflow in rooted trees
A greedy algorithm for multicut and integral multiflow in rooted trees
2003,
We present an O(min(Kn,n 2 )) algorithm to solve the maximum integral multiflow and...
A bicriterion Steiner tree problem on graph
A bicriterion Steiner tree problem on graph
2003,
This paper presents a formulation of bicriterion Steiner tree problem which is stated...
Network flow models for designing diameter-constrained minimum-spanning and Steiner trees
Network flow models for designing diameter-constrained minimum-spanning and Steiner trees
2003,
We formulate and computationally test several models for the Diameter-Constrained...
A hybrid GRASP with perturbations for the Steiner problem in graphs
A hybrid GRASP with perturbations for the Steiner problem in graphs
2002,
We propose and describe a hybrid GRASP with weight perturbations and adaptive...
A branch-and-price algorithm for switch-box routing
A branch-and-price algorithm for switch-box routing
2002,
Routing in VLSI design concerns the wiring of a chip after the logical modules have...
Local search with perturbations for the prize-collecting Steiner tree problem in graphs
Local search with perturbations for the prize-collecting Steiner tree problem in graphs
2001,
Given an undirected graph with prizes associated with its nodes and weights associated...
Approximation algorithms for degree-constrained minimum-cost network-design problems
Approximation algorithms for degree-constrained minimum-cost network-design problems
2001,
We study network-design problems with two different design objectives: the total cost...
Steiner minimal trees with one polygonal obstacle
Steiner minimal trees with one polygonal obstacle
2001,
In this paper we study the Steiner minimal tree T problem for a point set Z with...
Tabu search for the Steiner problem in graphs
Tabu search for the Steiner problem in graphs
2000,
Given an undirected graph with weights associated with its edges, the Steiner tree...
Approximating Steiner trees in graphs with restricted weights
Approximating Steiner trees in graphs with restricted weights
1998,
We analyze the approximation ratio for the average distance heuristic for the Steiner...
The pilot method: A strategy for heuristic repetition with application to the Steiner problem in graphs
The pilot method: A strategy for heuristic repetition with application to the Steiner problem in graphs
1999,
As a metaheuristic to obtain solutions of enhanced quality, we formulate the so-called...
Papers per page: