Josep Díaz
Skip Abstract Section
Abstract
Graph layout problems are a particular class of combinatorial optimization problems whose goal is to find a linear layout of an input graph in such way that a certain objective cost is optimized. This survey considers their motivation, complexity, approximation properties, upper and lower bounds, heuristics and probabilistic analysis on random graphs. The result is a complete view of the current state of the art with respect to layout problems from an algorithmic point of view.
- Aarts, E. and Lenstra, J. K., Eds. 1997. Local Search in Combinatorial Optimization. Wiley, New York.]] Google Scholar
- Adolphson, D. 1977. Single machine job sequencing with precedence constraints. SIAM J. Comput. 6, 40--54.]]Google Scholar
- Adolphson, D. and Hu, T. C. 1973. Optimal linear ordering. SIAM J. Appl. Mathem. 25, 3, 403--423.]]Google Scholar
- Alon, N. and Milman, V. 1985. λ1, isoperimetric inequalities for graphs and superconcentrators. J. Combinatorial Theory. Series B 38, 73--88.]]Google Scholar
- Àlvarez, C., Cases, R., Díaz, J., Petit, J., and Serna, M. 2000. Routing trees problems on random graphs. In Approximation and Randomized Algorithms in Communication Networks, J. Rolim et al., Ed. ICALP Workshops 2000. Carleton Scientific, 99--111.]]Google Scholar
- Àlvarez, C., Díaz, J., and Serna, M. 1998. Intervalizing colored graphs is NP-complete for caterpillars with hair length 2. Technical report LSI 98-9-R, Dept. de Llenguatges i Sistemes Informàtics, Univ. Politècnica de Catalunya.]]Google Scholar
- Àlvarez, C., Díaz, J., and Serna, M. 2001. The hardness of intervalizing four colored caterpillars. Discrete Mathematics 235, 19--27.]]Google Scholar
- Àlvarez, C. and Serna, M. 1999. The proper interval colored graph problem for caterpillar trees. Technical report LSI 99-12-R, Dept. de Llenguatges i Sistemes Informàtics, Univ. Politècnica de Catalunya.]]Google Scholar
- Arora, S., Frieze, A., and Kaplan, H. 1996. A new rounding procedure for the assignment problem with applications to dense graphs arrangements. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science. 21--30.]] Google Scholar
- Arora, S., Karger, D., and Karpinski, M. 1999. Polynomial time approximation schemes for dense instances of NP-hard problems. J. Comput. Syst. Sci. 58, 1, 193--210.]] Google Scholar
- Assman, S. F., Peck, G. W., Syslo, M. M., and Zak, J. 1981. The bandwidth of caterpillars with hair of lengths 1 and 2. SIAM J. Algebraic and Discrete Meth. 2, 387--393.]]Google Scholar
- Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., and Protasi, M. 1999. Complexity and Approximation. Springer-Verlag, Berlin.]] Google Scholar
- Azizoğlu, C. and Eğecioğlu, Ö. 2002. The isoperimetric number and the bisection width of generalized cylinders. Discrete Mathematics. To appear.]]Google Scholar
- Balasubramanian, R., Fellows, M., and Raman, V. 1998. An improved fixed-parameter algorithm for vertex cover. Information Proccessing Letters 65, 163--168.]] Google Scholar
- Barnard, S. T., Pothen, A., and Simon, H. 1995. A spectral algorithm for envelope reduction of sparse matrices. Numerical Linear Algebra with Applications 2, 4, 317--334.]]Google Scholar
- Barnard, S. T. and Simon, H. D. 1994. A fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems. Concurrency: Practice and Experience 6, 101--107.]]Google Scholar
- Barth, D., Pellegrini, F., Raspaud, A., and Roman, J. 1995. On bandwidth, cutwidth, and quotient graphs. RAIRO Informatique Théorique et Applications. 29, 6, 487--508.]]Google Scholar
- Battiti, R. and Bertossi, A. 1999. Greedy, prohibition, and reactive heuristics for graph partitioning. IEEE Trans. Comput. 48, 4, 361--385.]] Google Scholar
- Berger-Wolf, T. Y. and Reingold, E. M. 2002. Index assignment for multichannel communication under failure. IEEE Trans. Inform. Th.]]Google Scholar
- Bernhart, F. and Kainen, P. C. 1979. The book thickness of a graph. Journal of Combinatorial Theory. Series B 27, 3, 320--331.]]Google Scholar
- Berry, J. W. and Goldberg, M. K. 1999. Path optimization for graph partitioning problems. Discrete Applied Mathematics 90, 27--50.]] Google Scholar
- Bezrukov, S. L. 1999. Edge isoperimetric problems on graphs (a survey). In Graph Theory and Combinatorial Biology (Balatonlelle, 1996), L. Lovasz, A. Gyarfas, G. O. H. Katona, A. Recski, and L. Szekely, Eds. János Bolyai Math. Soc., 157--197.]]Google Scholar
- Bezrukov, S. L., Chavez, J. D., Harper, L. H., Röttger, M., and Schroeder, U.-P. 2000a. The congestion of n-cube layout on a rectangular grid. Discrete Mathematics 213, 1-3, 13--19.]] Google Scholar
- Bezrukov, S. L., Elsässer, R., Monien, B., Preis, R., and Tillich, J.-P. 2000b. New spectral lower bounds on the bisection width of graphs. In Graph-Theoretic Concepts in Computer Science, U. Brandes and D. Wagner, Eds. Lecture Notes in Computer Science, vol. 1928. Springer-Verlag, 23--34.]] Google Scholar
- Bhatt, S. N. and Leighton, F. T. 1984. A framework for solving VLSI graph layout problems. J. Comput. Syst. Sci. 28, 300--343.]]Google Scholar
- Bilski, T. 1993. Embedding graphs in books with prespecified order of vertices. Poznańskie Towarzystwo Przyjaciól Nauk. Wydzial Nauk Technicznych. Prace Komisji Automatyki i Informatyki. Studia z Automatyki 18, 5--12.]]Google Scholar
- Blache, G., Karpinski, M., and Wirtgen, J. 1998. On approximation intractability of the bandwidth problem. Technical report TR98-014, Electronic Colloquium on Computational Complexity.]]Google Scholar
- Blum, A., Konjevod, G., Ravi, R., and Vempala, S. 2000. Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems. Theoretical Computer Science 235, 1, 25--42.]] Google Scholar
- Bodlaender, H., Fellows, M. R., and Hallet, M. T. 1994. Beyond NP-completeness for problems of bounded width: hardness for the W-hierarchy. In Proceedings of the 26th Annual ACM Symposium on the Theory of Computing. 449--458.]] Google Scholar
- Bodlaender, H. L. 1993. A tourist guide through treewidth. Acta Cybernetica 11, 1-2, 1--21.]]Google Scholar
- Bodlaender, H. L. 1996. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25, 6, 1305--1317.]] Google Scholar
- Bodlaender, H. L. and de Fluiter, B. 1996. On intervalizing k-colored graphs for DNA physical mapping. Discrete Applied Mathematics 71, 1-3, 55--77.]] Google Scholar
- Bodlaender, H. L., Gilbert, J. R., Hafsteinsson, H., and Kloks, T. 1995a. Approximating treewidth, pathwidth, and minimum elimination tree height. J. Algor. 18, 238--255.]] Google Scholar
- Bodlaender, H. L., Kloks, T., and Kratsch, D. 1995b. Treewidth and pathwidth of permutation graphs. SIAM J. Discrete Mathem. 8, 4, 606--616.]] Google Scholar
- Bodlaender, H. L. and Möhring, R. H. 1993. The pathwidth and treewidth of cographs. SIAM J. Discrete Mathem. 6, 2, 181--188.]] Google Scholar
- Bollobás, B. 1985. Random Graphs. Academic Press, London.]]Google Scholar
- Bollobás, B. and Leader, I. 1991. Edge--isoperimetric inequalities in the grid. Combinatorica 4, 299--314.]]Google Scholar
- Boppana, R. 1987. Eigenvalues and graph bisection: An average case analysis. In Proceedings of the 28th Annual Symposium on Foundations of Computer Science. 280--285.]]Google Scholar
- Bornstein, C. and Vempala, S. 2002. Flow metrics. In Latin American Theoretical Informatics LATIN'02. Lecture Notes in Computer Science. To appear.]] Google Scholar
- Botafogo, R. A. 1993. Cluster analysis for hypertext systems. In Proceedings of the 16th Annual International ACM-SIGIR Conference on Research and Development in Information Retrieval, R. Korfhage, E. M. Rasmussen, and P. Willett, Eds. 116--125.]] Google Scholar
- Bui, T., Chaudhuri, S., Leighton, T., and Sipser, M. 1987. Graph bisection algorithms with good average case behavior. Combinatorica 7, 171--191.]] Google Scholar
- Bui, T. N. and Peck, A. 1992. Partitioning planar graphs. SIAM J. Comput. 21, 2, 203--215.]] Google Scholar
- Caprara, A., Malucelli, F., and Pretolani, D. 2002. On bandwidth-2 graphs. Discrete Applied Mathematics. 117, 1--13.]]Google Scholar
- Carson, T. and Impagliazzo, R. 2001. Hill climbing finds random planted bisections. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. 903--909.]] Google Scholar
- Chang, G. J. and Lai, Y.-L. 2001. On the profile of the corona of two graphs. Manuscript (provided by S. Bezrukov).]]Google Scholar
- Chinn, P., Chvátalová, J., Dewdney, A., and Gibbs, N. 1982. The bandwidth problem for graphs and matrices---A survey. Journal of Graph Theory 6, 223--254.]]Google Scholar
- Chinn, P. Z., Lin, Y. X., and Yuan, J. J. 1992. The bandwidth of the corona of two graphs. In Proceedings of the Twenty-third Southeastern International Conference on Combinatorics, Graph Theory, and Computing. Congressus Numerantium, vol. 91. Utilitas Math., 141--152.]]Google Scholar
- Chinn, P. Z., Lin, Y. X., Yuan, J. J., and Williams, K. 1995. Bandwidth of the composition of certain graph powers. Ars Combinatoria 39, 167--173.]]Google Scholar
- Chirravuri, S., Bhandarkar, S. M., and Arnold, J. 1996. Parallel computing of physical maps---A comparative study in SIMD and MIMD parallelism. Journal of Computational Biology 3, 4, 503--528.]]Google Scholar
- Chung, F. R. K. 1988. Labelings of Graphs. Academic Press, San Diego, 151--168.]]Google Scholar
- Chung, F. R. K., Leighton, F. T., and Rosenberg, A. L. 1987. Embedding graphs in books: a layout problem with applications to VLSI design. SIAM Journal on Algebraic and Discrete Methods 8, 1, 33--58.]] Google Scholar
- Chung, M., Makedon, F., Sudborough, I. H., and Turner, J. 1982. Polynomial time algorithms for the min cut problem on degree restricted trees. In Proceedings of the 23th Annual Symposium on Foundations of Computer Science. 262--271.]]Google Scholar
- Chvátalová, J. 1975. Optimal labelling of a product of two paths. Discrete Mathematics 11, 249--253.]]Google Scholar
- Chvátalová, J., Dewdney, A., Gibbs, N., and Korfhage, R. 1975. The bandwidth problem for graphs---A collection of recent results. Technical report CS 75020, Dept. of Computer Science, Southern Methodist University.]]Google Scholar
- Condon, A. and Karp, R. M. 2001. Algorithms for graph partitioning on the planted partition model. Random Structures & Algorithms 18, 2, 116--140.]] Google Scholar
- Crescenzi, P., Silvestri, R., and Trevisan, L. 2001. On weighted vs unweighted versions of combinatorial optimization problems. Information and Computation 167, 1, 10--26.]] Google Scholar
- Cuthill, E. H. and Mckee, J. 1969. Reducing the bandwidth of sparse symmetric matrices. In Proceedings of the 24th ACM National Conference. 157--172.]] Google Scholar
- Deo, N., Krishnamoorthy, M. S., and Langston, M. A. 1987. Exact and approximate solutions for the gate matrix layout problem. IEEE Transactions on Computer Aided Design 6, 1, 79--84.]]Google Scholar
- Dewdney, A. K. 1976. The bandwidth of a graph---some recent results. In Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory, and Computing. Number 17 in Congressus Numerantium. Utilitas Math., 273--288.]]Google Scholar
- Díaz, J. 1979. The Δ-operator. In Fundamentals of Computation Theory, L. Budach, Ed. Akademie--Verlag, 105--111.]]Google Scholar
- Díaz, J. 1992. Graph layout problems. In Mathematical Foundations of Computer Science 1992, I. M. Havel and V. Koubek, Eds. Lecture Notes in Computer Sciences, vol. 629. Springer--Verlag, 14--23.]] Google Scholar
- Díaz, J., Gibbons, A., Pantziou, G., Serna, M., Spirakis, P., and Torán, J. 1997a. Parallel algorithms for the minimum cut and the minimum length tree layout problems. Theoretical Computer Science 181, 2, 267--288.]] Google Scholar
- Díaz, J., Gibbons, A. M., Paterson, M. S., and Torán, J. 1991. The Minsumcut problem. In Algorithms and Data Structures, F. Dehen, R. J. Sack, and N. Santoro, Eds. Lecture Notes in Computer Science, vol. 519. Springer-Verlag, 65--79.]]Google Scholar
- Díaz, J., Penrose, M. D., Petit, J., and Serna, M. 2000. Convergence theorems for some layout measures on random lattice and random geometric graphs. Combinatorics, Probability and Computing 9, 6, 489--511.]] Google Scholar
- Díaz, J., Penrose, M. D., Petit, J., and Serna, M. 2001a. Approximating layout problems on random geometric graphs. J. Algorithms 39, 1, 78--116.]] Google Scholar
- Díaz, J., Petit, J., and Serna, M. 2001b. Faulty random geometric networks. Parallel Processing Letters 10, 4, 343--357.]]Google Scholar
- Díaz, J., Petit, J., Serna, M., and Trevisan, L. 2001c. Approximating layout problems on random graphs. Discrete Mathematics 235, 1--3, 245--253.]]Google Scholar
- Díaz, J., Serna, M., Spirakis, P., and Torán, J. 1997b. Paradigms for Fast Parallel Approximability. Cambridge University Press, Cambridge.]] Google Scholar
- Diekmann, R., Lüling, R., and Monien, B. 1994. Communication throughput of interconnection networks. In Mathematical Foundations of Computer Science 1994, I. Privara, B. Rovan, and P. Ruzicka, Eds. Lecture Notes in Computer Science, vol. 841. Springer--Verlag, 72--86.]] Google Scholar
- Diekmann, R., Lüling, R., Monien, B., and Spräner, C. 1996. Combining helpful sets and parallel simulated annealing for the graph-partitioning problem. Parallel Algorithms and Applications 8, 61--84.]]Google Scholar
- Diekmann, R., Monien, B., and Preis, R. 1995. Using helpful sets to improve graph bisections. In Interconnection Networks and Mapping and Scheduling Parallel Computations, D. F. Hsu, A. L. Rosenberg, and D. Sotteau, Eds. DIMACS Series in Discrete Mathematics and Theoretical Computer Science. AMS Press, 57--73.]]Google Scholar
- Diks, K., Djidjev, H., Sýroka, O., and Vr&tbreve;o, I. 1993. Edge separators for planar and outerplanar graphs with applications. Journal of Algorithms 14, 258--279.]] Google Scholar
- Ding, G. and Oporowski, B. 1995. Some results on tree decomposition of graphs. J. Graph Theory 20, 4, 481--499.]] Google Scholar
- Dinneen, M. J. 1995. Bounded cmbinatorial width and forbidden substructures. Ph.D. thesis, Computer Science Dept., University of Victoria.]] Google Scholar
- Downey, R. G. and Fellows, M. R. 1995. Fixed-parameter tractability and completeness II: On completeness for W{1}. Theoretical Computer Science 141, 1-2, 109--131.]] Google Scholar
- Downey, R. G. and Fellows, M. R. 1999. Parameterized Complexity. Springer-Verlag, New York.]]Google Scholar
- Dunagan, J. and Vempala, S. 2001. On Euclidean embeddings and bandwidth minimization. In Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques, M. Goemans, K. Jansen, J. Rolim, and L. Trevisan, Eds. Lecture Notes in Computer Science, vol. 2129. Springer-Verlag, 229--240.]] Google Scholar
- Ellis, J., Sudborough, I. H., and Turner, J. 1979. The vertex separation and search number of a graph. Information and Computation 113, 50--79.]] Google Scholar
- Elsner, U. 1997. Graph partitioning---A survey. Technical Report 393, Technische Universitat Chemnitz.]]Google Scholar
- Even, G., Naor, J., Rao, S., and Schieber, B. 1999. Fast approximate graphs algorithms. SIAM J. Comput. 28, 6, 2187--2214.]] Google Scholar
- Even, G., Naor, J., Rao, S., and Schieber, B. 2000. Divide-and-conquer approximation algorithms via spreading metrics. J. ACM 47, 4, 585--616.]] Google Scholar
- Even, S. and Itai, A. 1971. Queues, stacks, and graphs. In Theory of Machines and Computations. Academic Press, 71--86.]]Google Scholar
- Even, S. and Shiloach, Y. 1975. NP-completeness of several arrangement problems. Technical Report TR-43, Dept. of Computer Science, Technion, Haifa.]]Google Scholar
- Everstine, G. C. 1979. A comparison of three resequencing algorithms for the reduction of matrix profile and wavefront. Int. J. Num. Meth. Eng. 14, 837--853.]]Google Scholar
- Feige, U. 2000. Approximating the bandwidth via volume respecting embeddings. J. Comput. Syst. Sci. 60, 3, 510--539.]] Google Scholar
- Feige, U. and Krauthgamer, R. 1998. Improved performance guarantees for bandwidth minimization heuristics (draft). Technical Report, Computer Science Dept., Weizmann Inst. Tech.]]Google Scholar
- Feige, U. and Krauthgamer, R. 2002. A polylogarithmic approximation of the minimum bisection. SIAM J. Comput., To appear.]] Google Scholar
- Feige, U., Krauthgamer, R., and Nissim, K. 2002. Approximating the minimum bisection size. Discrete Applied Mathematics.]]Google Scholar
- Fellows, M. R., Hallet, M. T., and Wareham, W. T. 1993. DNA physical mapping: Three ways difficult. In Algorithms-ESA'93, T. Lengauer, Ed. Number 726 in Lecture Notes in Computer Science. Springer-Verlag, 157--168.]] Google Scholar
- Fellows, M. R. and Langston, M. A. 1988. Layout permutation problems and well-partially-ordered sets. In Advanced Research in VLSI. MIT Press, Cambridge, MA, 315--327.]] Google Scholar
- Fellows, M. R. and Langston, M. A. 1992. On well-partial-order theory and its application to combinatorial problems of VLSI design. SIAM J. Discrete Mathem. 5, 1, 117--126.]] Google Scholar
- Fellows, M. R. and Langston, M. A. 1994. On search, decision, and the efficiency of polynomial-time algorithms. J. Comput. Syst. Sci. 49, 3, 769--779.]] Google Scholar
- Fishburn, P., Tetali, P., and Winkler, P. 2000. Optimal linear arrangement of a rectangular grid. Discrete Mathematics 213, 123--139.]] Google Scholar
- Ford, L. R. and Fulkerson, D. R. 1962. Flows in Networks. Princeton University Press.]]Google Scholar
- Frieze, A. and Kannan, R. 1996. The regularity lemma and approximation schemes for dense problems. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science. 12--20.]] Google Scholar
- Gallian, J. 1998. A dynamic survey of graph labeling. Electronic Journal of Combininatorics 5, 1.]]Google Scholar
- Garey, M. R., Graham, R. L., Johnson, D. S., and Knuth, D. 1978. Complexity results for bandwidth minimization. SIAM J. Appl. Mathem. 34, 477--495.]]Google Scholar
- Garey, M. R. and Johnson, D. S. 1979. Computers and Intractability. A Guide to the Theory of NP-Completeness. Freeman and Company, New York.]] Google Scholar
- Garey, M. R., Johnson, D. S., Miller, G. L., and Papadimitriou, C. H. 1980. The complexity of coloring circular arcs and chords. SIAM J. Algeb. Discrete Meth. 1, 2, 216--227.]]Google Scholar
- Garey, M. R., Johnson, D. S., and Stockmeyer, L. 1976. Some simplified NP-complete graph problems. Theoretical Computer Science 1, 237--267.]]Google Scholar
- Gavril, F. 1977. Some NP-complete problems on graphs. In 11th Conference on Information Sciences and Systems. John Hopkins University, Baltimore, 91--95.]]Google Scholar
- Gibbs, N. E., Poole, Jr., W. G., and Stockmeyer, P. K. 1976. An algorithm for reducing the bandwidth and profile of a sparse matrix. SIAM J. Num. Anal. 13, 2, 236--250.]]Google Scholar
- Glover, F. and Laguna, M. 1997. Tabu Search, second ed. Kluwer, Boston.]] Google Scholar
- Goldberg, M. and Miller, Z. 1988. A parallel algorithm for bisection width in trees. Computers & Mathematics with Applications 15, 4, 259--266.]]Google Scholar
- Goldberg, M. K. and Klipker, I. A. 1976. An algorithm for minimal numeration of tree vertices. Sakharth. SSR Mecn. Akad. Moambe 81, 3, 553--556. In Russian.]]Google Scholar
- Goldberg, P. W., Golumbic, M. C., Kaplan, H., and Shamir, R. 1995. Four strikes against physical mapping of DNA. J. Comput. Biol. 2, 1, 139--152.]]Google Scholar
- Golovach, P. A. 1997. The total vertex separation number of a graph. Diskretnaya Matematika 9, 4, 86--91. In Russian.]]Google Scholar
- Golovach, P. A. and Fomin, F. V. 1998. The total vertex separation number and the profile of graphs. Diskretnaya Matematika 10, 1, 87--94. In Russian.]]Google Scholar
- Golumbic, M. C. 1980. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York.]] Google Scholar
- Golumbic, M. C., Kaplan, H., and Shamir, R. 1994. On the complexity of DNA physical mapping. Advances in Applied Mathematics 15, 203--215.]] Google Scholar
- Golumbic, M. C., Kaplan, H., and Shamir, R. 1995. Graph sandwich problems. J. Algor. 19, 449--473.]] Google Scholar
- Golumbic, M. C. and Shamir, R. 1993. Complexity and algorithms for reasoning about time: A graph theoretical approach. J. ACM 40, 1108--1113.]] Google Scholar
- Gomory, R. E. and Hu, T. C. 1975. Multi-Terminal Flows in a Network. Studies in Mathematics, vol. 11. MAA, 172--199.]]Google Scholar
- Greenlaw, R., Hoover, H. J., and Ruzzo, W. L. 1995. Limits to Parallel Computation: P-Completeness Theory. Oxford University Press, New York.]] Google Scholar
- Grimmett, G. R. 1999. Percolation, second ed. Springer-Verlag, Heidelberg.]]Google Scholar
- Gupta, A. 2001. Improved bandwidth approximation for trees and chordal graphs. J. Algor. 40, 1, 24--36.]] Google Scholar
- Gurari, E. and Sudborough, I. H. 1984. Improved dynamic programming algorithms for the bandwidth minimization and the mincut linear arrangement problem. J. Algor. 5, 531--546.]]Google Scholar
- Gustedt, J. 1993. On the pathwidth of chordal graphs. Discrete Applied Mathematics 45, 3, 233--248.]] Google Scholar
- Hager, W. W. 2002. Minimizing the profile of a symmetric matrix. SIAM J. Sci. Comput. 23, 5, 1799--1816.]] Google Scholar
- Hansen, M. D. 1989. Approximation algorithms for geometric embeddings in the plane with applications to parallel processing problems. In 30th Annual Symposium on Foundations of Computer Science. 604--609.]]Google Scholar
- Haralambides, J. and Makedon, F. 1997. Approximation algorithms for the bandwidth minimization problem for a large class of trees. Theory of Computing Systems 30, 67--90.]]Google Scholar
- Haralambides, J., Makedon, F., and Monien, B. 1991. Bandwidth minimization: an approximation algorithm for caterpillars. Mathematical Systems Theory 24, 169--177.]]Google Scholar
- Harary, F. 1967. Problem 16. In Graph Theory and Computing, M. Fiedler, Ed. Czechoslovak Academy Sciences, 161.]]Google Scholar
- Harper, L. H. 1964. Optimal assignments of numbers to vertices. J. SIAM 12, 1, 131--135.]]Google Scholar
- Harper, L. H. 1966. Optimal numberings and isoperimetric problems on graphs. J. Combinatorial Theory 1, 3, 385--393.]]Google Scholar
- Harper, L. H. 1970. Chassis layout and isoperimetric problems. Technical Report SPS 37--66, vol II, Jet Propulsion Laboratory.]]Google Scholar
- Harper, L. H. 1977. Stabilization and the edgesum problem. Ars Combinatoria 4, 225--270.]]Google Scholar
- Harper, L. H. 2001. On the bandwidth of a hamming graph. Manuscript.]]Google Scholar
- Heath, L. S., Leighton, F. T., and Rosenberg, A. L. 1992. Comparing queues and stacks as mechanisms for laying out graphs. SIAM J. Discrete Mathem. 5, 3, 398--412.]] Google Scholar
- Heath, L. S. and Pemmaraju, S. V. 1997. Stack and queue layouts of posets. SIAM J. Discrete Mathem. 10, 4, 599--625.]] Google Scholar
- Heath, L. S. and Pemmaraju, S. V. 1999. Stack and queue layouts of directed acyclic graphs. II. SIAM J. Comput. 28, 5, 1588--1626.]] Google Scholar
- Heath, L. S., Pemmaraju, S. V., and Ribbens, C. J. 1993. Sparse Matrix-Vector Multiplication on a Small Linear Array. Springer-Verlag.]]Google Scholar
- Heath, L. S., Pemmaraju, S. V., and Trenk, A. N. 1999. Stack and queue layouts of directed acyclic graphs. I. SIAM J. Comput. 28, 4, 1510--1539.]] Google Scholar
- Heath, L. S. and Rosenberg, A. L. 1992. Laying out graphs using queues. SIAM J. Comput. 21, 5, 927--958.]] Google Scholar
- Heckmann, R., Klasing, R., Monien, B., and Unger, W. 1998. Optimal embedding of complete binary trees into lines and grids. J. Parallel and Distributed Computing 49, 1, 40--56.]] Google Scholar
- Helmberg, C., Rendl, F., Mohar, B., and Poljak, S. 1995. A spectral approach to bandwidth and separator problems in graphs. Linear and Multilinear Algebra 39, 1-2, 73--90.]]Google Scholar
- Hendrich, U. and Stiebitz, M. 1992. On the bandwidth of graph products. J. Inform. Proc. Cybernetics 28, 113--125.]] Google Scholar
- Hendrickson, B. and Leland, R. 1997. The Chaco user's guide: version 2.0. Technical Report SAND94--2692, Sandia National Laboratories. ftp://ftp.cs.sandia.gov/pub/papers/bahendr/guide.ps.gz.]]Google Scholar
- Hromkovi&cbreve;, J. and Monien, B. 1992. The Bisection Problem for Graphs of Degree 4 (Configuring Transputer Systems). Teubner, Stuttgart, 215--233.]]Google Scholar
- Hu, T. C. 1974. Optimum communication spanning trees. SIAM J. Comput. 3, 188--195.]]Google Scholar
- Janson, S., Luczak, T., and Rucinski, A. 2000. Random Graphs. Wiley, New York.]]Google Scholar
- Jerrum, M. and Sorkin, G. 1998. The Metropolis algorithm for graph bisection. Discrete Applied Mathematics 82, 1-3, 155--175.]] Google Scholar
- Johnson, D. S., Aragon, C. R., McGeoch, L. A., and Schevon, C. 1989. Optimization by simulated annealing: an experimental evaluation; part I, graph partitioning. Operations Research 37, 6, 865--892.]] Google Scholar
- Johnson, D. S., Lenstra, J. K., and Kan, A. H. G. R. 1978. The complexity of the network design problem. Networks 8, 4, 279--285.]]Google Scholar
- Juels, A. 1996. Topics in black-box combinatorial optimization. Ph.D. thesis, University of California at Berkeley.]] Google Scholar
- Juvan, M. and Mohar, B. 1992. Optimal linear labelings and eigenvalues of graphs. Discrete Applied Mathematics 36, 2, 153--168.]] Google Scholar
- Kadluczka, P. and Wala, K. 1995. Tabu search and genetic algorithms for the generalized graph partitioning problem. Control and Cybernetics 24, 4, 459--476.]]Google Scholar
- Kaplan, H. and Shamir, R. 1996. Pathwidth, bandwidth and completion problems to proper interval graphs with small cliques. SIAM J. Comput. 25, 3, 540--561.]] Google Scholar
- Kaplan, H. and Shamir, R. 1999. Bounded degree interval sandwich problems. Algorithmica 24, 2, 96--104.]]Google Scholar
- Kaplan, H., Shamir, R., and Tarjan, R. E. 1999. Tractability of parameterized completion problems on chordal, strongly chordal, and proper interval graphs. SIAM J. Comput. 28, 5, 1906--1922.]] Google Scholar
- Karger, D. R. 1999. A randomized fully polynomial time approximation scheme for the all-terminal network reliability problem. SIAM J. Comput. 29, 2, 492--514.]] Google Scholar
- Karp, R. M. 1993. Mapping the genome: some combinatorial problems arising in molecular biology. In Proceedings of the 25th Annual ACM Symposium on the Theory of Computing. 278--285.]] Google Scholar
- Karpinski, M., Wirtgen, J., and Zelikovsky, A. 1997. An approximating algorithm for the bandwidth problem on dense graphs. Technical Report TR 97-017, Electronic Colloquium on Computational Complexity.]]Google Scholar
- Karypis, G. 2001. Metis's home page. Web page. http://www-users.cs.umn.edu/∼karypis/metis.]]Google Scholar
- Kendall, D. G. 1969. Incidence matrices, interval graphs, and seriation in archeology. Pacific J. Mathem. 28, 565--570.]]Google Scholar
- Kernighan, B. W. and Lin, S. 1970. An efficient heuristic procedure for partitioning graphs. Bell System Technical Journal 49, 291--307.]]Google Scholar
- King, I. P. 1970. An automatic reordering schema for simultaneous equations derived from network system. Int. J. Numer. Meth. Eng. 2, 523--533.]]Google Scholar
- Kinnersley, N. G. 1992. The vertex separation number of a graph equals its path-width. Information Processing Letters 42, 6, 345--350.]] Google Scholar
- Kirousis, L. M. and Papadimitriou, C. H. 1986. Searching and pebbling. Theoretical Computer Science 47, 205--216.]] Google Scholar
- Klasing, R. 1998. The relationship between the gossip complexity in vertex-disjoint paths mode and the vertex bisection width. Discrete Applied Mathematics 83, 229--246.]] Google Scholar
- Kleitman, D. J. and Vohra, R. V. 1990. Computing the bandwidth of interval graphs. SIAM J. Discrete Mathem. 3, 3, 373--375.]] Google Scholar
- Kloks, T., Kratsch, D., and Müller, H. 1998. Bandwidth of chain graphs. Information Processing Letters 68, 6, 313--315.]] Google Scholar
- Kloks, T., Kratsch, D., and Müller, H. 1999. Approximating the bandwidth for asteroidal triple-free graphs. J. Algor. 32, 1, 41--57.]]Google Scholar
- Kratsch, D. 1987. Finding the minimum bandwidth of an interval graph. Information and Computation 74, 2, 140--158.]] Google Scholar
- Kumfert, G. and Pothen, A. 1997. Two improved algorithms for reducing the envelope and wavefront. BIT 37, 3, 001--032.]]Google Scholar
- Kuo, D. and Chang, G. J. 1994. The profile minimization problem in trees. SIAM J. Comput. 23, 71--81.]] Google Scholar
- Lai, Y.-L. 1997. Bandwidth, edgesum and profile of graphs. Ph.D. thesis, Dept. of Computer Science, Western Michigan Univ.]] Google Scholar
- Lai, Y.-L. 2001. On the profile of the tensor product of path with complete bipartite graphs. Manuscript (provided by S. Bezrukov).]]Google Scholar
- Lai, Y.-L., Liu, J., and Williams, K. 1994. Bandwidth for the sum of k graphs. Ars Combinatoria 37, 149--155.]]Google Scholar
- Lai, Y.-L. and Williams, K. 1994. The edgesum of the sum of k sum deterministic graphs. In Proceedings of the Twenty-fifth Southeastern International Conference on Combinatorics, Graph Theory and Computing. Congressus Numerantium, vol. 102. Utilitas Math., 231--236.]]Google Scholar
- Lai, Y.-L. and Williams, K. 1995. Bandwidth of the strong product of paths and cycles. In Proceedings of the Twenty-sixth Southeastern International Conference on Combinatorics, Graph Theory and Computing. Congressus Numerantium, vol. 109. Utilitas Math., 123--128.]]Google Scholar
- Lai, Y.-L. and Williams, K. 1997. On bandwidth for the tensor product of paths and cycles. Discrete Applied Mathematics. 73, 2, 133--141.]] Google Scholar
- Lai, Y.-L. and Williams, K. 1999. A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs. J. Graph Theory 31, 2, 75--94.]]Google Scholar
- Lang, K. and Rao, S. 1993. Finding near-optimal cuts: An empirical evaluation. In Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms. 212--221.]] Google Scholar
- Leighton, F. T. 1993. Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann, San Mateo.]] Google Scholar
- Leighton, T. and Rao, S. 1999. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM 46, 6, 787--832.]] Google Scholar
- Leiserson, C. E. 1980. Area-efficient graph layouts (for VLSI). In Proceedings of the 21st Annual Symposium on Foundations of Computer Science. 270--281.]]Google Scholar
- Leland, R. and Hendrickson, B. 1994. An empirical study of static load balancing algorithms. In Scalable High-Performance Computing Conference. IEEE Computer Society Press, 682--685.]]Google Scholar
- Lengauer, T. 1981. Black-white pebbles and graph separation. Acta Informatica 16, 465--475.]]Google Scholar
- Lengauer, T. 1982. Upper and lower bounds on the complexity of the min-cut linear arrangements problem on trees. SIAM J. Algeb. Discrete Meth. 3, 99--113.]]Google Scholar
- Lepin, V. V. 1986. Profile minimization problem of matrices and graphs. Academy of Sciences of Belarus. Institute of Mathematics. 33, 269. In Russian.]]Google Scholar
- Lewis, R. 1994. Simulated annealing for profile and fill reduction of sparse matrices. Int. J. Num. Meth. Eng. 37, 6.]]Google Scholar
- Lin, Y. X. 1994. Two-dimensional bandwidth problem. In Combinatorics, Graph Theory, Algorithms and Applications (Beijing, 1993). World Sci. Publishing, 223--232.]]Google Scholar
- Lin, Y. X. and Yuan, J. 1994a. Profile minimization problem for matrices and graphs. Acta Mathematicae Applicatae Sinica. English Series 10, 1, 107--112.]]Google Scholar
- Lin, Y. X. and Yuan, J. J. 1994b. Profile minimization problem for matrices and graphs. Acta Mathematicae Applicatae Sinica. English Series. Yingyong Shuxue Xuebao 10, 1, 107--112.]]Google Scholar
- Lindsey, J. H. 1964. Assignments of numbers to vertices. American Mathematical Monthly 71, 508--516.]]Google Scholar
- Lipton, R. J. and Tarjan, R. E. 1979. A separator theorem for planar graphs. SIAM J. Appl. Mathem. 36, 177--189.]]Google Scholar
- Liu, H. E. and Yuan, J. J. 1995. The cutwidth problem for graphs. Gaoxiao Yingyong Shuxue Xuebao. Applied Mathematics. A Journal of Chinese Universities. Series A 10, 3, 339--348. In Chinese.]]Google Scholar
- Liu, J. 1992. On bandwidth sum for the composition of paths and cycles. Technical Report Rep/92-06, Dept. of Computer Science, Western Michigan Univ.]]Google Scholar
- Liu, J. and Williams, K. 1995. On bandwidth and edgesum for the composition of two graphs. Discrete Mathematics 143, 1-3, 159--166.]] Google Scholar
- Luczak, M. L. and McDiarmid, C. 2001. Bisecting sparse random graph. Random Structures & Algorithms 18, 31--38.]] Google Scholar
- MacGregor, R. M. 1978. On partitioning a graph: a theoretical and empirical study. Ph.D. thesis, University of California, Berkeley.]] Google Scholar
- Mahesh, R., Rangan, C. P., and Srinivasan, A. 1991. On finding the minimum bandwidth of interval graphs. Information and Computation 95, 2, 218--224.]] Google Scholar
- Mai, J. H. 1996. Profiles of some classes of condensable graphs. J. Syst. Sci. Mathem. Sci. Xitong Kexue yu Shuxue 16, 2, 141--148.]]Google Scholar
- Mai, J. H. and Luo, H. P. 1984. Some theorems on the bandwidth of a graph. Acta Mathematicae Applicatae Sinica. Yingyong Shuxue Xuebao 7, 1, 86--95.]]Google Scholar
- Makedon, F., Papadimitriou, C. H., and Sudborough, I. H. 1985. Topological bandwidth. SIAM J. Algeb. Discrete Meth. 6, 3, 418--444.]]Google Scholar
- Makedon, F., Sheinwald, D., and Wolfsthal, Y. 1993. A simple linear-time algorithm for the recognition of bandwidth-2 biconnected garphs. Information Processing Letters 46, 103--107.]] Google Scholar
- Makedon, F. and Sudborough, I. H. 1989. On minimizing width in linear layouts. Discrete Applied Mathematics 23, 3, 243--265.]] Google Scholar
- Manabe, Y., Hagihara, K., and Tokura, N. 1984. The minimum bisection widths of the cube-connected cycles graph and cube graph. Systems-Computers-Controls. The Transactions of the Institute of Electronics and Communication Engineers of Japan 15, 6, 9--18.]]Google Scholar
- Miller, Z. 1991. Multidimensional bandwidth in random graphs. In Graph Theory, Combinatorics, and Applications. Vol. 2 (Kalamazoo, MI, 1988). Wiley, New York, 861--870.]]Google Scholar
- Mitchison, G. and Durbin, R. 1986. Optimal numberings of an n × n array. SIAM J. Algeb. Discrete Meth. 7, 4, 571--582.]] Google Scholar
- Mohar, B. and Poljak, S. 1993. Eigenvalues in combinatorial optimization. In Combinatorial and Graph-Theoretical Problems in Linear Algebra, R. A. Brualdi, S. Friedland, and V. Klee, Eds. IMA Volumes in Mathematics and its Applications, vol. 50. Springer-Verlag, 107--151.]]Google Scholar
- Monien, B. 1986. The bandwidth minimization problem for caterpillars with hair length 3 is NP-complete. SIAM J. Algeb. Discrete Meth. 7, 4, 505--512.]] Google Scholar
- Monien, B. and Sudborough, I. H. 1988. Min Cut is NP-complete for edge weighted trees. Theoretical Computer Science 58, 1-3, 209--229.]] Google Scholar
- Monien, B. and Sudborough, I. H. 1990. Embedding one interconnection network in another. In Computational Graph Theory, G. Tinhofer, E. Mayr, H. Noltemeier, and M. M. Syslo, Eds. Computing Supplementa, vol. 7. Springer-Verlag, 257--282.]]Google Scholar
- Muradyan, D. 1999. Proceedings of Computer Science & Information Technologies Conference, Armenia.]]Google Scholar
- Muradyan, D. O. 1982. Minimal numberings of a two-dimensional cylinder. Akademiya Nauk Armyanskoĭ SSR. Doklady 75, 3, 114--119. In Russian.]]Google Scholar
- Muradyan, D. O. 1985. Some estimates for the length of an arbitrary graph. Mat. Voprosy Kibernet. Vychisl. Tekhn.14, 79--86, 126. In Russian.]]Google Scholar
- Muradyan, D. O. 1986. A polynomial algorithm for finding the bandwidth of interval graphs. Akademiya Nauk Armyanskoĭ SSR. Doklady 82, 2, 64--66. In Russian.]]Google Scholar
- Muradyan, D. O. and Piliposyan, T. E. 1980. Minimal numberings of vertices of a rectangular lattice. Akad. Nauk. Armjan. SRR 1, 70, 21--27. In Russian.]]Google Scholar
- Muradyan, D. O. and Piliposyan, T. E. 1980. The problem of finding the length and width of the complete p-partite graph. Uchen. Zapiski Erevan. Gosunivers. 2, 18--26. In Russian.]]Google Scholar
- Mutzel, P. 1995. A polyhedral approach to planar augmentation and related problems. In Algorithms---ESA'95, P. Spirakis, Ed. Lecture Notes in Computer Science, vol. 979. Springer-Verlag, 497--507.]] Google Scholar
- Nakano, K. 1994. Linear layouts of generalized hypercubes. In Graph-Theoretic Concepts in Computer Science, J. van Leeuwen, Ed. Lecture Notes in Computer Science, vol. 790. Springer-Verlag, 364--375.]] Google Scholar
- Niepel, L. and Tomasta, P. 1981. Elevation of a graph. Czechoslovak Mathematical Journal 31(106), 3, 475--483.]]Google Scholar
- Papadimitriou, C. 1976. The NP-completeness of the bandwidth minimization problem. Computing 16, 263--270.]]Google Scholar
- Papadimitriou, C. H. and Sideri, M. 1996. The bisection width of grid graphs. Mathematical Systems Theory 29, 2, 97--110.]]Google Scholar
- Penrose, M. 1995. Single linkage clustering and continuum percolation. J. Multivariate Anal. 53, 94--109.]] Google Scholar
- Penrose, M. 2000. Vertex ordering and partitioning problems for random spatial graphs. The Annals of Applied Probability 10, 517--538.]]Google Scholar
- Petit, J. 1998. Approximation heuristics and benchmarkings for the MinLA problem. In Alex '98---Building Bridges Between Theory and Applications, R. Battiti and A. Bertossi, Eds. 112--128.]]Google Scholar
- Petit, J. 2000. Combining spectral sequencing and parallel simulated annealing for the minLA problem. Technical Report LSI-01-13-R, Departament de Llenguatges i Sistemes Informàtics, Universitat Politècnica de Catalunya.]]Google Scholar
- Petit, J. 2001a. Experiments for the MinLAP problem. Technical Report LSI-R01-7-R, Departament de Llenguatges i Sistemes Informàtics, Universitat Politècnica de Catalunya.]]Google Scholar
- Petit, J. 2001b. Layout problems. Ph.D. thesis, Universitat Politècnica de Catalunya.]]Google Scholar
- Preis, R. and Diekmann, R. 1996. The Party partitioning library user guide. Technical Report TR-RSFB-96-024, Universität Paderborn.]]Google Scholar
- Rao, S. and Richa, A. W. 1998. New approximation techniques for some ordering problems. In Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms. 211--218.]] Google Scholar
- Raspaud, A., Sýkora, O., and Vr&tbreve;o, I. 1995. Cutwidth of the de Bruijn graph. RAIRO Informatique Théorique et Applications 29, 6, 509--514.]]Google Scholar
- Raspaud, A., Sýkora, O., and Vr&tbreve;o, I. 2000. Congestion and dilation, similarities and differences---a survey. In Proceedings 7th International Colloquium on Structural Information and Communication Complexity. Carleton Scientific, 269--280.]]Google Scholar
- Ravi, R., Agrawal, A., and Klein, P. 1991. Ordering problems approximated: single-processor scheduling and interval graph completition. In Automata, Languages and Programming, J. Leach, B. Monien, and M. Rodriguez, Eds. Lecture Notes in Computer Science, vol. 510. Springer-Verlag, 751--762.]] Google Scholar
- Robertson, N. and Seymour, P. D. 1985. Graph minors---a survey. In Surveys in Combinatorics. Cambridge University Press, 153--171.]]Google Scholar
- Rolim, J., Sýkora, O., and Vr˘to, I. 1995. Optimal cutwidths and bisection widths of 2- and 3-dimensional meshes. In Graph Theoretic Concepts in Computer Science. Lecture Notes in Computer Science, vol. 1017. Springer, 252--264.]] Google Scholar
- Rolim, J., Tvrdík, J., Trdli&cbreve;ka, J., and Vr&tbreve;o, I. 1998. Bisecting de Bruijn and Kautz graphs. Discrete Applied Mathematics 85, 87--97.]] Google Scholar
- Saad, Y. 1996. Iterative Methods for Sparse Linear Systems. PWS Publishing Company, Boston.]] Google Scholar
- Saxe, J. B. 1980. Dynamic-programming algorithms for recognizing small-bandwidth graphs in polynomial time. SIAM J. Algeb. Discrete Meth. 1, 4, 363--369.]]Google Scholar
- Seymour, P. D. 1995. Packing directed circuits fractionally. Combinatorica 15, 2, 281--288.]]Google Scholar
- Seymour, P. D. and Thomas, R. 1994. Call routing and the ratcatcher. Combinatorica 14, 2, 217--241.]]Google Scholar
- Shahrokhi, F., Sýkora, O., Székely, L. A., and Vr&tbreve;o, I. 1997. Crossing numbers: bounds and applications. János Bolyai Math. Soc., Budapest, 179--206.]]Google Scholar
- Shahrokhi, F., Sýkora, O., Székely, L. A., and Vr&tbreve;o, I. 2001. On bipartite drawings and the linear arrangement problem. SIAM J. Comput. 30, 6, 1773--1789.]] Google Scholar
- Shiloach, Y. 1979. A minimum linear arrangement algorithm for undirected trees. SIAM J. Comput. 8, 1, 15--32.]]Google Scholar
- Shing, M. T. and Hu, T. C. 1986. Computational complexity of layout problems. In Layout Design and Verification, T. Ohtsuki, Ed. Advances in CAD for VLSI, vol. 4. North--Holland, Amsterdam, 267--294.]]Google Scholar
- Simon, H. D. and Teng, S.-H. 1997. How good is recursive bisection? SIAM J. Sci. Comput. 18, 5, 1436--1445.]] Google Scholar
- Skodinis, K. 2000. Computing optimal linear layouts of trees in linear time. In Algorithms---ESA 2000, M. Paterson, Ed. Lecture Notes in Computer Science, vol. 1879. Springer-Verlag, 403--414.]] Google Scholar
- Soumyanath, K. and Deogun, J. S. 1990. On the bisection width of partial k-trees. In Proceedings of the Twentieth Southeastern Conference on Combinatorics, Graph Theory, and Computing. Congressus Numerantium, vol. 74. Utilitas Math., 25--37.]]Google Scholar
- Spielman, D. A. and Teng, S.-H. 1996. Spectral partitioning works: Planar graphs and finite element meshes. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science. 96--105.]] Google Scholar
- Sprague, A. P. 1994. An O(n log n) algorithm for bandwidth of interval graphs. SIAM J. Discrete Mathem. 7, 2, 213--220.]] Google Scholar
- Stacho, L. and Vr&tbreve;o, I. 1998. Bisection width of transposition graphs. Discrete Applied Mathematics 84, 1-3, 221--235.]] Google Scholar
- Sýkora, O. and Vr&tbreve;o, I. 1993. Edge separators for graphs of bounded genus with applications. Theoretical Computer Science 112, 419--429.]] Google Scholar
- Tewarson, R. 1973. Sparse Matrices. Academic Press, New York.]]Google Scholar
- Thilikos, D. M., Serna, M. J., and Bodlaender, H. L. 2000. Constructive linear time algorithms for small cutwidth and carving-width. In ISAAC 2000 Algorithms and Computation, D. T. Lee and S.-H. Teng, Eds. Lecture Notes in Computer Science, vol. 1969. Springer-Verlag, 192--203.]] Google Scholar
- Thilikos, D. M., Serna, M. J., and Bodlaender, H. L. 2001. A polynomial time algorithm for the cutwidth of bounded degree graphs with small treewidth. In Algorithms, ESA 2001, F. Meyer auf der Heide, Ed. Lecture Notes in Computer Science, vol. 2161. Springer-Verlag, 380--390.]] Google Scholar
- Thompson, C. D. 1979. Area-time complexity in VLSI design. In Proceedings of the 11th Annual ACM Symposium on the Theory of Computing. 81--88.]] Google Scholar
- Turner, J. S. 1986. On the probable performance of heuristics for bandwidth minimization. SIAM J. Comput. 15, 2, 561--580.]] Google Scholar
- Unger, W. 1998. The complexity of the approximation of the bandwidth problem. In 37th Annual Symposium on Foundations of Computer Science. 82--91.]] Google Scholar
- Vazirani, V. V. 2001. Approximation Algorithms. Springer, Berlin.]] Google Scholar
- Vr&tbreve;o, I. 2000. Cutwidth of the r-dimensional mesh of d-ary trees. RAIRO Informatique Théorique et Applications 34, 6, 515--519.]]Google Scholar
- Vr&tbreve;o, I. 2002. Crossing numbers of graphs: A bibliography. ftp://ftp.ifi.savba.sk/pub/imrich/crobib.ps.gz.]]Google Scholar
- Williams, K. 1993. On the minimum sum of the corona of two graphs. In Proceedings of the Twenty-fourth Southeastern International Conference on Combinatorics, Graph Theory, and Computing. Congressus Numerantium, vol. 94. Utilitas Math., 43--49.]]Google Scholar
- Williams, K. 1994. On bandwidth and edgesum for the tensor product of paths with complete bipartite graphs. In Proceedings of the Twenty-fifth Southeastern International Conference on Combinatorics, Graph Theory and Computing. Congressus Numerantium, vol. 102. Utilitas Math., 183--190.]]Google Scholar
- Williams, K. 1996. On bandwidth for the tensor product of paths and cycles with complete graphs. Bulletin of the Institute of Combinatorics and its Applications 16, 41--48.]]Google Scholar
- Wu, B. Y., Lancia, G., Bafna, V., Chao, K.-M., Ravi, R., and Tang, C. Y. 1999. A polynomial time approximation scheme for minimum routing cost spanning trees. SIAM J. Comput. 29, 3, 761--778.]] Google Scholar
- Yannakakis, M. 1985. A polynomial algorithm for the min-cut linear arrangement of trees. J. ACM 32, 4, 950--988.]] Google Scholar
- Yuan, J., Lin, Y., Liu, Y., and Wang, S. 1998. NP-completeness of the profile problem and the fill-in problem on cobipartite graphs. J. Mathem. Study 31, 3, 239--243.]]Google Scholar
- Zhou, S. and Yuan, J. 1998. Harper-type lower bounds and the bandwidths of the compositions of graphs. Discrete Mathematics 181, 1-3, 255--266.]] Google Scholar
Recommendations
The Complexity of König Subgraph Problems and Above-Guarantee Vertex Cover
A graph is König-Egerváry if the size of a minimum vertex cover equals that of a maximum matching in the graph. These graphs have been studied extensively from a graph-theoretic point of view. In this paper, we introduce and study the algorithmic ...
Heuristic methods for graph coloring problems
SAC '05: Proceedings of the 2005 ACM symposium on Applied computingIn this work, the Graph Coloring Problem and its generalizations - the Bandwidth Coloring Problem, the Multicoloring Problem and the Bandwidth Multicoloring Problem - are studied. A Squeaky Wheel Optimization with Tabu Search heuristic is developed and ...
Equimatchable Graphs on Surfaces
A graph G is equimatchable if each matching in G is a subset of a maximum-size matching and it is factor critical if G-v has a perfect matching for each vertex v of G. It is known that any 2-connected equimatchable graph is either bipartite or factor ...
Comments