Linear Layout Problems

Eduardo G. Pardo (), Rafael Martí () and Abraham Duarte ()
Additional contact information
Eduardo G. Pardo: Universidad Politécnica de Madrid, Dept. of Sistemas Informáticos
Rafael Martí: University of Valencia, Statistics and Operations Research Department
Abraham Duarte: Universidad Rey Juan Carlos, Móstoles (Madrid), Department of Ciencias de la Computación

Chapter 34 in Handbook of Heuristics, 2018, pp 1025-1049 from Springer

Abstract: Abstract The term layout problem comes from the context of Very Large-Scale Integration (VLSI) circuit design. Graph layouts are optimization problems where the main objective is to project an original graph into a predefined host graph, usually a horizontal line. In this paper, some of the most relevant linear layout problems are reviewed, where the purpose is to minimize the objective function: the Cutwidth, the Minimum Linear Arrangement, the Vertex Separation, the SumCut, and the Bandwidth. Each problem is presented with its formal definition and it is illustrated with a detailed example. Additionally, the most relevant heuristic methods in the associated literature are reviewed together with the instances used in their evaluation. Since linear layouts represent a challenge for optimization methods in general and, for heuristics in particular, this review pays special attention to the strategies and methodologies which provide high-quality solutions.

Keywords: Embedding; Graph layout; Heuristics; Linear arrangement; Linear layout; Optimization (search for similar items in EconPapers)
Date: 2018
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-319-07124-4_45

Ordering information: This item can be ordered from
http://www.springer.com/9783319071244

DOI: 10.1007/978-3-319-07124-4_45

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().