1 2@article{and90-random, 3 author="S. L. Anderson", 4 title="Random number generators on vector supercomputers 5 and other advanced architectures", 6 journal="SIAM Review", 7 volume="32", 8 year="1990", 9 pages="221-251"} 10 11@misc{ash97-utah, 12 AUTHOR="C. Ashcraft and S. C. Eisenstat and J. W. H. Liu", 13 title="Practical extensions of the multisection ordering for 14 sparse matrices", 15 howpublished="Minisymposium presentation at 16 the Sixth SIAM Conference on Applied Linear Algebra, 17 Snowbird, Utah", 18 year="October 29, 1997"} 19 20@misc{ash94-utah, 21 AUTHOR="C. Ashcraft and J. W. H. Liu", 22 title="Generalized nested dissection: some recent progress", 23 howpublished="Minisymposium presentation at 24 the Fifth SIAM Conference on Applied Linear Algebra, 25 Snowbird, Utah", 26 year="June 18, 1994"} 27 28@misc{rot96-balance, 29 AUTHOR="E. Rothberg", 30 title="Exploring the tradeoff between imbalance and separator 31 size in nested dissection ordering", 32 howpublished="unpublished", 33 year="1996"} 34 35@misc{ro95-hybrid, 36 AUTHOR="E. Rothberg", 37 title="Robust ordering of sparse matrices: a minimum degree, 38 nested dissection hybrid", 39 howpublished="unpublished", 40 year="1995"} 41 42@misc{rothberg95, 43 AUTHOR="E. Rothberg", 44 howpublished="private communication", 45 year="1995"} 46 47@conference{rot96-mindefIdaho, 48 author="E. Rothberg", 49 title="Ordering sparse matrices 50 using approximate minimum local fill", 51 booktitle="Second SIAM Conference on Sparse Matrices", 52 year="1996", 53 note="Conference presentation"} 54 55@techreport{hr96-msndtalk, 56 author="B. Hendrickson and E. Rothberg", 57 title="Improving the runtime and quality of nested dissection 58 ordering", 59 booktitle="Second SIAM Conference on Sparse Matrices", 60 year="1996", 61 note="Conference presentation"} 62 63@conference{ng96-mindefIdaho, 64 author="E. Ng and P. Raghavan", 65 title="Minimum deficiency ordering", 66 booktitle="Second SIAM Conference on Sparse Matrices", 67 year="1996", 68 note="Conference presentation"} 69 70@article{gib76-profile, 71 AUTHOR = {N. E. Gibbs and W. G. Poole Jr and P. K. Stockmeyer}, 72 JOURNAL = {SIAM. J. Numer. Anal.}, 73 KEY = {LLt band profile}, 74 PAGES = {236-250}, 75 TITLE = {An algorithm for reducing the bandwidth and profile 76 of a sparse matrix}, 77 VOLUME = {13}, 78 YEAR = {1976} } 79 80@techreport{rag95-PCO, 81 author="P. Raghavan", 82 title="Parallel ordering using edge contraction", 83 number="CS-95-293", 84 institution="Dept. of Computer Science, The University of 85 Tennessee", 86 address="Knoxville, Tennessee", 87 year="1995"} 88 89@techreport{ame94-amdTR, 90 author="P. Amestoy and T. Davis and I. Duff", 91 title="An approximate minimum degree ordering algorithm", 92 number = "TR-94-039", 93 institution="University of Florida", 94 year="1994"} 95 96@article{ame96-amd, 97 author="P. Amestoy and T. Davis and I. Duff", 98 title="An approximate minimum degree ordering algorithm", 99 journal="SIAM J. Matrix Anal. Appl.", 100 volume="17", 101 pages="886-905", 102 year="1996"} 103 104@techreport{hr96-msnd, 105 author="B. Hendrickson and E. Rothberg", 106 title="Improving the runtime and quality of nested dissection 107 ordering", 108 institution="Sandia National Laboratories", 109 year="1996"} 110 111@article{ash89-relaxed, 112 author="C. Ashcraft and R. Grimes", 113 title="The influence of relaxed supernode partitions on the 114 multifrontal method", 115 journal="ACM Trans. Math. Software", 116 volume="15", 117 year="1989", 118 pages="291-309"} 119 120@techreport{ash95-AGL, 121 author="C. Ashcraft and R. G. Grimes and J. G. Lewis", 122 title="Accurate symmetric indefinite linear equation solvers", 123 number="ISSTECH-95-029", 124 institution="Boeing Computer Services", 125 year="1995", 126 note="Accepted for publication in {\it SIAM J. Matrix. Anal.}"} 127 128@techreport{ash96-multisection, 129 author="C. Ashcraft and J. W. H. Liu", 130 title="Robust ordering of sparse matrices using multisection", 131 number="ISSTECH-96-002", 132 institution="Boeing Information and Support Services", 133 year="1996", 134 note="Accepted for publication in {\it SIAM J. Matrix. Anal.}"} 135 136@techreport{ash95-DDSEP, 137 author="C. Ashcraft and J. W. H. Liu", 138 title="Using domain decompositions to find graph bisectors", 139 number="ISSTECH-95-024", 140 institution="Boeing Computer Services", 141 year="1995", 142 note="Accepted for publication in {\it BIT}"} 143 144@techreport{ash95-robust, 145 author="C. Ashcraft and J. W. H. Liu", 146 title="Robust ordering of sparse matrices using multisection", 147 number="ISSTECH-96-002", 148 institution="Boeing Computer Services", 149 year="1996"} 150 151@techreport{ash96-maxflow, 152 author="C. Ashcraft and J. W. H. Liu", 153 title="Applications of the {D}ulmage-{M}endelsohn decomposition 154 and network flow to graph bisection improvement", 155 number="ISSTECH-96-017", 156 institution="Boeing Computer Services", 157 year="1996", 158 note="Accepted for publication in {\it SIAM J. Matrix. Anal.}"} 159 160@techreport{ash93-compressed-graphs-TR, 161 author="C. Ashcraft", 162 title="Compressed graphs and the minimum degree algorithm", 163 number="BCSTECH-93-024", 164 institution="Boeing Computer Services", 165 year="1993"} 166 167@techreport{ash94-partition, 168 author="C. Ashcraft and J. W. H. Liu", 169 title="A partition improvement algorithm for generalized nested dissection", 170 number="BCSTECH-94-020", 171 institution="Boeing Computer Services", 172 year="1994", 173 note="Accepted for publication in {\it BIT}"} 174 175@article{ber90-mindeg, 176 author="P. Berman and G. Schnitger", 177 title="On the performance of the minimum degree ordering for 178 {G}aussian elimination", 179 journal="SIAM J. Matrix Analysis and Applic.", 180 volume="11", 181 year="1990", 182 pages="83-88"} 183 184@article{bha93-localND, 185 author="M. V. Bhat and W. G. Habashi and J. W. H. Liu 186 and V. N. Nguyen and M. F. Peeters", 187 title="A note on nested dissection for rectangular grids", 188 journal="SIAM J. Matrix Analysis and Applic.", 189 volume="14", 190 year="1993", 191 pages="253-258"} 192 193@phdthesis{dam92-compressed, 194 author="A. C. Damhaug", 195 title="Sparse Solution of Finite Element Equations", 196 school="The Norwegian Institute of Technology", 197 year="1992"} 198 199@article{duf83-multifrontal, 200 author="I. Duff and J. Reid", 201 title="The multifrontal solution of indefinite sparse 202 symmetric linear equations", 203 journal="ACM Trans. Math. Software", 204 volume="6", 205 year="1983", 206 pages="302-325"} 207 208@inproceedings{eis76-elementModel, 209 author="S. C. Eisenstat and M. H. Schultz and A. H. Sherman", 210 title="Applications of an element model 211 for {G}aussian elimination", 212 booktitle="Sparse Matrix Computations", 213 pages="85-96", 214 publisher="Academic Press", 215 year="1976", 216 editor="J. R. Bunch and D. J. Rose"} 217 218@inproceedings{fid82-partition, 219 author="C. M. Fiduccia and R. M. Mattheyses", 220 title="A linear-time heuristic for improving network partition", 221 booktitle="ACM IEEE Proc. 19th Design Automation Conference, 222 Las Vegas, Nevada", 223 year="1982", 224 pages="175-181"} 225 226@article{geo80-1way, 227 author="J. A. George", 228 title="An automatic one-way dissection algorithm for irregular finite 229 element problems", 230 journal="SIAM J. Numer. Anal.", 231 volume="17", 232 year="1980", 233 pages="740-751"} 234 235@article{sparsematlab, 236 author="J. Gilbert and C. Moler and R. Schreiber", 237 title="Sparse matrices in {MATLAB}: design and implementation", 238 journal="SIAM J. Matrix Analysis and Applic.", 239 volume="13", 240 year="1992", 241 pages="335-356"} 242 243@techreport{gup96-WGPP, 244 author="A. Gupta", 245 title="{WGPP}: {W}atson {G}raph {P}artitioning and sparse matrix 246 ordering {P}ackage", 247 number="Users Manual", 248 institution="IBM T.J. Watson Research Center", 249 address="New York", 250 year="1996"} 251 252 253@techreport{hea92-dissection, 254 author="M.T. Heath and P. Raghavan", 255 title="A Cartesian nested dissection algorithm", 256 number="UIUCDCS-R-92-1772", 257 institution="Dept of Computer Science, University of Illinois", 258 address="Urbana, IL", 259 year="1992"} 260 261@techreport{hen92-partition, 262 author="B. Hendrickson and R. Leland", 263 title="An improved spectral graph partitioning algorithm for 264mapping parallel computations", 265 number="SAND92-1460", 266 institution="Sandia National Laboratories", 267 address="Albuquerque, NM", 268 year="1992"} 269 270@techreport{hen93-partition, 271 author="B. Hendrickson and R. Leland", 272 title="Multidimensional spectral load balancing", 273 number="SAND93-074", 274 institution="Sandia National Laboratories", 275 address="Albuquerque, NM", 276 year="1993"} 277 278@article{ker70-partition, 279 author="B. W. Kernighan and S. Lin", 280 title="An efficient heuristic procedure for partitioning graphs", 281 journal="Bell System Technical Journal", 282 volume="49", 283 year="1970", 284 pages="291-307"} 285 286@inproceedings{lei89-fidmat, 287 author="C. E. Leiserson and J. G. Lewis", 288 title="Orderings for parallel sparse symmetric factorization", 289 booktitle="Parallel Processing for Scientific Computing", 290 year="1989", 291 pages="27-31"} 292 293@article{lip79-separators, 294 author="R. J. Lipton and R. E. Tarjan", 295 title="A separator theorem for planar graphs", 296 journal="SIAM J. Applied Math", 297 volume="36", 298 year="1979", 299 pages="177-189"} 300 301@article{liu89-separators, 302 author="J. W. H. Liu", 303 title="A graph partitioning algorithm by node separators", 304 journal="ACM Trans. on Math. Software", 305 volume="15", 306 year="1989", 307 pages="198-219"} 308 309@article{liu85-mfstorage, 310 author="J. W. H. Liu", 311 title="On the storage requirement in the out-of-core 312 multifrontal method for sparse factorization", 313 journal="ACM Trans. on Math. Software", 314 volume="12", 315 year="1986", 316 pages="249-264"} 317 318@article{liu85-mmd, 319 author="J. W. H. Liu", 320 title="Modification of the minimum degree algorithm by 321 multiple elimination", 322 journal="ACM Trans. on Math. Software", 323 volume="11", 324 year="1985", 325 pages="141-153"} 326 327@article{liu89-mindeg, 328 author="J. W. H. Liu", 329 title="On the minimum degree ordering with constraints", 330 journal="SIAM J. Sci. Stat. Comput.", 331 volume="10", 332 year="1989", 333 pages="1136-1145"} 334 335@article{liu90-etree, 336 author="J. W. H. Liu", 337 title="The role of elimination trees in sparse factorization", 338 journal="SIAM J. Matrix Analysis and Applic.", 339 volume="11", 340 year="1990", 341 pages="134-172"} 342 343@article{liu91-generalizedEnvelope, 344 author="J. W. H. Liu", 345 title="A generalized envelope method 346 for sparse factorization by rows", 347 journal="ACM Trans. on Math. Software", 348 volume="17", 349 year="1991", 350 pages="112-129"} 351 352@article{mar57, 353 author="H. M. Markowitz", 354 title="The elimination form of the inverse and its application to 355 linear programming", 356 journal="Management Sci.", 357 volume="3", 358 year="1957", 359 pages="255-269"} 360 361@mastersthesis{ng79-master, 362 author="E. Ng", 363 title="On one-way dissection schemes", 364 school="Dept of Computer Science, University of Waterloo", 365 address="Waterloo, Ontario", 366 year="1979"} 367 368@techreport{rag93-separators, 369 author="P. Raghavan", 370 title="Line and plane separators", 371 number="UIUCDCS-R-93-1794", 372 institution="Dept of Computer Science, University of Illinois", 373 address="Urbana, IL", 374 year="1993"} 375 376@inproceedings{ros72-elimination, 377 author="D. J. Rose", 378 title="A graph-theoretic study of the numerical solution of sparse 379 positive definite systems of linear equations", 380 booktitle="Graph Theory and Computing", 381 publisher="Academic Press", 382 editor="R. Read", 383 year="1972", 384 pages="183-217"} 385 386@article{ros70-elimination, 387 author="D. J. Rose", 388 title="Triangulated graphs and the elimination process", 389 journal="J. Math. Anal. & Appl.", 390 volume="32", 391 year="1970", 392 pages="597-609"} 393 394@techreport{ten91-separators, 395 author="S.H. Teng", 396 title="Points, Spheres, and Separators", 397 number="CMU-CS-91-184", 398 institution="School of Computer Science, Carnegie Mellon University", 399 address="Pittsburgh, PA", 400 year="1991"} 401 402@article{tin67-order, 403 author="W. F. Tinney and J. W. Walker", 404 title="Direct solutions of sparse network equations by optimally ordered 405 triangular factorization", 406 journal="J Proc. IEEE", 407 volume="55", 408 year="1967", 409 pages="1801-1809"} 410 411@book{aho83, 412 author="A. V. Aho and J. E. Hopcroft and J. D. Ullman", 413 title="Data Structures and Algorithms", 414 publisher="Addison-Wesley", 415 address="Reading, MA", 416 year="1983"} 417 418@book{duf87-book, 419 author="I. S. Duff and A. M. Erisman and J. K. Reid", 420 title="Direct Methods for Sparse Matrices", 421 publisher="Oxford University Press", 422 address="London", 423 year="1987"} 424 425@book{geo81-book, 426 author="J. A. George and J. W. H. Liu", 427 title="Computer Solution of Large Sparse Positive Definite Systems", 428 publisher="Prentice-Hall", 429 address="Englewood Cliffs, NJ", 430 year="1981"} 431 432@article{ash87-progress, 433 AUTHOR = {C. Ashcraft and R. Grimes and J. Lewis and B. Peyton 434 and H. Simon}, 435 JOURNAL = {Intern. J. of Supercomputer Applications}, 436 KEY = {LLt vector}, 437 PAGES = {10-30}, 438 TITLE = {Progress in sparse matrix methods for large sparse 439 linear systems on vector supercomputers}, 440 VOLUME = {1}, 441 YEAR = {1987} 442} 443 444@techreport{ash90-partition, 445 author="C. Ashcraft", 446 title="The domain/segment partition for the factorization of sparse 447symmetric positive definite matrices", 448 number="ECA-TR-148", 449 institution="Boeing Computer Services", 450 address="Seattle, WA", 451 year="1990"} 452 453@article{ash95-compressed-graphs, 454 author="C. Ashcraft", 455 title="Compressed graphs and the minimum degree algorithm", 456 journal="SIAM J. Sci. Comput.", 457 pages = "1404-1411", 458 volume = 16, 459 year="1995"} 460 461@inproceedings{ash90-lookahead, 462 author="C. Ashcraft and S. C. Eisenstat and J. W. H. Liu and 463 B. W. Peyton and A. H. Sherman", 464 title="A compute-ahead fan-in scheme for parallel sparse 465 matrix factorization", 466 booktitle="Fourth Canadian Supercomputing Symposium (1990)", 467 editor="D. Pelletier", 468 year="June, 1990", 469 pages="351-361"} 470 471 472@inproceedings{ash94-multisection, 473 author="C. Ashcraft and J. W. H. Liu", 474 title="Generalized nested dissection: some recent progress", 475 booktitle="Fifth SIAM Conference on Applied Linear Algebra", 476 address="Snowbird, Utah", 477 year="June 18, 1994"} 478 479@inproceedings{bar93-partition, 480 author="S. T. Barnard and H. D. Simon", 481 title="A fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems", 482 booktitle="Proceedings of the Sixth SIAM Conference on Parallel Processing for Scientific Computing", 483 year="1993", 484 pages="711-718"} 485 486@inproceedings{bar95-partition, 487 author="S. T. Barnard and H. D. Simon", 488 title="A parallel implementation of multilevel recursive spectral bisection for applications in adaptive unstructured meshes", 489 booktitle="Proceedings of the seventh SIAM Conference on Parallel Processing for Scientific Computing", 490 year="1995", 491 pages="627-632"} 492 493@article{bui92-partition, 494 author="T. Bui and C. Jones", 495 title="Finding good approximate vertex and edge partitions is {NP}-hard", 496 journal="Information Processing Letters", 497 volume="42", 498 year="1992", 499 pages="153-159"} 500 501@inproceedings{bui93-partition, 502 author="T. Bui and C. Jones", 503 title="A heuristic for reducing fill-in in sparse matrix factorization", 504 booktitle="Proceedings of Sixth SIAM Conference on Parallel Processing ", 505 year="1993", 506 pages="445-452"} 507 508 509@article{geo73-nested, 510 author="J. A. George", 511 title="Nested dissection of a regular finite element mesh", 512 journal="SIAM J. Numer. Anal.", 513 volume="10", 514 year="1973", 515 pages="345-363"} 516 517@article{geo89-mindeg, 518 author="J.A. George and J. W. H. Liu", 519 title="The evolution of the minimum degree ordering algorithm", 520 journal="SIAM Review", 521 volume="31", 522 year="1989", 523 pages="1-19"} 524 525@techreport{goe95-partition, 526 author="T. Goehring and Y. Saad", 527 title="Heuristic algorithms for automatic graph partitioning", 528 number="", 529 institution="Computer Science Department, University of Minnesota", 530 address="Minnesota", 531 year="1995"} 532 533@article{hal35, 534 author = "P. Hall", 535 title = "On representatives of subsets", 536 journal = "J. London Math. Society", 537 volume = "10", 538 year = "1935", 539 pages = "26-30"} 540 541@article{Harwell-Boeing-Matrices, 542 author = "I.S. Duff and R.G. Grimes and J.G. Lewis", 543 title = "Sparse matrix test problems", 544 journal="ACM Trans. on Math. Software", 545 volume = "15", 546 year = "1989", 547 pages = "1-14"} 548 549@article{dul58, 550 author = "A.L. Dulmage and N.S. Mendelsohn", 551 title = "Coverings of bipartite graphs", 552 journal="Can. J. Math", 553 volume = "10", 554 year = "1958", 555 pages = "517-534"} 556 557@techreport{sparspak80, 558 author="J. A. George and J. W. H. Liu and E. G. Ng", 559 title="User's guide for {SPARSPAK}: {W}aterloo sparse linear 560 equations package", 561 number = "Tech. Rep. CS78-30(revised)", 562 institution = "Dept. of Computer Sciences, Univ. of Waterloo", 563 address="Waterloo, Ontario, Canada", 564 year = "1980"} 565 566@techreport{hen93-chaco, 567 author="B. Hendrickson and R. Leland", 568 title="The {C}haco user's guide", 569 number="SAND93-2339", 570 institution="Sandia National Laboratories", 571 address="Albuquerque, NM", 572 year="1993"} 573 574@techreport{hen93-partition, 575 author="B. Hendrickson and R. Leland", 576 title="A multilevel algorithm for partitioning graphs", 577 number="SAND93-1301", 578 institution="Sandia National Laboratories", 579 address="Albuquerque, NM", 580 year="1993"} 581 582@techreport{hen93-spectral, 583 author="B. Hendrickson and R. Leland", 584 title="Multidimensional spectral load balancing", 585 number="SAND93-074", 586 institution="Sandia National Laboratories", 587 address="Albuquerque, NM", 588 year="1993"} 589 590@techreport{kar95-kway, 591 author="G. Karypis and V. Kumar", 592 title="Multilevel $k$-way partitioning scheme for irregular graphs", 593 institution="Department of Computer Science, University of Minnesota", 594 address="Minnesota", 595 year="1995"} 596% number="Technical Report", 597 598@techreport{kar95-multilevel, 599 author="G. Karypis and V. Kumar", 600 title="A fast and high quality multilevel scheme for partitioning irregular graphs", 601 number="TR 95-035", 602 institution="Department of Computer Science, University of Minnesota", 603 address="Minnesota", 604 year="1995"} 605 606@techreport{kar95-metis, 607 author="G. Karypis and V. Kumar", 608 title="{METIS}: Unstructured graph partitioning and sparse matrix ordering system", 609 institution="Department of Computer Science, University of Minnesota", 610 address="Minnesota", 611 year="1995"} 612% number="TR 95-???", 613 614@techreport{kar95-partition, 615 author="G. Karypis and V. Kumar", 616 title="Analysis of multilevel graph partitioning", 617 number="TR 95-037", 618 institution="Department of Computer Science, University of Minnesota", 619 address="Minnesota", 620 year="1995"} 621 622@inproceedings{kar95, 623 author="G. Karypis and V. Kumar", 624 title="Multilevel graph partition and sparse matrix ordering", 625 booktitle="Intl. Conf. on Parallel Processing", 626 year="1995"} 627 628@article{lip79, 629 author="R. J. Lipton and R. E. Tarjan", 630 title="A separator theorem for planar graphs", 631 journal="SIAM J. Applied Math", 632 volume="36", 633 year="1979", 634 pages="177-189"} 635 636@techreport{mai94-partition, 637 author="H.S. Maini and K.G. Mehrotra and S. Ranka", 638 title="Genetic algorithms for graph partitioning and incremental 639 graph partitioning", 640 number="Technical report", 641 institution="Center for Science and Technology, Syracuse University", 642 address="Synracuse, N.Y.", 643 year="1994"} 644 645@article{pot90-triangular, 646 author="A. Pothen and C. Fan", 647 title="Computing the block triangular form of a sparse matrix", 648 journal="ACM Trans. on Math. Software", 649 volume="16", 650 year="1990", 651 pages="303-324"} 652 653@article{pot90-partition, 654 author="A. Pothen and H. Simon and K.P. Liou", 655 title="Partitioning sparse matrices with eigenvectors of graphs", 656 journal="SIAM J. Matrix Analysis and Applic.", 657 volume="11", 658 year="1990", 659 pages="430-452"} 660 661@book{aho83, 662 author="A. V. Aho and J. E. Hopcroft and J. D. Ullman", 663 title="Data Structures and Algorithms", 664 publisher="Addison-Wesley", 665 address="Reading, MA", 666 year="1983"} 667 668@book{ull84-vlsi, 669 author="J. D. Ullman", 670 title="Computational Aspects of VLSI", 671 publisher="Computer Science Press", 672 address="Rockville, Md", 673 year="1984"} 674 675@book{duf87-book, 676 author="I. S. Duff and A. M. Erisman and J. K. Reid", 677 title="Direct Methods for Sparse Matrices", 678 publisher="Oxford University Press", 679 address="London", 680 year="1987"} 681 682@book{geo81-book, 683 author="J. A. George and J. W. H. Liu", 684 title="Computer Solution of Large Sparse Positive Definite Systems", 685 publisher="Prentice-Hall", 686 address="Englewood Cliffs, NJ", 687 year="1981"} 688 689@book{zzzz99-book, 690 author="J. A. George and J. W. H. Liu", 691 title="Computer Solution of Large Sparse Positive Definite Systems", 692 publisher="Prentice-Hall", 693 address="Englewood Cliffs, NJ", 694 year="1981"} 695 696 697@article{arn85, 698 author="S. Arnborg", 699 title="Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey", 700 journal="BIT", 701 volume="25", 702 year="1985", 703 pages="2-23"} 704 705@techreport{bar81, 706 author="E. R. Barnes", 707 title="An algorithm for partitioning the nodes of a graph", 708 number="RC8690", 709 institution="IBM Thomas J. Watson Research Center", 710 address="Yorktown Heights, New York", 711 year="1981"} 712 713@inproceedings{bar85, 714 author="E. R. Barnes", 715 title="Partitioning the nodes of a graph", 716 booktitle="Graph Theory with Applications to Algorithms and Computer Science", 717 editor="Y. Alavi and G. Chartrand and D. Lick and C. Wall and L. Lesuiak", 718 publisher="John Wiley \& Sons Inc.", 719 address="New York", 720 year="1985", 721 pages="57-72"} 722 723@article{bha84, 724 author="S. N. Bhatt and F. T. Leighton", 725 title="A framework for solving {VLSI} graph layout problems", 726 journal="Journal of Computer \& Systems Sciences", 727 volume="28", 728 year="1984", 729 pages=""} 730 731@inproceedings{bre77, 732 author="M. A. Breuer", 733 title="A class of min-cut placement algorithms", 734 booktitle="Proc. 14th Design Automation Conference", 735 year="1977", 736 pages="284-290"} 737 738@inproceedings{bui84, 739 author="S. N. Bui and S. Chaudhuri and T. Leighton and M. Sipser", 740 title="Graph bisection algorithms with good average case behavior", 741 booktitle="Proceedings of the 25th Annual Symposium of Foundations of Computer Science", 742 year="1984", 743 pages="181-192"} 744 745@article{dji81, 746 author="H. N. Djidjev", 747 title="A separator theorem", 748 journal="Comptes rendus de l' Academie bulgare des Sciences", 749 volume="34", 750 year="1981", 751 pages="643-645"} 752 753@article{dji82-linear, 754 author="H. N. Djidjev", 755 title="A linear algorithm for partitioning graphs", 756 journal="Comptes rendus de l' Academie bulgare des Sciences", 757 volume="35", 758 year="1982", 759 pages="1053-1056"} 760 761@article{dji82-planar, 762 author="H. N. Djidjev", 763 title="On the problem of partitioning planar graphs", 764 journal="SIAM J. Alg. \& Disc. Meth.", 765 volume="3", 766 year="1982", 767 pages="229-240"} 768 769@article{don72, 770 author="W. E. Donath and A. J. Hoffman", 771 title="Algorithms for partitioning of graphs and computer logic based on eigenvectors of connection matrices", 772 journal="IBM Technical Disclosure Bulletin", 773 volume="15", 774 year="1972", 775 pages="938-944"} 776 777@article{don73, 778 author="W. E. Donath and A. J. Hoffman", 779 title="Lower bounds for the partitioning of graphs", 780 journal="IBM J. Res. Develop.", 781 volume="17", 782 year="1973", 783 pages="420-425"} 784 785@article{fie73, 786 author="M. Fiedler", 787 title="Algebraic connectivity of graphs", 788 journal="Czechoslovak Math J.", 789 volume="23", 790 year="1973", 791 pages="298-305"} 792 793@book{fre86, 794 author="G. N. Fredrickson and R. Janardan", 795 title="Separator-based strategies for efficient message routing", 796 booktitle="27th Annual Symposium on Foundation of Computer Science", 797 publisher="IEEE", 798 year="1986", 799 pages="428-437"} 800 801@book{gaz87, 802 author="H. Gazit and G. L. Miller", 803 title="A parallel algorithm for finding a separator in planar graphs", 804 booktitle="28th Annual Symposium on Foundation of Computer Science", 805 publisher="IEEE", 806 year="1987", 807 pages="238-248"} 808 809@techreport{gil80, 810 author="J. R. Gilbert", 811 title="Graph separator theorems and sparse {G}aussian elimination", 812 number="Ph.D. Thesis", 813 institution="DCS, Stanford University", 814 year="1980"} 815 816@article{gil84-genus, 817 author="J. R. Gilbert and J. P. Hutchinson and R. E. Tarjan", 818 title="A separator theorem for graphs of bounded genus", 819 journal="J. of Algorithms", 820 volume="5", 821 year="1984", 822 pages="391-407"} 823 824@article{gil84-chordal, 825 author="J. R. Gilbert and D. J. Rose and A. Edenbrandt", 826 title="A separator theorem for chordal graphs", 827 journal="SIAM J. Alg. \& Disc. Meth.", 828 volume="5", 829 year="1984", 830 pages="306-313"} 831 832@inproceedings{gol83, 833 author="M. K. Goldberg and M. Burstein", 834 title="Heuristic improvement technique for bisection of {VLSI} networks", 835 booktitle="Proc. IEEE International Conf. on Computer Design", 836 address="Port Chester, New York", 837 year="1983", 838 pages="122-125"} 839 840@techreport{gol87, 841 author="M. K. Goldberg and S. Lath and J. W. Roberts", 842 title="Heuristics for the graph bisection problem", 843 number="Report", 844 institution="Rensselaer Polytechnic Institute", 845 year="1987"} 846 847@techreport{hen92, 848 author="B. Hendrickson and R. Leland", 849 title="An improved spectral graph partitioning algorithm for mapping parallel computations", 850 number="SAND92-1460", 851 institution="Sandia National Laboratories", 852 address="Albuquerque, NM", 853 year="1992"} 854 855@techreport{hen93, 856 author="B. Hendrickson and R. Leland", 857 title="Multidimensional spectral load balancing", 858 number="SAND93-074", 859 institution="Sandia National Laboratories", 860 address="Albuquerque, NM", 861 year="1993"} 862 863@article{hu81, 864 author="T. C. Hu and M. T. Shing", 865 title="An O(n) algorithm to find a near-optimum partition", 866 journal="Journal of Algorithms", 867 volume="2", 868 year="1981", 869 pages="122-138"} 870 871@article{hu85, 872 author="T. C. Hu and M. T. Shing", 873 title="A decomposition algorithm for circuit routing", 874 journal="Math. Programming Study", 875 volume="24", 876 year="1985", 877 pages="87-103"} 878 879@article{hu86, 880 author="T. C. Hu and M. T. Shing", 881 title="A decomposition algorithm for multi-terminal network flows", 882 journal="J. Discrete Applied Math.", 883 volume="13", 884 year="1986", 885 pages="165-181"} 886 887@article{joh88, 888 author="D. S. Johnson and C. R. Aragon and L. A. McGeoch and C. Schevon", 889 title="Optimization by simulated annealing: an experimental evaluation", 890 journal="Operations Research", 891 note="((submitted))", 892 year="1988"} 893 894@article{kan91, 895 author="A. Kanevsky and V. Ramachandran", 896 title="Improved algorithms for graph four-connectivity", 897 journal="J. of Computer Science and Systems", 898 volume="42", 899 year="1991", 900 pages="288-306"} 901 902@article{kan9x, 903 author="A. Kanevsky", 904 title="Finding all minimum size vertex sets in a graph", 905 journal="J. of Networks", 906 year="199x"} 907 908@inproceedings{kan90, 909 author="A. Kanevsky", 910 title="On the number of minimum size separating vertex sets of a graph and how to find all of them", 911 booktitle="First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '90)", 912 year="January 22-24,1990", 913 pages="411-421"} 914 915@article{kao90, 916 author="M. Kao and F. Wan", 917 title="Not all planar digraphs have small cycle separators", 918 journal="Information Processing Letters", 919 year="1990"} 920 921@techreport{ker69, 922 author="B. W. Kernighan", 923 title="Some graph partitioning problems related to program segmentation", 924 number="Ph.D. Thesis", 925 institution="Princeton University", 926 year="1969"} 927 928@article{ker70, 929 author="B. W. Kernighan and S. Lin", 930 title="An efficient heuristic procedure for partitioning graphs", 931 journal="Bell System Technical Journal", 932 volume="49", 933 year="1970", 934 pages="291-307"} 935 936@article{kir83, 937 author="S. Kirkpatrick and C. D. Gelatt Jr. and M. P. Vecchi", 938 title="Optimization by simulated annealing", 939 journal="Science", 940 volume="220", 941 year="1983", 942 pages="671-680"} 943 944@article{kom85, 945 author="J. Komlos and M. T. Shing", 946 title="Probabilistic partitioning algorithms for the rectilinear Steiner problem", 947 journal="Networks", 948 volume="15", 949 year="1985", 950 pages="413-423"} 951 952@article{kri84, 953 author="B. Krishnamurthy", 954 title="An improved min-cut algorithm for partitioning {VLSI} networks", 955 journal="IEEE Trans. on Computers", 956 volume="C-33", 957 year="1984", 958 pages="438-446"} 959 960@article{kri87, 961 author="B. Krishnamurthy", 962 title="Constructing test cases for partitioning heuristics", 963 journal="IEEE Trans. on Computers", 964 volume="C-36", 965 year="198", 966 pages="1112-1114"} 967 968@inproceedings{lei82, 969 author="F. T. Leighton", 970 title="A layout strategy for {VLSI} which is provably good", 971 booktitle="Proceedings of the 14th Annual ACM Symposium on Theory of Computing", 972 year="1982", 973 pages="85-98"} 974 975@book{lei80, 976 author="C. Leiserson", 977 title="Area-efficient graph layout (for vlsi)", 978 booktitle="21st Annual Symposium on Foundation of Computer Science", 979 publisher="IEEE", 980 year="1980", 981 pages="270-281"} 982 983@article{lin77, 984 author="T. D. Lin and R. S. H. Mah", 985 title="Hierarchical partition -- a new optimal pivoting algorithm", 986 journal="Math. Programming", 987 volume="12", 988 year="1977", 989 pages="260-278"} 990 991@article{lip80, 992 author="R. J. Lipton and R. E. Tarjan", 993 title="Applications of a planar separator theorem", 994 journal="SICOMP", 995 volume="9", 996 year="1980", 997 pages="615-627"} 998 999@techreport{mac78, 1000 author="R. M. Macgregor", 1001 title="On partitioning a graph: a theoretical and empirical study", 1002 number="UCB/ERL M78/14 (Ph.D. Thesis)", 1003 institution="Standford University", 1004 year="1978"} 1005 1006@inproceedings{mil84, 1007 author="G. L. Miller", 1008 title="Finding small simple cycle separators for 2-connected planar graphs", 1009 booktitle="Proceedings of the 16th Annual ACM Symposium on Theory of Computing", 1010 year="1984", 1011 pages="376-382"} 1012 1013@techreport{moo88, 1014 author="D. Moore", 1015 title="A round-robin parallel partitioning algorithm", 1016 number="TR 88-916", 1017 institution="DCS, Cornell University", 1018 year="1988"} 1019 1020@article{pai87, 1021 author="R. Paige and R. E. Tarjan", 1022 title="Three partition refinement algorithm", 1023 journal="SICOMP", 1024 volume="16", 1025 year="1987", 1026 pages="973-989"} 1027 1028@article{pow88, 1029 author="D. Powers", 1030 title="Graph partitioning by eigenvectors", 1031 journal="Lin. Alg. Appl.", 1032 volume="101", 1033 year="1988", 1034 pages="121-133"} 1035 1036@book{rao87, 1037 author="S. Rao", 1038 title="Finding near optimal separators in planar graphs", 1039 booktitle="28th Annual Symposium on Foundation of Computer Science", 1040 publisher="IEEE", 1041 year="1987", 1042 pages="225-237"} 1043 1044@article{rav87, 1045 author="S. Ravi and H. Hunt III", 1046 title="An application of the planar separator theorem to counting problem", 1047 journal="Inform. Process. Letters", 1048 volume="25", 1049 year="1987", 1050 pages="317-322"} 1051 1052@techreport{ren90, 1053 author="F. Rendl and H. Wolkowicz", 1054 title="A projection technique for partitioning the nodes of a graph", 1055 number="CORR 90-20", 1056 institution="University of Waterloo", 1057 address="Waterloo, Ontario", 1058 year="1990"} 1059 1060@inproceedings{san76, 1061 author="A. Sangiovanni-Vincentelli", 1062 title="An optimization problem arising from tearing methods", 1063 booktitle="Sparse Matrix Computations", 1064 editor="J.R. Bunch and D.J. Rose", 1065 publisher="Academic Press", 1066 year="1976", 1067 pages="97-110"} 1068 1069@inproceedings{sch79, 1070 author="D. G. Schweikert and B. W. Kernighan", 1071 title="A proper model for the partitioning of electrical circuits", 1072 booktitle="Proc. 9th Design Automation Workshop", 1073 year="1979", 1074 pages="57-62"} 1075 1076@article{sen92, 1077 author="A. Sen and H. Deng and S. Guha", 1078 title="On a graph partition problem with application to vlsi layout", 1079 journal="Information Processing Letters", 1080 year="1992", 1081 volume="43", 1082 pages="87-94"} 1083 1084@techreport{she87, 1085 author="T. J. Sheffler", 1086 title="A graph separator theorem and its application to {G}aussian elimination to optimize {B}oolean expression for parallel evaluation", 1087 number="CMU-CS-87-123", 1088 institution="DCS, Carnegie-Mellon University", 1089 year="1987"} 1090 1091@inproceedings{shi80, 1092 author="H. Shiraishi and F. Hirose", 1093 title="Efficient placement and routing for masterslice {LSI}", 1094 booktitle="Proc. 17th Design Automation Conference", 1095 year="1980", 1096 pages="458-464"} 1097 1098@article{sua88, 1099 author="P. Suaris and G. Kedem", 1100 title="An algorithm for quadrisection and its application to standard cell placement", 1101 journal="IEEE Trans. Circuits and Systems", 1102 volume="35", 1103 year="1988", 1104 pages="294-303"} 1105 1106@article{tar??, 1107 author="R. E. Tarjan", 1108 title="Decomposition by clique separators", 1109 journal="Discrete Math", 1110 year="to appear"} 1111 1112@article{ven87, 1113 author="S. Venkatesan", 1114 title="Improved constants for some separator theorems", 1115 journal="J. Algorithms", 1116 volume="8", 1117 year="1987", 1118 pages="572-578"} 1119 1120@article{wan91, 1121 author="F. Wan", 1122 title="A linear-processor algorithm for finding small cycle separators on undirected planar graphs", 1123 journal="SICOMP", 1124 year="1991?"} 1125 1126@article{whi81, 1127 author="S. H. Whitesides", 1128 title="An algorithm for finding clique cutsets", 1129 journal="Inf. Proc. Letters", 1130 volume="12", 1131 year="1981", 1132 pages="31-32"} 1133 1134@incollection{matrixmarket97, 1135 author="R. F. Boisvert and R. Pozo and K. Remington 1136 and R. F. Barrett and J. J. Dongarra", 1137 title="Matrix {M}arket: a web resource for test matrix collections", 1138 booktitle="The Quality of Numerical Software: 1139 Assessment and Enhancement", 1140 publisher="Chapman and Hall, London", 1141 year="1997", 1142 editor="R. F. Boisvert", 1143 pages="125-137"} 1144 1145@article{ne92-rook, 1146 author="L. Neal and G. Poole", 1147 title="A geometric analysis of {G}aussian elimination II.}", 1148 journal="Linear Alg. and Appl.", 1149 volume="173", 1150 year="1992", 1151 pages="239-264"} 1152 1153@misc{fo96-rook, 1154 author="L. V. Foster", 1155 title="The growth factor and efficiency of {G}aussian 1156 elimination with rook pivoting", 1157 note="Accepted for publication in {\it J. Comp. and Appl. Math.}"} 1158 1159