References

[1]     A. V. Aho, M. R. Garey, and J. D. Ullman. The transitive reduction of a directed graph. SIAM Journal on Computing, 1(2):131–137, 1972.

[2]     R. Bar-Yehuda, G. Even, J. Feldman, and J. Naor. Computing an optimal orientation of a balanced decomposition tree for linear arrangement problems. J. Graph Algorithms Appl., 5(4):1–27, 2001.

[3]     R. Bellman. On a routing problem. Quarterly of Applied Mathematics, 16(1):87–90, 1958.

[4]     A. Brandstädt, B. Van Le, and J. P. Spinrad. Graph classes: a survey. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1999.

[5]     E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269–271, 1959.

[6]     L. R. Ford. Network flow theory. Technical Report P-923, RAND Corp., Santa Monica, CA, USA, 1956.

[7]     M. L. Fredman and R. E. Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 34(3):596–615, 1987.

[8]     M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA, 1979.

[9]     L. H. Harper. Optimal assignments of numbers to vertices. Journal of the Society for Industrial and Applied Mathematics, 12(1):131–135, 1964.

[10]   B. Hendrickson and R. Leland. The Chaco User’s Guide Version 2.0. Sandia National Laboratories, Albuquerque, NM, USA, July 1995.

[11]   M. Juvan and B. Mohar. Optimal linear labelings and eigenvalues of graphs. Discrete Appl. Math., 36(2):153–168, 1992.

[12]   G. Karypis and V. Kumar. Analysis of multilevel graph partitioning. In Supercomputing ’95: Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), page 29, New York, NY, USA, 1995. ACM.

[13]   G. Karypis and V. Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput., 20(1):359–392, 1998.

[14]   G. Karypis and V. Kumar. METIS – A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices: Version 4.0. University of Minnesota, Minneapolis, MN, USA, 4.0 edition, September 1998.

[15]   G. Karypis and V. Kumar. Multilevel algorithms for multi-constraint graph partitioning. In Supercomputing ’98: Proceedings of the 1998 ACM/IEEE conference on Supercomputing, pages 1–13, Washington, DC, USA, 1998. IEEE Computer Society.

[16]   Y. Koren and D. Harel. A multi-scale algorithm for the linear arrangement problem. In WG ’02: Revised Papers from the 28th International Workshop on Graph-Theoretic Concepts in Computer Science, pages 296–309, London, UK, 2002. Springer-Verlag.

[17]   J. Leskovec, K. Lang, A. Dasgupta, and M. Mahoney. Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. Technical report, University of Stanford, 2008.

[18]   J. Petit. Combining spectral sequencing and parallel simulated annealing for the minla problem. Parallel Processing Letters, 13:2003, 2003.

[19]   J. Petit. Experiments on the minimum linear arrangement problem. J. Exp. Algorithmics, 8, 2003.

[20]   R. Ramakrishnan and J. Gehrke. Database Management Systems. McGraw-Hill, New York, NY, USA, 2002.

[21]   C. Ruemmler and J. Wilkes. An introduction to disk drive modeling. IEEE Computer, 27:17–28, 1994.

[22]   I. Safro, D. Ron, and A. Brandt. Graph minimum linear arrangement by multilevel weighted edge contractions. J. Algorithms, 60(1):24–41, 2006.

[23]   K. Schloegel, G. Karypis, and V. Kumar. Graph partitioning for high-performance scientific simulations, pages 491–541. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2003.