FLOORPLANNING BY GRAPH DUALIZATION - L-SHAPED MODULES

Authors
SUN YY SARRAFZADEH M
Citation
Yy. Sun et M. Sarrafzadeh, FLOORPLANNING BY GRAPH DUALIZATION - L-SHAPED MODULES, Algorithmica, 10(6), 1993, pp. 429-456
Citations number
15
Categorie Soggetti
Computer Sciences",Mathematics,Mathematics,"Computer Applications & Cybernetics
Journal title
Algorithmica → ACNP
ISSN journal
01784617
Volume
10
Issue
6
Year of publication
1993
Pages
429 - 456
Database
ISI
SICI code
0178-4617(1993)10:6<429:FBGD-L>2.0.ZU;2-N
Abstract
We propose a novel technique for constructing a floorplan from an adja cency requirement-represented by a graph G. The algorithm finds a geom etric dual of G involving both rectangular and L-shaped modules. This is the first dualization technique which permits L-shaped modules. We can test in 0(n3/2) time if G admits an L-shaped dual and construct on e, if it exists, in O(n2) time, where n is the number of modules.