An algorithm for the steiner problem in graphs | Zendy

Beasley J. E. | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

An algorithm for the steiner problem in graphs

Author(s) -

Beasley J. E.

Publication year - 1984

Publication title -

networks

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.977

H-Index - 64

eISSN - 1097-0037

pISSN - 0028-3045

DOI - 10.1002/net.3230140112

Subject(s) - steiner tree problem , mathematics , combinatorics , undirected graph , maximum cut , connection (principal bundle) , graph , integer programming , reduction (mathematics) , discrete mathematics , algorithm , geometry

In this paper we consider the Steiner problem in graphs. This is the problem of connecting together, at minimum cost, a number of vertices in an undirected graph. We present two lower bounds for the problem, these bounds being based on two separate Lagrangian relaxations of a zero‐one integer programming formulation of the problem. Problem reduction tests derived from both the original problem and the Lagrangian relaxations are given. Incorporating the bounds and the reduction tests into a tree search procedure enables us to solve problems involving the connection of up to 50 vertices in a graph with 200 undirected arcs and 100 vertices.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research