An Exact Algorithm for Steiner Tree Problem on Graphs

The paper presents a new original algorithm for solving Steiner tree problem on graph. The algorithm is simple and intended for solving problems with relatively low dimensions. It is based on use of existing open source software for solving integer linear programming problems. The algorithm is teste...

Full description

Saved in:
Bibliographic Details
Published in:International journal of computers, communications & control communications & control, 2006-03, Vol.1 (1), p.41
Main Authors: Stanojevic, Milan, Vujoševic, Mirko
Format: Article
Language:English
Subjects:
Algorithms
Graphs
Integer programming
Linear programming
Problem solving
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The paper presents a new original algorithm for solving Steiner tree problem on graph. The algorithm is simple and intended for solving problems with relatively low dimensions. It is based on use of existing open source software for solving integer linear programming problems. The algorithm is tested and shown very efficient for different randomly generated problems on graphs of up to 50 nodes, up to 10 terminals and average node degree 7.
ISSN:1841-9836
1841-9844
DOI:10.15837/ijccc.2006.1.2271