Ilya Safro
Skip Abstract Section
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.
- Bar-Yehuda, R., Even, G., Feldman, J., and Naor, J. 2001. Computing an optimal orientation of a balanced decomposition tree for linear arrangement problems. J. Graph Algorithms Appl. 5, 4, 1--27.Google Scholar
Cross Ref
- Barnard, S., Pothen, A., and Simon, H. 1995. A spectral algorithm for envelope reduction of sparse matrices. Numerical Linear Algebra Appl. 2, 4, 317--334.Google ScholarCross Ref
- Brandt, A. 1986. Algebraic multigrid theory: The symmetric case. J. Appl. Math. Comp. 19, 23--56. Preliminary proceedings of the International Multigrid Conference, April 6--8, 1983, Copper Mountain, CO. Google ScholarDigital Library
- Brandt, A. 2001. Multiscale scientific computation: Review 2001. In Multiscale and Multiresolution Methods (Proceeding of the Yosemite Educational Symposium, October 2000), T. Barth, R. Haimes, and T. Chan, Eds. Springer-Verlag.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- Briggs, W. L., Henson, V. E., and McCormick, S. F. 2000. A multigrid tutorial: second edition. Society for Industrial and Applied Mathematics, Philadelphia, PA. Google ScholarDigital Library
- Campos, V., Glover, F., Laguna, M., and Martí, R. 2001. An experimental evaluation of a scatter search for the linear ordering problem. J. Global Optimization 21, 4, 397--414. Google ScholarDigital Library
- Caprara, A. and González, J. J. S. 2005. Laying out sparse graphs with provably minimum bandwidth. INFORMS J. Comput. 17, 3, 356--373. Google ScholarDigital Library
- Cheng, C.-K. 1987. Linear placement algorithm and applications to VLSI design. Network 17, 4, 439--464. Google ScholarDigital Library
- Corso, G. M. D. and Romani, F. 2001a. Heuristic spectral techniques for the reduction of bandwidth and work-bound of sparse matrices. Numerical Algorithms 28, 1--4 (Dec.), 117--136.Google ScholarCross Ref
- Corso, G. M. D. and Romani, F. 2001b. Heuristic spectral techniques for the reduction of bandwidth and work-bound of sparse matrices. Tech. Rep. TR-01-02, Universitá di Piza, Dipartimento di Informatica.Google Scholar
- Cuthill, E. and McKee, J. 1969. Reducing the bandwidth of sparse symmetric matrices. In Proceedings of the 1969 24th national conference. ACM Press, New York. 157--172. Google ScholarDigital Library
- Davis, T. 1997. University of florida sparse matrix collection. NA Digest 97, 23.Google Scholar
- Díaz, J., Petit, J., and Serna, M. 2002. A survey of graph layout problems. ACM Comput. Surv. 34, 3, 313--356. Google ScholarDigital Library
- Dueck, G. W. and Jeffs, J. 1995. A heuristic bandwidth reduction algorithm. J. Combinatorial Math. Combinatorial Comput. 18, 97--108.Google Scholar
- Garey, M. R., Johnson, D. S., and Stockmeyer, L. 1974. Some simplified np-complete problems. In STOC'74: Proceedings of the 6th Annual ACM Symposium on Theory of Computing. ACM Press, New York. 47--63. Google ScholarDigital Library
- George, A. and Pothen, A. 1997. An analysis of spectral envelope reduction via quadratic assignment problems. SIAM J. Matrix Analysis Appl. 18, 3, 706--732. Google ScholarDigital Library
- Horton, S. B. 1997. The optimal linear arrangement problem: Algorithms and approximation. Ph.D. thesis, Georgia Institute of Technology. Google ScholarDigital Library
- Hu, Y. F. and Scott, J. A. 2001. A multilevel algorithm for wavefront reduction. SIAM J. Sci. Comput. 23, 4, 1352--1375. Google ScholarDigital Library
- Juvan, M. and Mohar, B. 1992. Optimal linear labelings and eigenvalues of graphs. Discrete Appl. Math. 36, 2, 153--168. Google ScholarDigital Library
- Kirkpatrick, S. 1981. Models of disordered systems. In Lecture Notes in Physics 149, C. Castellani, Ed. Springer-Verlag, New York.Google Scholar
- Koren, Y. and Harel, D. 2002. Multi-scale algorithm for the linear arrangement problem. In Proceedings of 28th International Workshop on Graph-Theoretic Concepts. Google ScholarDigital Library
- Lai, Y. and Williams, K. 1999. A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs. J. Graph Theory 31, 75--94. Google ScholarDigital Library
- Lim, A., Rodrigues, B., and Xiao, F. 2006. Heuristics for matrix bandwidth reduction. Europ. J. Operational Res. 174, 1, 69--91.Google ScholarCross Ref
- Martí, R., M., L., F., G., and Campos, V. 2001. Reducing the bandwidth of a sparse matrix with tabu search. Eur. J. Oper. Res. 135, 2, 211--220.Google ScholarCross Ref
- Mehlhorn, K. and Näher, S. 1995. Leda: a platform for combinatorial and geometric computing. Commun. ACM 38, 1, 96--102. Google ScholarDigital Library
- Petit, J. 2003. Experiments on the minimum linear arrangement problem. ACM J. Experimental Algorithmics, 8. Google ScholarDigital Library
- Pinana, E., Plana, I., Campos, V., and Martí, R. 2004. GRASP and path relinking for the matrix bandwidth minimization. Europ. J. Operational Res. 153, 1, 200--210.Google ScholarCross Ref
- Pozo, R., Dongarra, J. J., and Walker, D. W. 1993. Lapack++: a design overview of object-oriented extensions for high performance linear algebra. In Supercomputing '93: Proceedings of the 1993 ACM/IEEE Conference on Supercomputing. ACM Press, New York. 162--171. Google ScholarDigital Library
- 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.Google Scholar
- Ron, D., Wishko-Stern, S., and Brandt, A. 2005. An algebraic multigrid based algorithm for bisectioning general graphs. Tech. Rep. MCS05-01, Department of Computer Science and Applied Mathematics, The Weizmann Institute of Science.Google Scholar
- Ruge, J. and Stüben, K. 1987. Algebraic Multigrid. SIAM, 73--130.Google Scholar
- Safro, I. Homepage of our projects. http://www.wisdom.weizmann.ac.il/~safro.Google Scholar
- Safro, I., Ron, D., and Brandt, A. 2006a. Graph minimum linear arrangement by multilevel weighted edge contractions. J. Algorithms 60, 1, 24--41. Google ScholarDigital Library
- Safro, I., Ron, D., and Brandt, A. 2006b. Multilevel algorithm for the minimum 2-sum problem. J. Graph Algorithms Appl. 10, 2, 237--258.Google ScholarCross Ref
- Shahrokhi, F., Sýkora, O., Székely, L. A., and Vrto, I. 2001. On bipartite drawings and the linear arrangement problem. SIAM J. Comput. 30, 6, 1773--1789. Google ScholarDigital Library
- Sharon, E., Brandt, A., and Basri, R. 2000. Fast multiscale image segmentation. In Proceedings IEEE Conference on Computer Vision and Pattern Recognition. 70--77.Google Scholar
- Stüben, K. 2001a. An introduction to algebraic multigrid. Academic Press, New York. 413--532.Google Scholar
- Stüben, K. 2001b. A review of algebraic multigrid. J. Comput. Appl. Math. 128, 1-2, 281--309. Google ScholarDigital Library
Index Terms
- Multilevel algorithms for linear ordering problems
Recommendations
Linear Orderings of Subfamilies of AT-Free Graphs
Asteroidal triple free (AT-free) graphs have been introduced as a generalization of interval graphs, since interval graphs are exactly the chordal AT-free graphs. While for interval graphs it is obvious that there is always a linear ordering of the ...
Genus g graphs have pagenumber O( square root g)
SFCS '88: Proceedings of the 29th Annual Symposium on Foundations of Computer ScienceA book embedding of a graph consists of a linear ordering of the vertices along the spine of a book and an assignment of edges to pages so that edges on the same page do not intersect. The minimum number of pages in which a graph can be embedded is its ...
Algebraic Multilevel Krylov Methods
In [Erlangga and Nabben, SIAM J. Sci. Comput., 30 (2008), pp. 1572-1595], we developed a new type of multilevel method, called the multilevel Krylov (MK) method, to solve linear systems of equations. The basic idea of this type of method is to shift ...
Comments