Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Kongresse
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Veranstaltungskalender Awards MyNewsletter Firmensuche
Kunden Login
Über Einzelzugang informieren
Über Unternehmenszugang informieren
Referenzkunden
Elektrische Antriebe und Energiesysteme 2025 | 26 + 27 März 2025

19. Internationaler MTZ-Fachkongress Zukunftsantriebe

Seien Sie bei der Konferenz dabei! Dort treffen Experten aus der Automobilindustrie, Energieerzeugung und Stromnetzbetrieb auf Vertreter aus Politik und Wissenschaft. Diskutiert werden wichtige Themen der Branche.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Kapitel lesen Erstes Kapitel lesen

2018 | OriginalPaper | Buchkapitel

34. Linear Layout Problems

verfasst von : Eduardo G. Pardo, Rafael Martí, Abraham Duarte

Erschienen in: Handbook of Heuristics

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Evolutionary Algorithms for the Inverse Protein Folding Problem
Nächstes Kapitel Maritime Container Terminal Problems
Literatur
1.
Adolphson DL (1977) Single machine job sequencing with precedence constraints. SIAM J Comput 6:50–54
2.
Adolphson DL, Hu TC (1973) Optimal linear ordering. SIAM J Appl Math 25(3):403–423
3.
Álvarez C, Cases R, Díaz J, Petit J, Serna M (2000) Approximation and randomized algorithms in communication networks. In: Routing trees problems on random graphs. ICALP workshops 2000. Carleton Scientific, p 99111
4.
Andrade DV, Resende MGC (2007) GRASP with evolutionary path-relinking. In: Seventh metaheuristics international conference (MIC), Montreal
5.
Andrade DV, Resende MGC (2007) GRASP with path-relinking for network migration scheduling. In: Proceedings of international network optimization conference (INOC), Spa
6.
Bezrukov SL, Chavez JD, Harper LH, öttger MR, Schroeder UP (2000) The congestion of n-cube layout on a rectangular grid. Discret Math 213:13–19
7.
Blin G, Fertin G, Hermelin D, Vialette S (2008) Fixed-parameter algorithms for protein similarity search under mRNA structure constraints. J Discret Algorithms 6:618–626
8.
Bodlaender HL, Gilbert JR, Hafsteinsson H, Kloks T (1995) Approximating treewidth, pathwidth, frontsize, and shortest elimination tree. J Algorithms 18(2):238–255
9.
Bodlaender HL, Gustedt J, Telle JA (1998) Linear-time register allocation for a fixed number of registers. In: Proceedings of the ninth annual ACM-SIAM symposium on discrete algorithms (SODA’98). Society for Industrial and Applied Mathematics, Philadelphia, pp 574–583
10.
Bodlaender HL, Kloks T, Kratsch D (1993) Treewidth and pathwidth of permutation graphs. In: Lingas A, Karlsson R, Carlsson S (eds) Automata, languages and programming. Lecture notes in computer science, vol 700. Springer, Berlin/Heidelberg, pp 114–125
11.
Bodlaender HL, Kloks T, Kratsch D (1995) Treewidth and pathwidth of permutation graphs. SIAM J Discret Math 8(4):606–616
12.
Bodlaender HL, Möhring RH (1990) The pathwidth and treewidth of cographs. SIAM J Discret Math 6(6):181–188
13.
Bollobás B, Leader I (1991) Edge-isoperimetric inequalities in the grid. Combinatorica 11(4):299–314
14.
Botafogo RA (1993) Cluster analysis for hypertext systems. In: 16th annual international ACM-SIGIR conference on research and development in information retrieval, Pittsburgh, PA, USA, pp 116–125
15.
Campos V, Piñana E, Martí R (2011) Adaptive memory programming for matrix bandwidth minimization. Ann Oper Res 183(1):7–23
16.
Chinn PZ, Chvátalová J, Dewdney AK, Gibbs NE (1982) The bandwidth problem for graphs and matricesa survey. J Graph Theory 6(3):223–254
17.
Chung MJ, Makedon F, Sudborough IH, Turner J (1982) Polynomial time algorithms for the min cut problem on degree restricted trees. In: Proceedings of the 23rd annual symposium on foundations of computer science (SFCS’82). IEEE Computer Society, Washington, DC, pp 262–271
18.
Cohoon J, Sahni S (1983) Exact algorithms for special cases of the board permutation problem. In: Proceedings of the allerton conference on communication, control and computing, Monticello, pp 246–255
19.
Cohoon J, Sahni S (1987) Heuristics for backplane ordering. J VLSI Comput Syst 2:37–61
20.
21.
Cuthill E, McKee J (1969) Reducing the bandwidth of sparse symmetric matrices. In: Proceedings of the 1969 24th national conference. ACM, New York, pp 157–172
22.
Corso GMD, Manzini G (1999) Finding exact solutions to the bandwidth minimization problem. Computing 62(3):189–203
23.
Díaz J, Gibbons A, Pantziou GE, Serna MJ, Spirakis PG, Torán J (1997) Parallel algorithms for the minimum cut and the minimum length tree layout problems. Theor Comput Sci 181:267–287
24.
Díaz J, Gibbons A, Paterson M, Torán J (1991) The minsumcut problem. In: Dehne F, Sack J-R, Santoro N (eds) WADS. Lecture notes in computer science, vol 519. Springer, Berlin/Heidelberg, pp 65–89
25.
Díaz J, Penrose MD, Petit J, Serna MJ (2000) Convergence theorems for some layout measures on random lattice and random geometric graphs. Comb Probab Comput 9: 489–511
26.
Díaz J, Petit J, Serna MJ (2002) A survey of graph layout problems. ACM Comput Surv (CSUR) 34(3):313–356
27.
Díaz J, Petit J, Serna MJ, Trevisan L (1998) Approximating layout problems on random sparse graphs. Technical report LSI-98-44-R, Departament de Llenguatges i Sistemes Informàtics, Universitat Politècnica de Catalunya (Presented in the fifth Czech-Slovak international symposium on combinatorics, graph theory, algorithms and applications)
28.
Ding G, Oporowski B (1995) Some results on tree decomposition of graphs. J Graph Theory 20(4):481–499
29.
Dorigo M (1992) Optimization, learning and natural algorithms. PhD thesis, Politecnico di Milano, Italia
30.
Duarte A, Escudero LF, Martí R, Mladenović N, Pantrigo JJ, Sánchez-Oro J (2012) Variable neighborhood search for the vertex separation problem. Comput Oper Res 39(12): 3247–3255
31.
Duarte A, Pantrigo JJ, Pardo EG, Mladenović N (2015) Multi-objective variable neighborhood search: an application to combinatorial optimization problems. J Glob Optim 63(3):515–536
32.
Duarte A, Pantrigo JJ, Pardo EG, Sánchez-Oro J (2016) Parallel variable neighbourhood search strategies for the cutwidth minimization problem. IMA J Manag Math 27(1):55–73
33.
Dueck G, Jeffs J (1995) A heuristic bandwidth reduction algorithm. J comb math comput 18:97–108
34.
Duff IS, Grimes RG, Lewis JG (1989) Sparse matrix test problems. ACM Trans Math Softw 15(1):1–14
35.
Duff IS, Grimes RG, Lewis JG (1992) User’s guide for the harwell-boeing sparse matrix collection (release I), Rutherford Appleton Laboratory, Chilton
36.
Dujmovic V, Fellows MR, Kitching M, Liotta G, McCartin C, Nishimura N, Ragde P, Rosamond F, Whitesides S, Wood DR (2008) On the parameterized complexity of layered graph drawing. Algorithmica 52(2):267–292
37.
Ellis JA, Sudborough IH, Turner JS (1994) The vertex separation and search number of a graph. Inf Comput 113(1):50–79
38.
Ellis JA, Markov M (2004) Computing the vertex separation of unicyclic graphs. Inf Comput 192(2):123–161
39.
Fellows MR, Langston MA (1994) On search, decision, and the efficiency of polynomial-time algorithms. J Comput Syst Sci 49(3):769–779
40.
Feo TA, Resende MGC (1989) A probabilistic heuristic for a computationally difficult set covering problem. Oper Res Lett 8(2):67–71
41.
Feo TA, Resende MGC (1995) Greedy randomized adaptive search procedures. J Glob Optim 6(2):109–133
42.
Garey MR, Johnson DS (1979) Computers and intractability: a Guide to the theory of np-completeness. W.H. Freeman, San Francisco
43.
Gavril F (1977) Some NP-complete problems on graphs. In: Proceedings of the eleventh conference on information sciences and systems, Baltimore, pp 91–95
44.
Gibbs NE, Poole WG Jr, Stockmeyer PK (1976) An algorithm for reducing the bandwidth and profile of a sparse matrix. SIAM J Numer Anal 13(2):236–250
45.
Glover F (1977) Heuristics for integer programming using surrogate constraints. Decis Sci 8(1):156–166
46.
Glover F (1997) Tabu search and adaptive memory programming—advances, applications and challenges. Springer, Boston, pp 1–75
47.
Glover F, Laguna M (1997) Tabu search. Kluwer Academic Publishers, Norwell
48.
Golberg DE (1989) Genetic algorithms in search, optimization, and machine learning. Addion wesley 1989:102
49.
Golovach P (2009) The total vertex separation number of a graph. Discret Math Appl 6(7):631–636
50.
Harper LH (1964) Optimal assignments of numbers to vertices. J Soc Ind Appl Math 12(1):131–135
51.
Harper LH (1966) Optimal numberings and isoperimetric problems on graphs. J Comb Theory 1:385–393
52.
Holland JH (1975) Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. University of Michigan Press, Ann Arbor
53.
Hu TC (1974) Optimum communication spanning trees. SIAM J Comput 3(3):188–195
54.
Johnson DS, Lenstra JK, Kan AHGR (1978) The complexity of the network design problem. Networks 8(4):279–285
55.
Juvan M, Marincek J, Mohar B (1995) Embedding a graph into the torus in linear time. Springer, Berlin/Heidelberg, pp 360–363
56.
Juvan M, Mohar B 1992 Optimal linear labelings and eigenvalues of graphs. Discret Appl Math 36:153–168
57.
Karger DR (1999) A randomized fully polynomial time approximation scheme for the all-terminal network reliability problem. SIAM J Comput 29(2):492–514
58.
Karp RM (1993) Mapping the genome: some combinatorial problems arising in molecular biology. In: Proceedings of the twenty-fifth annual ACM symposium on theory of computing. ACM, New York, pp 278–285
59.
Kendall D (1969) Incidence matrices, interval graphs and seriation in archeology. Pac J math 28(3):565–570
60.
Kennedy J Eberhart R (1995) Particle swarm optimization. In: Proceedings of the IEEE international conference on neural networks, Yokohama, vol 4, pp 1942–1948
61.
Kinnersley NG (1992) The vertex separation number of a graph equals its path-width. Inf Process Lett 42(6):345–350
62.
Kirkpatrick S, Gelatt CD, Vecchi MP 1983 Optimization by simulated annealing. Science 220(4598):671–680
63.
Kirousis LM, Papadimitriou CH (1985) Interval graphs and searching. Discret Math 55(2):181–184
64.
Kirousis LM, Papadimitriou CH (1986) Searching and pebbling. Theor Comput Sci 47(0):205–218
65.
Klugerman M, Russell A, Sundaram R (1998) On embedding complete graphs into hypercubes. Discret Math 186(13):289–293
66.
Laguna M, Martí R (2012) Scatter search: methodology and implementations in C, vol 24. Springer Science & Business Media, New York
67.
Leiserson CE (1980) Area-efficient graph layouts (for vlsi). In: IEEE symposium on foundations of computer science, Syracuse, pp 270–281
68.
Lewis JG (1982) The gibbs-poole-stockmeyer and gibbs-king algorithms for reordering sparse matrices. ACM Trans Math Softw (TOMS) 8(2):190–194
69.
Lewis RR (1994) Simulated annealing for profile and fill reduction of sparse matrices. Int J Numer Methods Eng 37(6):905–925
70.
Lim A, Lin J, Rodrigues B, Xiao F (2006) Ant colony optimization with hill climbing for the bandwidth minimization problem. Appl Soft Comput 6(2):180–188
71.
Lim A, Lin J, Xiao F (2007) Particle swarm optimization and hill climbing for the bandwidth minimization problem. Appl Intell 26(3):175–182
72.
Lim A, Rodrigues B, Xiao F (2006) Heuristics for matrix bandwidth reduction. Eur J Oper Res 174(1):69–91
73.
Lin YX (1994) Two-dimensional bandwidth problem. In: Combinatorics, graph theory, algorithms and applications 1993, Beijing, pp 223–232
74.
Lipton RJ, Tarjan RE (1979) A separator theorem for planar graphs. SIAM J Appl Math 36(2):177–189
75.
Livingston M, Stout QF (1988) Embeddings in hypercubes. Math Comput Model 11(0): 222–227
76.
López-Locés MC, Castillo-García N, Huacuja HJF, Bouvry P, Pecero JE, Rangel RAP, Barbosa JJG, Valdez F (2014) A new integer linear programming model for the cutwidth minimization problem of a connected undirected graph. In: Recent advances on hybrid approaches for designing intelligent systems. Springer, Cham, pp 509–517
77.
Lozano M, Duarte A, Gortázar F, Martí R (2013) A hybrid metaheuristic for the cyclic antibandwidth problem. Knowl-Based Syst 54:103–113
78.
Luttamaguzi J, Pelsmajer M, Shen Z, Yang B (2005) Integer programming solutions for several optimization problems in graph theory. Technical report, Center for Discrete Mathematics and Theoretical Computer Science, DIMACS
79.
80.
Martí R, Campos V, Piñana E (2008) A branch and bound algorithm for the matrix bandwidth minimization. Eur J Oper Res 186(2):513–528MathSciNetCrossRef
81.
Martí R, Laguna M, Glover F, Campos V (2001) Reducing the bandwidth of a sparse matrix with tabu search. Eur J Oper Res 135(2):450–459MathSciNetCrossRef
82.
Martí R, Pantrigo JJ, Duarte A, Campos V, Glover F (2011) Scatter search and path relinking: a tutorial on the linear arrangement problem. Int J Swarm Intell Res (IJSIR) 2(2): 1–21CrossRef
83.
Martí R, Pantrigo JJ, Duarte A, Pardo EG (2013) Branch and bound for the cutwidth minimization problem. Comput Oper Res 40(1):137–149MathSciNetCrossRef
84.
Mcallister AJ (1999) A new heuristic algorithm for the linear arrangement problem. Technical report, University of New Brunswick
85.
Miller Z, Sudborough IH 1991 A polynomial algorithm for recognizing bounded cutwidth in hypergraphs. Theory Comput Syst 24:11–40MathSciNetMATH
86.
87.
88.
Mladenović N, Urošević D, Pérez-Brito D (2014) Variable neighborhood search for minimum linear arrangement problem. Yugosl J Oper Res 24(2):2334–6043. ISSN:0354-0243
89.
Mladenović N, Urošević D, Pérez-Brito D, García-González CG (2010) Variable neighbourhood search for bandwidth reduction. Eur J Oper Res 200(1):14–27MathSciNetCrossRef
90.
Mutzel P (1995) A polyhedral approach to planar augmentation and related problems. In: Proceedings of the third annual European symposium on algorithms, ESA’95. Springer, London, pp 494–507
91.
Palubeckis G, Rubliauskas D (2012) A branch-and-bound algorithm for the minimum cut linear arrangement problem. J comb optim 24(4):540–563MathSciNetCrossRef
92.
Pantrigo JJ, Martí R, Duarte A, Pardo EG (2012) Scatter search for the cutwidth minimization problem. Ann Oper Res 199:285–304MathSciNetCrossRef
93.
94.
Pardo EG, Mladenović N, Pantrigo JJ, Duarte A (2012) A variable neighbourhood search approach to the cutwidth minimization problem. Electron Notes Discret Math 39(0):67–74MathSciNetCrossRef
95.
Pardo EG, Mladenović N, Pantrigo JJ, Duarte A (2013) Variable formulation search for the cutwidth minimization problem. Appl Soft Comput 13(5):2242–2252CrossRef
96.
97.
Peng SL, Ho CW, Hsu TS, Ko MT, Tang C (1998) A linear-time algorithm for constructing an optimal node-search strategy of a tree. In: Hsu W-L, Kao M-Y (eds) Computing and combinatorics. Lecture notes in computer science, vol 1449. Springer, Berlin/Heidelberg, pp 279–289CrossRef
98.
Petit J (2003) Combining spectral sequencing and parallel simulated annealing for the minla problem. Parallel Process Lett 13(1):77–91MathSciNetCrossRef
99.
Petit J (2003) Experiments on the minimum linear arrangement problem. ACM J Exp Algorithm 8:2–3MathSciNetMATH
100.
Piñana E, Plana I, Campos V, Martí R (2004) GRASP and path relinking for the matrix bandwidth minimization. Eur J Oper Res 153(1):200–210MathSciNetCrossRef
101.
Pop PC, Matei O (2011) An improved heuristic for the bandwidth minimization based on genetic programming. In: Hybrid artificial intelligent systems. Springer, Berlin, pp 67–74CrossRef
102.
Raspaud A, Schröder H, Sỳkora O, Torok L, Vrto I (2009) Antibandwidth and cyclic antibandwidth of meshes and hypercubes. Discret Math 309(11):3541–3552
103.
Ravi R, Agrawal A, Klein P (1991) Ordering problems approximated: single-processor scheduling and interval graph completion. In: Proceedings of the ICALP. Springer, Berlin, pp 751–762
104.
Resende MGC, Andrade DV (2009) Method and system for network migration scheduling. United States Patent Application Publication. US2009/0168665
105.
Rodriguez-Tello E, Hao J-K, Torres-Jimenez J (2008) An effective two-stage simulated annealing algorithm for the minimum linear arrangement problem. Comput Oper Res 35(10):3331–3346CrossRef
106.
Rodriguez-Tello E, Hao J-K, Torres-Jimenez J (2008) An improved simulated annealing algorithm for bandwidth minimization. Eur J Oper Res 185(3):1319–1335CrossRef
107.
Rolim J, Sýkora O, Vrt’o I (1995) Optimal cutwidths and bisection widths of 2- and 3-dimensional meshes. In: Graph-theoretic concepts in computer science. Lecture notes in computer science, vol 1017. Springer, Berlin/Heidelberg, pp 252–264
108.
Saad Y (2003) Iterative methods for sparse linear systems. SIAM, PhiladelphiaCrossRef
109.
Sánchez-Oro J, Duarte A (2012) An experimental comparison of variable neighborhood search variants for the minimization of the vertex-cut in layout problems. Electron Notes Discret Math 39:59–66MathSciNetCrossRef
110.
Sánchez-Oro J, Duarte A (2012) Grasp with path relinking for the sumcut problem. Int J Comb Optim Probl Inf 3:3–11
111.
Sánchez-Oro J, Duarte A Grasp for the sumcut problem. In: XVII international congress on computer science research, Morelia (México), 26–28/10/2011
112.
Sánchez-Oro J, Laguna M, Duarte A, Martí R (2015) Scatter search for the profile minimization problem. Networks 65(1):10–21MathSciNetCrossRef
113.
Sánchez-Oro J, Pantrigo JJ, Duarte A (2014) Combining intensification and diversification strategies in VNS. An application to the vertex separation problem. Comput Oper Res 52(Part B):209–219
114.
Shahrokhi F, Sýkora O, Székely LA, Vrt’o I (2001) On bipartite drawings and the linear arrangement problem. SIAM J Comput 30(6):1773–1789MathSciNetCrossRef
115.
116.
Skodinis K (2000) Computing optimal linear layouts of trees in linear time. In: Proceedings of the 8th annual European symposium on algorithms, ESA’00. Springer, London, pp 403–414
117.
Sýkora O, Torok L, Vrt’o I (2005) The cyclic antibandwidth problem. Electron Notes Discret Math 7th Int Colloq Graph Theory 22:223–227
118.
Takagi K, Takagi N (1999) Minimum cut linear arrangement of p-q dags for VLSI layout of adder trees. IEICE Trans Fundam Electron Commun Comput Sci E82-A(5):767–774
119.
Tewarson RP (1973) Sparse matrices, vol 69. Academic Press, New YorkMATH
120.
Thilikos DM, Serna MJ, Bodlaender HL (2005) Cutwidth II: algorithms for partial w-trees of bounded degree. J Algorithms 56(1):25–49MathSciNetCrossRef
121.
Woodcock JR (2006) A faster algorithm for torus embedding. PhD thesis, University of Victoria
122.
Yannakakis M (1985) A polynomial algorithm for the min-cut linear arrangement of trees. J ACM (JACM) 32:950–988MathSciNetCrossRef
123.
Yuan J, Lin Y, Liu Y, Wang S (1998) NP-completeness of the profile problem and the fill-in problem on cobipartite graphs. J Math Study 31(3):239–243MathSciNetMATH
Metadaten
Titel
Linear Layout Problems
verfasst von
Eduardo G. Pardo
Rafael Martí
Abraham Duarte
Copyright-Jahr
2018
Buch
Handbook of Heuristics

Print ISBN: 978-3-319-07123-7

Electronic ISBN: 978-3-319-07124-4

Copyright-Jahr: 2018

DOI
https://doi.org/10.1007/978-3-319-07124-4_45

Premium Partner

    Bildnachweise