{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T20:36:51Z","timestamp":1725482211882},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540667315"},{"type":"electronic","value":"9783540467847"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-46784-x_28","type":"book-chapter","created":{"date-parts":[[2007,4,5]],"date-time":"2007-04-05T08:02:55Z","timestamp":1175760175000},"page":"291-302","source":"Crossref","is-referenced-by-count":2,"title":["Linear Orderings of Random Geometric Graphs"],"prefix":"10.1007","author":[{"given":"Josep","family":"D\u00edaz","sequence":"first","affiliation":[]},{"given":"Mathew D.","family":"Penrose","sequence":"additional","affiliation":[]},{"given":"Jordi","family":"Petit","sequence":"additional","affiliation":[]},{"given":"Mar\u00eda","family":"Serna","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"28_CR1","volume-title":"The probabilistic method","author":"N. Alon","year":"1992","unstructured":"N. Alon, J. H. Spencer, and P. Erd?os. The probabilistic method. Wiley-Interscience, New York, 1992. 292"},{"key":"28_CR2","unstructured":"M. J. Appel and R. P. Russo. The connectivity of a graph on uniform points in [0, 1] d . Technical Report #275, Department of Statistics and Actuarial Science, University of Iowa, 1996. 294"},{"issue":"1","key":"28_CR3","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1137\/S0097539795285771","volume":"28","author":"J.E. Atkins","year":"1999","unstructured":"J.E. Atkins, E.G. Boman, and B. Hendrickson. A spectral algorithm for seriation and the consecutive ones problem. SIAM J. Comput., 28(1):297\u2013310, 1999. 291","journal-title":"SIAM J. Comput."},{"key":"28_CR4","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1016\/0022-0000(84)90071-0","volume":"28","author":"S. N. Bhatt","year":"1984","unstructured":"S. N. Bhatt and F. T. Leighton. A framework for solving VLSI graph layout problems. Journal of Computer and System Sciences, 28:300\u2013343, 1984. 291","journal-title":"Journal of Computer and System Sciences"},{"key":"28_CR5","doi-asserted-by":"crossref","unstructured":"R. Boppana. Eigenvalues and graph bisection: An average case analysis. In Proc. on Foundations of Computer Science, pages 280\u2013285, 1987. 292","DOI":"10.1109\/SFCS.1987.22"},{"key":"28_CR6","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/BF02579448","volume":"7","author":"T. Bui","year":"1987","unstructured":"T. Bui, S. Chaudhuri, T. Leighton, and M. Sipser. Graph bisection algorithms with good average case behavior. Combinatorica, 7:171\u2013191, 1987. 292","journal-title":"Combinatorica"},{"key":"28_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-48109-5","volume-title":"Computing and Combinatorics-5th Annual International Conference, COCOON\u201999, Tokyo, Japan","author":"J. D\u00edaz","year":"1999","unstructured":"Josep D\u00edaz, Mathew D. Penrose, Jordi Petit, and Mar\u00eda Serna. Layout problems on lattice graphs. In T. Asano, H. Imai, D.T. Lee, S. Nakano, and T. Tokuyama, editors, Computing and Combinatorics-5th Annual International Conference, COCOON\u201999, Tokyo, Japan, July 26-28, 1999, number 1627 in Lecture Notes in Computer Science. Springer-Verlag, Berlin, July 1999. 301"},{"key":"28_CR8","unstructured":"J. D\u00edaz, J. Petit, M. Serna, and L. Trevisan. Approximating layout problems on random sparse graphs. Technical Report LSI 98-44-R, Universitat Polit`ecnica de Catalunya, 1998. 292"},{"key":"28_CR9","unstructured":"M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco, 1979. 293"},{"key":"28_CR10","first-page":"91","volume-title":"Proc. 11th. Conference on Information Sciences and Systems","author":"F. Gavril","year":"1977","unstructured":"F. Gavril. Some NP-complete problems on graphs. In Proc. 11th. Conference on Information Sciences and Systems, pages 91\u201395, John Hopkins Univ., Baltimore, 1977. 293"},{"issue":"6","key":"28_CR11","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1287\/opre.37.6.865","volume":"37","author":"D. S. Johnson","year":"1989","unstructured":"D. S. Johnson, C. R. Aragon, L. A. McGeoch, and C. Schevon. Optimization by simulated annealing: an experimental evaluation; part I, graph partitioning. Operations Research, 37(6):865\u2013892, November 1989. 292","journal-title":"Operations Research"},{"key":"28_CR12","unstructured":"K. Lang and S. Rao. Finding Near-Optimal Cuts: An Empirical Evaluation. In Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 212\u2013221, 1993. 292"},{"key":"28_CR13","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/BF00264496","volume":"16","author":"T. Lengauer","year":"1981","unstructured":"T. Lengauer. Black-white pebbles and graph separation. Acta Informatica, 16:465\u2013475, 1981. 293","journal-title":"Acta Informatica"},{"issue":"4","key":"28_CR14","doi-asserted-by":"publisher","first-page":"571","DOI":"10.1137\/0607063","volume":"7","author":"G. Mitchison","year":"1986","unstructured":"G. Mitchison and R. Durbin. Optimal numberings of an n\u00d7n array. SIAM Journal on Discrete Mathematics, 7(4):571\u2013582, 1986. 291","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"28_CR15","unstructured":"C. H. Papadimitriou and M. Sideri. The bisection width of grid graphs. In First ACM-SIAM Symposium on Discrete Algorithms, pages 405\u2013410, San Francisco, 1990. 295"},{"key":"28_CR16","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1214\/aoap\/1034625335","volume":"7","author":"M. D. Penrose","year":"1997","unstructured":"M. D. Penrose. The longest edge of the random minimal spanning tree. The Annals of Applied Probability, 7:340\u2013361, 1997. 292","journal-title":"The Annals of Applied Probability"},{"key":"28_CR17","unstructured":"J. Petit. 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\u00e0tics, Universitat Polit`ecnica de Catalunya, 1997. 291"},{"key":"28_CR18","unstructured":"J. Petit. Approximation Heuristics and Benchmarkings for the MinLA Problem. In R. Battiti and A. Bertossi, editors, Alex\u2019 98-Building bridges between theory and applications, http:\/\/www.lsi.upc.es\/?jpetit\/MinLA\/Benchmark , February 1998. Universit`a di Trento. 291, 292"},{"key":"28_CR19","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1137\/0215041","volume":"15","author":"J. S. Turner","year":"1986","unstructured":"J. S. Turner. On the probable performance of heuristics for bandwidth minimization. SIAM Journal on Computing, 15:561\u2013580, 1986. 291, 292","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46784-X_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,26]],"date-time":"2019-04-26T23:38:15Z","timestamp":1556321895000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46784-X_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540667315","9783540467847"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-46784-x_28","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1999]]}}}