A branch-and-bound algorithm for the minimum cut linear arrangement problem
详细信息 查看全文
- 作者：Gintaras Palubeckis (1) gintaras@soften.ktu.lt
Dalius Rubliauskas (1) dalius@soften.ktu.lt - 关键词：Graph – ; Cutwidth – ; Combinatorial optimization – ; Minimum cut linear arrangement – ; Branch ; and ; bound algorithm – ; Tabu search
- 刊名：Journal of Combinatorial Optimization
- 出版年：2012
- 出版时间：November 2012
- 年：2012
- 卷：24
- 期：4
- 页码：540-563
- 全文大小：693.0 KB
- 参考文献：1. Berger N, Kenyon C, Mossel E, Peres Y (2005) Glauber dynamics on trees and hyperbolic graphs. Probab Theory Relat Fields 131:311–340
2. Bezrukov SL, Das SK, Els盲sser R (2000) An edge-isoperimetric problem for powers of the Petersen graph. Ann Comb 4:153–169
3. Blin G, Fertin G, Hermelin D, Vialette S (2005) Fixed-parameter algorithms for protein similarity search under mRNA structure constraints. In: 31st International workshop on graph-theoretic concepts in computer science (WG’05). LNCS, vol 3787. Springer, Berlin, pp 271–282
4. Brunetta L, Conforti M, Rinaldi G (1997) A branch-and-cut algorithm for the equicut problem. Math Program 78:243–263
5. D铆az J, Petit J, Serna M (2002) A survey of graph layout problems. ACM Comput Surv 34:313–356
6. Djidjev HN, Vrt’o I (2003) Crossing numbers and cutwidths. J Graph Algorithms Appl 7:245–251
7. G&G Graph Library (2009). http://bkocay.cs.umanitoba.ca/g&g/graphlib.html. Accessed 5 May 2009
8. Gatto M, Jacob R, Nunkesser M (2006) Optimization of a railway hub-and-spoke system: routing and shunting. Technical report 477, ETH Zurich, Institute for Theoretical Computer Science
9. Gavril F (1977) Some NP-complete problems on graphs. In: Proceedings of the 11th conference on information sciences and systems. John Hopkins University, Baltimore, pp 91–95
10. Glover F (1989) Tabu search—part I. ORSA J Comput 1:190–206
11. Harper LH (1964) Optimal assignments of numbers to vertices. SIAM J Appl Math 12:131–135
12. Karisch SE, Rendl F, Clausen J (2000) Solving graph bisection problems with semidefinite programming. INFORMS J Comput 12:177–191
13. Luttamaguzi J, Pelsmajer M, Shen Z, Yang B (2005) Integer programming methods for several optimization problems in graph theory. In: Proceedings of the 20th international conference on computers and their applications (CATA 2005), New Orleans, LA, USA, pp 50–55
14. Makedon F, Sudborough IH (1983) Minimizing width in linear layouts. In: Proceedings of the 10th colloquium on automata, languages and programming. LNCS, vol 154. Springer, Berlin, pp 478–490
15. Mart铆 R, Pantrigo JJ, Duarte A, Pardo EG (2010) Branch and bound for the cutwidth minimization problem. Technical report, University of Valencia, Spain
16. MathWorld: A Wolfram Web Resource (2009). http://mathworld.wolfram.com/topics/ArchimedeanGraphs.html. Accessed 5 May 2009
17. Monien B, Sudborough IH (1988) Min cut is NP-complete for edge weighted trees. Theor Comput Sci 58:209–229
18. Monien B, Vrt’o I (2004) Improved bounds on cutwidths of shuffle-exchange and de Bruijn graphs. Parallel Process Lett 14:361–366
19. Montanari A, Semerjian G (2006) On the dynamics of the glass transition on Bethe lattices. J Stat Phys 124:103–189
20. Nakano K (2003) Linear layout of generalized hypercubes. Int J Found Comput Sci 14:137–156
21. Palubeckis G (2006) Iterated tabu search for the unconstrained binary quadratic optimization problem. Informatica 17:279–296
22. Palubeckis G (2007) Iterated tabu search for the maximum diversity problem. Appl Math Comput 189:371–383
23. Pantrigo JJ, Mart铆 R, Duarte A, Pardo EG (2010) Scatter search for the cutwidth minimization problem. Technical report, University of Valencia, Spain
24. PARTY Graph Collection (2009). http://wwwcs.uni-paderborn.de/cs/ag-monien/RESEARCH/PART/graphs.html. Accessed 5 May 2009
25. Rolim J, S媒kora O, Vrt’o I (1995) Optimal cutwidths and bisection widths of 2- and 3-dimensional meshes. In: 21st International workshop on graph-theoretic concepts in computer science (WG’95). LNCS, vol 1017. Springer, Berlin, pp 252–264
26. Shelar RS, Sapatnekar SS (2002) Efficient layout synthesis algorithm for pass transistor logic circuits. In: Proceedings of the 11th IEEE/ACM international workshop on logic&synthesis (IWLS-02), New Orleans, LA, USA, pp 209–214
27. 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:767–774
28. Thilikos DM, Serna M, Bodlaender HL (2005a) Cutwidth I: a linear time fixed parameter algorithm. J Algorithms 56:1–24
29. Thilikos DM, Serna M, Bodlaender HL (2005b) Cutwidth II: algorithms for partial w-trees of bounded degree. J Algorithms 56:25–49
30. Wikipedia (2009). http://en.wikipedia.org/wiki/Gray_graph. Accessed 5 May 2009
31. Yannakakis M (1985) A polynomial algorithm for the min-cut linear arrangement of trees. J ACM 32:950–988 - 作者单位：1. Multimedia Engineering Department, Kaunas University of Technology, Studentu 50-408, 51368 Kaunas, Lithuania
- ISSN：1573-2886
文摘
Given an edge-weighted graph G of order n, the minimum cut linear arrangement problem (MCLAP) asks to find a one-to-one map from the vertices of G to integers from 1 to n such that the largest of the cut values c 1,…,c n−1 is minimized, where c i , i∈{1,…,n−1}, is the total weight of the edges connecting vertices mapped to integers 1 through i with vertices mapped to integers i+1 through n. In this paper, we present a branch-and-bound algorithm for solving this problem. A salient feature of the algorithm is that it employs a dominance test which allows reducing the redundancy in the enumeration process drastically. The test is based on the use of a tabu search procedure developed to solve the MCLAP. We report computational results for both the unweighted and weighted graphs. In particular, we focus on calculating the cutwidth of some well-known graphs from the literature.