Mechanism for Connecting Input Edges Using Steiner Tree


The KIPS Transactions:PartA, Vol. 17, No. 5, pp. 213-220, Oct. 2010
10.3745/KIPSTA.2010.17.5.213,   PDF Download:

Abstract

In this paper, a mechanism connecting all input edges with minimum length through Steiner tree is proposed. Edges are convertible into communication lines, road, railroads or trace of moving object. Proposed mechanism could be applied to connect these edges with minimum cost. In our experiments where input edge number and maximum connections per edge are used as input parameters, our mechanism made connection length decrease average 6.8%, while building time for a connecting solution increase average192.0% comparing with the method using minimum spanning tree. The result shows our mechanism might be well applied to the applications where connecting cost is more important than building time for a connecting solution.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
J. M. Kim and I. B. Kim, "Mechanism for Connecting Input Edges Using Steiner Tree," The KIPS Transactions:PartA, vol. 17, no. 5, pp. 213-220, 2010. DOI: 10.3745/KIPSTA.2010.17.5.213.

[ACM Style]
Joon Mo Kim and In Bum Kim. 2010. Mechanism for Connecting Input Edges Using Steiner Tree. The KIPS Transactions:PartA, 17, 5, (2010), 213-220. DOI: 10.3745/KIPSTA.2010.17.5.213.