A Distributed Heuristic Algorithm for the Rectilinear Steiner Minimal Tree Problem

Date

2008-11-01

Author

Cinel, Sertac
Bazlamaçcı, Cüneyt Fehmi

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

182
views

0
downloads

Rectilinear Steiner minimal tree (RSMT) problem finds a minimum length tree that interconnects a given set of points by only horizontal and vertical line segments and by using extra points if necessary. In this paper, to speedup the RSMT construction, two recently developed successful heuristic algorithms, namely rectilinear steiner tree (RST) by Zhou and hatched greedy algorithm (BGA) by Kahng et al., have been used as the basis. Following a slight modification on RST, which led to a nonrecursive and a considerably faster version, a partially parallelized and distributed form of this modified algorithm is proposed. Computational tests using large random data sets have shown the advantage of the modification on RST, and tests conducted on a cluster of workstations have proven the proposed distributed approach to be very promising particularly for large problem instances.

Subject Keywords

Electrical and Electronic Engineering, Software, Computer Graphics and Computer-Aided Design

URI

https://hdl.handle.net/11511/57098

Journal

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS

DOI

https://doi.org/10.1109/tcad.2008.2006085

Collections

Department of Electrical and Electronics Engineering, Article

Suggestions

OpenMETU
Core

Transformation-based metamaterials to eliminate the staircasing error in the finite difference time domain method Ozgun, Ozlem; Kuzuoğlu, Mustafa (Wiley, 2012-07-01) A coordinate transformation technique is introduced for the finite difference time domain method to alleviate the effects of errors introduced by the staircasing approximation of curved geometries that do not conform to a Cartesian grid. An anisotropic metamaterial region, which is adapted to the Cartesian grid and designed by the coordinate transformation technique, is constructed around the curved boundary of the object, and the region occupied between the curved boundary and the inner boundary of the ani...
A quadtree-based adaptively-refined cartesian-grid algorithm for solution of the euler equations Bulkök, Murat; Aksel, Mehmet Haluk; Department of Mechanical Engineering (2005) A Cartesian method for solution of the steady two-dimensional Euler equations is produced. Dynamic data structures are used and both geometric and solution-based adaptations are applied. Solution adaptation is achieved through solution-based gradient information. The finite volume method is used with cell-centered approach. The solution is converged to a steady state by means of an approximate Riemann solver. Local time step is used for convergence acceleration. A multistage time stepping scheme is used to ...
A MAP-Based Approach for Hyperspectral Imagery Super-Resolution IRMAK, Hasan; Akar, Gözde; Yuksel, Seniha Esen (Institute of Electrical and Electronics Engineers (IEEE), 2018-06-01) In this paper, we propose a novel single image Bayesian super-resolution (SR) algorithm where the hyperspectral image (HSI) is the only source of information. The main contribution of the proposed approach is to convert the ill-posed SR reconstruction problem in the spectral domain to a quadratic optimization problem in the abundance map domain. In order to do so, Markov random field based energy minimization approach is proposed and proved that the solution is quadratic. The proposed approach consists of f...
Monte Carlo analysis of ridged waveguides with transformation media Ozgun, Ozlem; Kuzuoğlu, Mustafa (Wiley, 2013-07-01) A computational model is presented for Monte Carlo simulation of waveguides with ridges, by combining the principles of transformation electromagnetics and the finite methods (such as finite element or finite difference methods). The principle idea is to place a transformation medium around the ridge structure, so that a single and easy-to-generate mesh can be used for each realization of the Monte Carlo simulation. Hence, this approach leads to less computational resources. The technique is validated by me...
Discretization of Parametrizable Signal Manifolds Vural, Elif (Institute of Electrical and Electronics Engineers (IEEE), 2011-12-01) Transformation-invariant analysis of signals often requires the computation of the distance from a test pattern to a transformation manifold. In particular, the estimation of the distances between a transformed query signal and several transformation manifolds representing different classes provides essential information for the classification of the signal. In many applications, the computation of the exact distance to the manifold is costly, whereas an efficient practical solution is the approximation of ...

Citation Formats

S. Cinel and C. F. Bazlamaçcı, “A Distributed Heuristic Algorithm for the Rectilinear Steiner Minimal Tree Problem,” IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, pp. 2083–2087, 2008, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/57098.