Show/Hide Menu
Hide/Show Apps
Logout
Türkçe
Türkçe
Search
Search
Login
Login
OpenMETU
OpenMETU
About
About
Open Science Policy
Open Science Policy
Open Access Guideline
Open Access Guideline
Postgraduate Thesis Guideline
Postgraduate Thesis Guideline
Communities & Collections
Communities & Collections
Help
Help
Frequently Asked Questions
Frequently Asked Questions
Guides
Guides
Thesis submission
Thesis submission
MS without thesis term project submission
MS without thesis term project submission
Publication submission with DOI
Publication submission with DOI
Publication submission
Publication submission
Supporting Information
Supporting Information
General Information
General Information
Copyright, Embargo and License
Copyright, Embargo and License
Contact us
Contact us
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
199
views
0
downloads
Cite This
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
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
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.