{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,11]],"date-time":"2023-01-11T08:09:32Z","timestamp":1673424572867},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2009,2]]},"abstract":"Linear ordering problems are combinatorial optimization problems that deal with the minimization of different functionals by finding a suitable permutation of the graph vertices. These problems are widely used and studied in many practical and theoretical applications. In this paper, we present a variety of linear--time algorithms for these problems inspired by the Algebraic Multigrid approach, which is based on weighted-edge contraction. The experimental result for four such problems turned out to be better than every known result in almost all cases, while the short (linear) running time of the algorithms enables testing very large graphs.<\/jats:p>","DOI":"10.1145\/1412228.1412232","type":"journal-article","created":{"date-parts":[[2008,10,7]],"date-time":"2008-10-07T12:48:29Z","timestamp":1223383709000},"source":"Crossref","is-referenced-by-count":22,"title":["Multilevel algorithms for linear ordering problems"],"prefix":"10.1145","volume":"13","author":[{"given":"Ilya","family":"Safro","sequence":"first","affiliation":[{"name":"The Weizmann Institute of Science, Rehovot, Israel"}]},{"given":"Dorit","family":"Ron","sequence":"additional","affiliation":[{"name":"The Weizmann Institute of Science, Rehovot, Israel"}]},{"given":"Achi","family":"Brandt","sequence":"additional","affiliation":[{"name":"The Weizmann Institute of Science, Rehovot, Israel"}]}],"member":"320","published-online":{"date-parts":[[2009,2,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00035"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1002\/nla.1680020402"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0096-3003(86)90095-0"},{"key":"e_1_2_1_4_1","volume-title":"Multiscale and Multiresolution Methods (Proceeding of the Yosemite Educational Symposium","author":"Brandt A.","year":"2001"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Brandt A. and Ron D. 2003. Chapter 1 : Multigrid solvers and multilevel optimization strategies. In Multilevel Optimization and VLSICAD J. Cong and J. R. Shinnerl Eds. Kluwer Boston MA. Brandt A. and Ron D. 2003. Chapter 1 : Multigrid solvers and multilevel optimization strategies. In Multilevel Optimization and VLSICAD J. Cong and J. R. Shinnerl Eds. Kluwer Boston MA.","DOI":"10.1007\/978-1-4757-3748-6_1"},{"key":"e_1_2_1_6_1","unstructured":"Brandt A. McCormick S. and Ruge J. 1982. Algebraic multigrid (AMG) for automatic multigrid solution with application to geodetic computations. Tech. Rep. Institute for Computational Studies Fort Collins CO POB 1852. Brandt A. McCormick S. and Ruge J. 1982. Algebraic multigrid (AMG) for automatic multigrid solution with application to geodetic computations. Tech. Rep. Institute for Computational Studies Fort Collins CO POB 1852."},{"key":"e_1_2_1_7_1","unstructured":"Brandt A. McCormick S. and Ruge J. 1984. Algebraic multigrid (AMG) for sparse matrix equations. In Sparsity and its Applications D. J. Evans Ed. Cambridge University Press Cambridge. 257--284. Brandt A. McCormick S. and Ruge J. 1984. Algebraic multigrid (AMG) for sparse matrix equations. In Sparsity and its Applications D. J. Evans Ed. Cambridge University Press Cambridge. 257--284."},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Brandt A. Ron D. and Amit D. 1986. Multi-level approaches to discrete-state and stochastic problems. In Multigrid Methods II W. Hackbush and U. Trottenberg Eds. Springer-Verlag New York 66--99. Brandt A. Ron D. and Amit D. 1986. Multi-level approaches to discrete-state and stochastic problems. In Multigrid Methods II W. Hackbush and U. Trottenberg Eds. Springer-Verlag New York 66--99.","DOI":"10.1007\/BFb0072642"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Briggs W. L. Henson V. E. and McCormick S. F. 2000. A multigrid tutorial: second edition. Society for Industrial and Applied Mathematics Philadelphia PA. Briggs W. L. Henson V. E. and McCormick S. F. 2000. A multigrid tutorial: second edition. Society for Industrial and Applied Mathematics Philadelphia PA.","DOI":"10.1137\/1.9780898719505"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1012793906010"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1040.0083"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230170406"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1016880217658"},{"key":"e_1_2_1_14_1","volume-title":"Tech. Rep. TR-01-02, Universit\u00e1 di Piza, Dipartimento di Informatica.","author":"Corso G. M. D.","year":"2001"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/800195.805928"},{"key":"e_1_2_1_16_1","first-page":"23","article-title":"University of florida sparse matrix collection","volume":"97","author":"Davis T.","year":"1997","journal-title":"NA Digest"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/568522.568523"},{"key":"e_1_2_1_18_1","first-page":"97","article-title":"A heuristic bandwidth reduction algorithm","volume":"18","author":"Dueck G. W.","year":"1995","journal-title":"J. Combinatorial Math. Combinatorial Comput."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/800119.803884"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S089547989427470X"},{"key":"e_1_2_1_21_1","unstructured":"Horton S. B. 1997. The optimal linear arrangement problem: Algorithms and approximation. Ph.D. thesis Georgia Institute of Technology. Horton S. B. 1997. The optimal linear arrangement problem: Algorithms and approximation. Ph.D. thesis Georgia Institute of Technology."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827500377733"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(92)90229-4"},{"key":"e_1_2_1_24_1","volume-title":"Lecture Notes in Physics 149","author":"Kirkpatrick S."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of 28th International Workshop on Graph-Theoretic Concepts.","author":"Koren Y."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199906)31:2%26lt;%26gt;1.0.CO;2-3"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2005.02.066"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(00)00325-8"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/204865.204889"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/996546.996554"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(02)00715-4"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/169627.169680"},{"key":"e_1_2_1_33_1","unstructured":"Ron D. 1990. Ph.D. thesis. development of fast numerical solvers for problems in optimization and statistical mechanics. Ph.D. thesis The Weizmann Institute of Science. Ron D. 1990. Ph.D. thesis. development of fast numerical solvers for problems in optimization and statistical mechanics. Ph.D. thesis The Weizmann Institute of Science."},{"key":"e_1_2_1_34_1","volume-title":"Tech. Rep. MCS05-01, Department of Computer Science and Applied Mathematics","author":"Ron D.","year":"2005"},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","unstructured":"Ruge J. and St\u00fcben K. 1987. Algebraic Multigrid. SIAM 73--130. Ruge J. and St\u00fcben K. 1987. Algebraic Multigrid. SIAM 73--130.","DOI":"10.1137\/1.9781611971057.ch4"},{"key":"e_1_2_1_36_1","unstructured":"Safro I. Homepage of our projects. http:\/\/www.wisdom.weizmann.ac.il\/~safro. Safro I. Homepage of our projects. http:\/\/www.wisdom.weizmann.ac.il\/~safro."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.10.004"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00126"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797331671"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings IEEE Conference on Computer Vision and Pattern Recognition. 70--77","author":"Sharon E."},{"key":"e_1_2_1_41_1","unstructured":"St\u00fcben K. 2001a. An introduction to algebraic multigrid. Academic Press New York. 413--532. St\u00fcben K. 2001a. An introduction to algebraic multigrid. Academic Press New York. 413--532."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-0427(00)00516-1"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1412228.1412232","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,29]],"date-time":"2022-12-29T08:54:35Z","timestamp":1672304075000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1412228.1412232"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,2]]},"references-count":42,"alternative-id":["10.1145\/1412228.1412232"],"URL":"http:\/\/dx.doi.org\/10.1145\/1412228.1412232","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":["Theoretical Computer Science"],"published":{"date-parts":[[2009,2]]}}}