Mechanism for Building Approximation Edge Minimum Spanning Tree Using Portals on Input Edges


The KIPS Transactions:PartA, Vol. 16, No. 6, pp. 509-518, Dec. 2009
10.3745/KIPSTA.2009.16.6.509,   PDF Download:

Abstract

In this paper, a mechanism that produces an approximation edges minimum spanning tree swiftly using virtual nodes called portals dividing given edges into same distance sub-edges. The approximation edges minimum spanning tree can be used in many useful areas as connecting communication lines, road networks and railroad systems. For 3000 random input edges, when portal distance is 0.3, tree building time decreased 29.74% while the length of the produced tree increased 1.8% comparing with optimal edge minimum spanning tree in our experiment. When portal distance is 0.75, tree building time decreased 39.96% while the tree length increased 2.96%. The result shows this mechanism might be well applied to the applications that may allow a little length overhead, but should produce an edge connecting tree in short time. And the proposed mechanism can produce an approximation edge minimum spanning tree focusing on tree length or on building time to meet user requests by adjusting portal distance or portal discard ratio as parameter.


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]
I. B. Kim and S. I. Kim, "Mechanism for Building Approximation Edge Minimum Spanning Tree Using Portals on Input Edges," The KIPS Transactions:PartA, vol. 16, no. 6, pp. 509-518, 2009. DOI: 10.3745/KIPSTA.2009.16.6.509.

[ACM Style]
In Bum Kim and Soo In Kim. 2009. Mechanism for Building Approximation Edge Minimum Spanning Tree Using Portals on Input Edges. The KIPS Transactions:PartA, 16, 6, (2009), 509-518. DOI: 10.3745/KIPSTA.2009.16.6.509.