A FAST MULTIGRID ALGORITHM FOR ENERGY MINIMIZATION UNDER PLANAR DENSITY CONSTRAINTS

被引：2

作者：

Ron, Dorit ^{[1
]}

Safro, Ilya ^{[2
]}

Brandt, Achi ^{[1
]}

机构：

[1] Weizmann Inst Sci, Dept Appl Math, IL-76100 Rehovot, Israel

[2] Argonne Natl Lab, Dept Math & Comp Sci, Argonne, IL 60439 USA

来源：

MULTISCALE MODELING & SIMULATION | 2010年 / 8卷 / 05期

关键词：

layout problems; graph drawing and visualization; density constraints; constrained optimization; geometric multigrid; full approximation scheme;

D O I：

10.1137/090771995

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

The two-dimensional layout optimization problem reinforced by the efficient space utilization demand has a wide spectrum of practical applications. Formulating the problem as a nonlinear minimization problem under planar equality and/or inequality density constraints, we present a linear time multigrid algorithm for solving a correction to this problem. The method is demonstrated in various graph drawing (visualization) instances.

引用

页码：1599 / 1620

页数：22

共 16 条

[1]

[Anonymous], 2003, NONLINEAR PROGRAMMIN

[2]

[Anonymous], 1984, Congr Numer

[3]

[Anonymous], ACM J EXP ALGORITHMI

[4]

Battista GD., 1998, Graph drawing: algorithms for the visualization of graphs

[5]

BRANDT A, 1977, MATH COMPUT, V31, P333, DOI 10.1090/S0025-5718-1977-0431719-X

[6]

Brandt A., 2003, Multilevel optimization in VLSICAD, V14 of Comb, P1

[7] Energy-efficient coverage problems in wireless ad-hoc sensor networks [J].

Cardei, M ;

Wu, J .

COMPUTER COMMUNICATIONS, 2006, 29 (04) :413-420

[8]

Chan T., 2005, P ISPD, P185

[9]

Drezner Z., 1995, Facility Location: A Survey of Applications and Methods

[10] ON VISUAL FORMALISMS [J].

HAREL, D .

COMMUNICATIONS OF THE ACM, 1988, 31 (05) :514-530

← 1 2 →