Abstract
This work deals with bounds on the cost of layout problems for lattice graphs and random lattice graphs. Our main result in this paper is a convergence theorem for the optimal cost of the Minimum Linear Arrangement problem and the Minimum Sum Cut problem, for the case where the underlying graph is obtained through a subcritical site percolation process. This result can be viewed as an analogue of the Beardwood, Halton and Hammersley theorem for the Euclidian TSP. Finally we estimate empirically the value for the constant in the mentioned theorem.
This research was partially supported by ESPRIT LTR Project no. 20244 — ALCOM-IT, CICYT Project TIC97-1475-CE, and CIRIT project 1997SGR-00366.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
S. Arora, A. Frieze, and H. Kaplan. A new rounding procedure for the assignment problem with applications to dense graphs arrangements. In 37th IEEE Symposium on Foundations of Computer Science, 1996.
J. Beardwood, J. Halton, and J.M. Hammersley. The shortest path through many points. Proceedings of the Cambridge Philos. Society., 55:299–327, 1959.
K.L. Chung. A Course in Probability Theory. Academic Press, New York, 1974.
J. Díaz, M. D. Penrose, J. Petit, and M. Serna. Linear orderings of random geometric graphs. Technical report, Departament de Llenguatges i Sistemes Informàtics, UPC, http://www.lsi.upc.es/~jpetit/Publications, 1999.
J. Díaz. The δ-operator. In L. Budach, editor, Fundamentals of Computation Theory, pages 105–111. Akademie-Verlag, 1979.
N. Dunford and J. Schwartz. Linear Operators. Part I: General Theory. Interscience Publisher., New York, 1958.
S. Even and Y. Shiloach. NP-completeness of several arrangements problems. Technical report, TR-43 The Technion, Haifa, 1978.
G. Grimmett. Percolation. (2nd edition). Springer-Verlag, Heidelberg, 1999.
G. Mitchison and R. Durbin. Optimal numberings of an n x n array. SIAM Journal on Discrete Mathematics, 7(4):571–582, 1986.
D.O. Muradyan and T.E. Piliposjan. Minimal numberings of vertices of a rectangular lattice. Akad. Nauk. Armjan. SRR, 1(70):21–27, 1980. In Russian.
K. Nakano. Linear layouts of generalized hypercubes. In J. van Leewen, editor, Graph-theoretic concepts in computer science, volume 790 of Lecture Notes in Computer Science, pages 364–375. Springer-Verlag, 1993.
C. H. Papadimitriou and M. Sideri. The bisection width of grid graphs. In First ACM-SIAM Symp. on Discrete Algorithms., pages 405–410, San Francisco, 1990.
M.D. Penrose. Vertex ordering and partition problems for random spatial graphs. Technical report, University of Durham, 1999.
J. Petit i Silvestre. Combining Spectral Sequencing with Simulated Annealing for the MINLA Problem: Sequential and Parallel Heuristics. Technical Report LSI-97-46-R, Departament de Llenguatges i Sistemes Informàtics, Universitat Politècnica de Catalunya, 1997.
J. Petit i Silvestre. Approximation Heuristics and Benchmarkings for the MINLA Problem. In Roberto Battiti and Alan A Bertossi, editors, Alex —98 — Building bridges between theory and applications, http://www.lsi.upc.es/~jpetit/MinLA/Benchmark, February 1998. Universitá di Trento.
J.M. Steele. Probability theory and Combinatorial Optimization. SIAM CBMS-NSF Regional Conference Series in Applied Mathematics., 1997.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Díaz, J., Penrose, M.D., Petit, J., Serna, M. (1999). Layout Problems on Lattice Graphs. In: Asano, T., Imai, H., Lee, D.T., Nakano, Si., Tokuyama, T. (eds) Computing and Combinatorics. COCOON 1999. Lecture Notes in Computer Science, vol 1627. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48686-0_10
Download citation
DOI: https://doi.org/10.1007/3-540-48686-0_10
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66200-6
Online ISBN: 978-3-540-48686-2
eBook Packages: Springer Book Archive