Distributed Processing and On Minimum-Cost Rectilinear Steiner Distance-Preserving Tree


The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 3, No. 7, pp. 1707-1718, Dec. 1996
10.3745/KIPSTE.1996.3.7.1707,   PDF Download:

Abstract

Given a signal net N=s,1,...,n to be the set of nodes, with an the source and remaining nodes sinks, an MRDPT (minimum-cost rectilinear Steiner distance-preserving tree) has the property that the length of every source to sink path is equal to the rectilinear distance between the source and sink. The minimum-cost rectilinear Steiner distance-preserving three minimizes the total wore length while maintaining minimal source to sink length. Recently, some heuristic algorithm have been proposed for the problem of finding the MRDPT. In this paper, we investigate an optimal structure on the MRDPT and present a theoretical breakthrough which shows that the min-cost flow formulation leads to an efficient o((n2 log m)2) time algorithm. A more practical extension is also investigated along with interesting open problems.


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]
C. J. Dong, "Distributed Processing and On Minimum-Cost Rectilinear Steiner Distance-Preserving Tree," The Transactions of the Korea Information Processing Society (1994 ~ 2000), vol. 3, no. 7, pp. 1707-1718, 1996. DOI: 10.3745/KIPSTE.1996.3.7.1707.

[ACM Style]
Cho Jun Dong. 1996. Distributed Processing and On Minimum-Cost Rectilinear Steiner Distance-Preserving Tree. The Transactions of the Korea Information Processing Society (1994 ~ 2000), 3, 7, (1996), 1707-1718. DOI: 10.3745/KIPSTE.1996.3.7.1707.