1@article{ash97-partition, 2 author="C. Ashcraft and J. W. H. Liu", 3 title="Using domain decomposition to find graph bisectors", 4 journal="BIT", 5 volume="37", 6 year="1997"} 7 8@techreport{kar94-mf, 9 author="G. Karypis and V. Kumar", 10 title="A high performance sparse {C}holesky factorization 11 algorithm for scalable parallel computers", 12 institution="Dept. of Computer Science, University of Minnesota", 13 year="1994", 14 number="94-41"} 15 16@techreport{SuperLU95, 17 author="J. W. Demmel and S. C. Eisenstat and J. R. Gilbert 18 and X. S. Li and J. W. H. Liu", 19 title="A supernodal approach to sparse partial pivoting", 20 institution="Xerox Palo Alto Research Center", 21 number="CSL--94--14", 22 year="1995", 23 note="Accepted for publication in {\it SIAM J. Matrix. Anal.}"} 24 25@article{roth98-minfill, 26 author="E. Rothberg and S. C. Eisenstat", 27 title="Node selection strategies 28 for bottom-up sparse matrix ordering", 29 journal="SIAM J. Matrix Anal.", 30 volume="19", 31 year="1998", 32 pages="682-695"} 33 34@article{pot93-proportional, 35 author="A. Pothen and C. Sun", 36 title="A mapping algorithm for parallel sparse {C}holesky 37 factorization", 38 journal="SIAM J. Sci. Comput.", 39 volume="14", 40 year="1993", 41 pages="1253-1257"} 42 43@article{and90-random, 44 author="S. L. Anderson", 45 title="Random number generators on vector supercomputers 46 and other advanced architectures", 47 journal="SIAM Review", 48 volume="32", 49 year="1990", 50 pages="221-251"} 51 52@misc{roger97-amalg, 53 AUTHOR="R. Grimes", 54 note="personal communication"} 55 56@misc{ash97-utah, 57 AUTHOR="C. Ashcraft and S. C. Eisenstat and J. W. H. Liu", 58 title="Practical extensions of the multisection ordering for 59 sparse matrices", 60 howpublished="Minisymposium presentation at 61 the Sixth SIAM Conference on Applied Linear Algebra, 62 Snowbird, Utah", 63 year="October 29, 1997"} 64 65@misc{ash94-utah, 66 AUTHOR="C. Ashcraft and J. W. H. Liu", 67 title="Generalized nested dissection: some recent progress", 68 howpublished="Minisymposium presentation at 69 the Fifth SIAM Conference on Applied Linear Algebra, 70 Snowbird, Utah", 71 year="June 18, 1994"} 72 73@misc{rot96-balance, 74 AUTHOR="E. Rothberg", 75 title="Exploring the tradeoff between imbalance and separator 76 size in nested dissection ordering", 77 howpublished="unpublished", 78 year="1996"} 79 80@misc{ro95-hybrid, 81 AUTHOR="E. Rothberg", 82 title="Robust ordering of sparse matrices: a minimum degree, 83 nested dissection hybrid", 84 howpublished="unpublished", 85 year="1995"} 86 87@misc{rothberg95, 88 AUTHOR="E. Rothberg", 89 howpublished="private communication", 90 year="1995"} 91 92@conference{rot96-mindefIdaho, 93 author="E. Rothberg", 94 title="Ordering sparse matrices 95 using approximate minimum local fill", 96 booktitle="Second SIAM Conference on Sparse Matrices", 97 year="1996", 98 note="Conference presentation"} 99 100@techreport{hr96-msndtalk, 101 author="B. Hendrickson and E. Rothberg", 102 title="Improving the runtime and quality of nested dissection 103 ordering", 104 booktitle="Second SIAM Conference on Sparse Matrices", 105 year="1996", 106 note="Conference presentation"} 107 108@conference{ng96-mindefIdaho, 109 author="E. Ng and P. Raghavan", 110 title="Minimum deficiency ordering", 111 booktitle="Second SIAM Conference on Sparse Matrices", 112 year="1996", 113 note="Conference presentation"} 114 115@article{gib76-profile, 116 AUTHOR = {N. E. Gibbs and W. G. Poole Jr and P. K. Stockmeyer}, 117 JOURNAL = {SIAM. J. Numer. Anal.}, 118 KEY = {LLt band profile}, 119 PAGES = {236-250}, 120 TITLE = {An algorithm for reducing the bandwidth and profile 121 of a sparse matrix}, 122 VOLUME = {13}, 123 YEAR = {1976} } 124 125@techreport{rag95-PCO, 126 author="P. Raghavan", 127 title="Parallel ordering using edge contraction", 128 number="CS-95-293", 129 institution="Dept. of Computer Science, The University of 130 Tennessee", 131 address="Knoxville, Tennessee", 132 year="1995"} 133 134@techreport{ame94-amdTR, 135 author="P. Amestoy and T. Davis and I. Duff", 136 title="An approximate minimum degree ordering algorithm", 137 number = "TR-94-039", 138 institution="University of Florida", 139 year="1994"} 140 141@techreport{hr96-msnd, 142 author="B. Hendrickson and E. Rothberg", 143 title="Improving the runtime and quality of nested dissection 144 ordering", 145 institution="Sandia National Laboratories", 146 year="1996"} 147 148@article{ash89-relaxed, 149 author="C. Ashcraft and R. Grimes", 150 title="The influence of relaxed supernode partitions on the 151 multifrontal method", 152 journal="ACM Trans. Math. Software", 153 volume="15", 154 year="1989", 155 pages="291-309"} 156 157@techreport{ash95-AGL, 158 author="C. Ashcraft and R. G. Grimes and J. G. Lewis", 159 title="Accurate symmetric indefinite linear equation solvers", 160 number="ISSTECH-95-029", 161 institution="Boeing Computer Services", 162 year="1995", 163 note="Accepted for publication in {\it SIAM J. Matrix. Anal.}"} 164 165@article{ash98-multisection, 166 author="C. Ashcraft and J. W. H. Liu", 167 title="Robust ordering of sparse matrices using multisection", 168 volume="19", 169 pages="816-832", 170 year="1998", 171 journal="SIAM J. Matrix. Anal."} 172 173@techreport{ash95-DDSEP, 174 author="C. Ashcraft and J. W. H. Liu", 175 title="Using domain decompositions to find graph bisectors", 176 number="ISSTECH-95-024", 177 institution="Boeing Computer Services", 178 year="1995", 179 note="Accepted for publication in {\it BIT}"} 180 181@techreport{ash95-robust, 182 author="C. Ashcraft and J. W. H. Liu", 183 title="Robust ordering of sparse matrices using multisection", 184 number="ISSTECH-96-002", 185 institution="Boeing Computer Services", 186 year="1996"} 187 188@article{ash98-maxflow, 189 author="C. Ashcraft and J. W. H. Liu", 190 title="Applications of the {D}ulmage-{M}endelsohn decomposition 191 and network flow to graph bisection improvement", 192 volume="19", 193 pages="325-354", 194 year="1999", 195 journal="SIAM J. Matrix. Anal."} 196 197@techreport{ash96-maxflow, 198 author="C. Ashcraft and J. W. H. Liu", 199 title="Applications of the {D}ulmage-{M}endelsohn decomposition 200 and network flow to graph bisection improvement", 201 number="ISSTECH-96-017", 202 institution="Boeing Computer Services", 203 year="1996", 204 note="Accepted for publication in {\it SIAM J. Matrix. Anal.}"} 205 206@techreport{ash93-compressed-graphs-TR, 207 author="C. Ashcraft", 208 title="Compressed graphs and the minimum degree algorithm", 209 number="BCSTECH-93-024", 210 institution="Boeing Computer Services", 211 year="1993"} 212 213@techreport{ash94-partition, 214 author="C. Ashcraft and J. W. H. Liu", 215 title="A partition improvement algorithm for generalized nested dissection", 216 number="BCSTECH-94-020", 217 institution="Boeing Computer Services", 218 year="1994"} 219 220@article{ber90-mindeg, 221 author="P. Berman and G. Schnitger", 222 title="On the performance of the minimum degree ordering for 223 {G}aussian elimination", 224 journal="SIAM J. Matrix Analysis and Applic.", 225 volume="11", 226 year="1990", 227 pages="83-88"} 228 229@article{bha93-localND, 230 author="M. V. Bhat and W. G. Habashi and J. W. H. Liu 231 and V. N. Nguyen and M. F. Peeters", 232 title="A note on nested dissection for rectangular grids", 233 journal="SIAM J. Matrix Analysis and Applic.", 234 volume="14", 235 year="1993", 236 pages="253-258"} 237 238@article{hr98-msnd, 239 author="B. Hendrickson and E. Rothberg", 240 title="Improving the runtime and quality of nested dissection 241 ordering", 242 pages={468-489}, 243 journal={SIAM J. Sci. Comput.}, 244 volume={20}, 245 year="1998"} 246 247@TechReport{ karypis98metis, 248 author = {G. Karypis and V. Kumar}, 249 title = {METIS~4.0: Unstructured graph partitioning and 250 sparse matrix ordering system}, 251 institution = {Department of Computer Science, 252 University of Minnesota}, 253 year = {1998}, 254 number = {}, 255 note = {Available on the WWW at URL 256 {\em http://www.cs.umn.edu/\~{}metis}} 257} 258 259@phdthesis{dam92-compressed, 260 author="A. C. Damhaug", 261 title="Sparse Solution of Finite Element Equations", 262 school="The Norwegian Institute of Technology", 263 year="1992"} 264 265@article{duf83-multifrontal, 266 author="I. Duff and J. Reid", 267 title="The multifrontal solution of indefinite sparse 268 symmetric linear equations", 269 journal="ACM Trans. Math. Software", 270 volume="6", 271 year="1983", 272 pages="302-325"} 273 274@inproceedings{eis76-elementModel, 275 author="S. C. Eisenstat and M. H. Schultz and A. H. Sherman", 276 title="Applications of an element model 277 for {G}aussian elimination", 278 booktitle="Sparse Matrix Computations", 279 pages="85-96", 280 publisher="Academic Press", 281 year="1976", 282 editor="J. R. Bunch and D. J. Rose"} 283 284@inproceedings{fid82-partition, 285 author="C. M. Fiduccia and R. M. Mattheyses", 286 title="A linear-time heuristic for improving network partition", 287 booktitle="ACM IEEE Proc. 19th Design Automation Conference, 288 Las Vegas, Nevada", 289 year="1982", 290 pages="175-181"} 291 292@article{geo80-1way, 293 author="J. A. George", 294 title="An automatic one-way dissection algorithm for irregular finite 295 element problems", 296 journal="SIAM J. Numer. Anal.", 297 volume="17", 298 year="1980", 299 pages="740-751"} 300 301@article{sparsematlab, 302 author="J. Gilbert and C. Moler and R. Schreiber", 303 title="Sparse matrices in {MATLAB}: design and implementation", 304 journal="SIAM J. Matrix Analysis and Applic.", 305 volume="13", 306 year="1992", 307 pages="335-356"} 308 309@techreport{gup96-WGPP, 310 author="A. Gupta", 311 title="{WGPP}: {W}atson {G}raph {P}artitioning and sparse matrix 312 ordering {P}ackage", 313 number="Users Manual", 314 institution="IBM T.J. Watson Research Center", 315 address="New York", 316 year="1996"} 317 318 319@techreport{hea92-dissection, 320 author="M.T. Heath and P. Raghavan", 321 title="A Cartesian nested dissection algorithm", 322 number="UIUCDCS-R-92-1772", 323 institution="Dept of Computer Science, University of Illinois", 324 address="Urbana, IL", 325 year="1992"} 326 327@techreport{hen92-partition, 328 author="B. Hendrickson and R. Leland", 329 title="An improved spectral graph partitioning algorithm for 330mapping parallel computations", 331 number="SAND92-1460", 332 institution="Sandia National Laboratories", 333 address="Albuquerque, NM", 334 year="1992"} 335 336@article{ker70-partition, 337 author="B. W. Kernighan and S. Lin", 338 title="An efficient heuristic procedure for partitioning graphs", 339 journal="Bell System Technical Journal", 340 volume="49", 341 year="1970", 342 pages="291-307"} 343 344@inproceedings{lei89-fidmat, 345 author="C. E. Leiserson and J. G. Lewis", 346 title="Orderings for parallel sparse symmetric factorization", 347 booktitle="Parallel Processing for Scientific Computing", 348 year="1989", 349 pages="27-31"} 350 351@article{lip79-separators, 352 author="R. J. Lipton and R. E. Tarjan", 353 title="A separator theorem for planar graphs", 354 journal="SIAM J. Applied Math", 355 volume="36", 356 year="1979", 357 pages="177-189"} 358 359@article{liu89-separators, 360 author="J. W. H. Liu", 361 title="A graph partitioning algorithm by node separators", 362 journal="ACM Trans. on Math. Software", 363 volume="15", 364 year="1989", 365 pages="198-219"} 366 367@article{liu85-mfstorage, 368 author="J. W. H. Liu", 369 title="On the storage requirement in the out-of-core 370 multifrontal method for sparse factorization", 371 journal="ACM Trans. on Math. Software", 372 volume="12", 373 year="1986", 374 pages="249-264"} 375 376@article{liu85-mmd, 377 author="J. W. H. Liu", 378 title="Modification of the minimum degree algorithm by 379 multiple elimination", 380 journal="ACM Trans. on Math. Software", 381 volume="11", 382 year="1985", 383 pages="141-153"} 384 385@article{liu89-mindeg, 386 author="J. W. H. Liu", 387 title="On the minimum degree ordering with constraints", 388 journal="SIAM J. Sci. Stat. Comput.", 389 volume="10", 390 year="1989", 391 pages="1136-1145"} 392 393@article{liu90-etree, 394 author="J. W. H. Liu", 395 title="The role of elimination trees in sparse factorization", 396 journal="SIAM J. Matrix Analysis and Applic.", 397 volume="11", 398 year="1990", 399 pages="134-172"} 400 401@article{liu91-generalizedEnvelope, 402 author="J. W. H. Liu", 403 title="A generalized envelope method 404 for sparse factorization by rows", 405 journal="ACM Trans. on Math. Software", 406 volume="17", 407 year="1991", 408 pages="112-129"} 409 410@article{mar57, 411 author="H. M. Markowitz", 412 title="The elimination form of the inverse and its application to 413 linear programming", 414 journal="Management Sci.", 415 volume="3", 416 year="1957", 417 pages="255-269"} 418 419@mastersthesis{ng79-master, 420 author="E. Ng", 421 title="On one-way dissection schemes", 422 school="Dept of Computer Science, University of Waterloo", 423 address="Waterloo, Ontario", 424 year="1979"} 425 426@techreport{rag93-separators, 427 author="P. Raghavan", 428 title="Line and plane separators", 429 number="UIUCDCS-R-93-1794", 430 institution="Dept of Computer Science, University of Illinois", 431 address="Urbana, IL", 432 year="1993"} 433 434@inproceedings{ros72-elimination, 435 author="D. J. Rose", 436 title="A graph-theoretic study of the numerical solution of sparse 437 positive definite systems of linear equations", 438 booktitle="Graph Theory and Computing", 439 publisher="Academic Press", 440 editor="R. Read", 441 year="1972", 442 pages="183-217"} 443 444@article{ros70-elimination, 445 author="D. J. Rose", 446 title="Triangulated graphs and the elimination process", 447 journal="J. Math. Anal. & Appl.", 448 volume="32", 449 year="1970", 450 pages="597-609"} 451 452@techreport{ten91-separators, 453 author="S.H. Teng", 454 title="Points, Spheres, and Separators", 455 number="CMU-CS-91-184", 456 institution="School of Computer Science, Carnegie Mellon University", 457 address="Pittsburgh, PA", 458 year="1991"} 459 460@article{tin67-order, 461 author="W. F. Tinney and J. W. Walker", 462 title="Direct solutions of sparse network equations by optimally ordered 463 triangular factorization", 464 journal="J Proc. IEEE", 465 volume="55", 466 year="1967", 467 pages="1801-1809"} 468 469@book{aho83, 470 author="A. V. Aho and J. E. Hopcroft and J. D. Ullman", 471 title="Data Structures and Algorithms", 472 publisher="Addison-Wesley", 473 address="Reading, MA", 474 year="1983"} 475 476@book{duf87-book, 477 author="I. S. Duff and A. M. Erisman and J. K. Reid", 478 title="Direct Methods for Sparse Matrices", 479 publisher="Oxford University Press", 480 address="London", 481 year="1987"} 482 483@article{ash87-progress, 484 AUTHOR = {C. Ashcraft and R. Grimes and J. Lewis and B. Peyton 485 and H. Simon}, 486 JOURNAL = {Intern. J. of Supercomputer Applications}, 487 KEY = {LLt vector}, 488 PAGES = {10-30}, 489 TITLE = {Progress in sparse matrix methods for large sparse 490 linear systems on vector supercomputers}, 491 VOLUME = {1}, 492 YEAR = {1987} 493} 494 495@techreport{ash90-partition, 496 author="C. Ashcraft", 497 title="The domain/segment partition for the factorization of sparse 498symmetric positive definite matrices", 499 number="ECA-TR-148", 500 institution="Boeing Computer Services", 501 address="Seattle, WA", 502 year="1990"} 503 504@article{ash95-compressed-graphs, 505 author="C. Ashcraft", 506 title="Compressed graphs and the minimum degree algorithm", 507 journal="SIAM J. Sci. Comput.", 508 pages = "1404-1411", 509 volume = 16, 510 year="1995"} 511 512@inproceedings{ash90-lookahead, 513 author="C. Ashcraft and S. C. Eisenstat and J. W. H. Liu and 514 B. W. Peyton and A. H. Sherman", 515 title="A compute-ahead fan-in scheme for parallel sparse 516 matrix factorization", 517 booktitle="Fourth Canadian Supercomputing Symposium (1990)", 518 editor="D. Pelletier", 519 year="June, 1990", 520 pages="351-361"} 521 522 523@inproceedings{ash94-multisection, 524 author="C. Ashcraft and J. W. H. Liu", 525 title="Generalized nested dissection: some recent progress", 526 booktitle="Fifth SIAM Conference on Applied Linear Algebra", 527 address="Snowbird, Utah", 528 year="June 18, 1994"} 529 530@inproceedings{bar93-partition, 531 author="S. T. Barnard and H. D. Simon", 532 title="A fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems", 533 booktitle="Proceedings of the Sixth SIAM Conference on Parallel Processing for Scientific Computing", 534 year="1993", 535 pages="711-718"} 536 537@inproceedings{bar95-partition, 538 author="S. T. Barnard and H. D. Simon", 539 title="A parallel implementation of multilevel recursive spectral bisection for applications in adaptive unstructured meshes", 540 booktitle="Proceedings of the seventh SIAM Conference on Parallel Processing for Scientific Computing", 541 year="1995", 542 pages="627-632"} 543 544@article{bui92-partition, 545 author="T. Bui and C. Jones", 546 title="Finding good approximate vertex and edge partitions is {NP}-hard", 547 journal="Information Processing Letters", 548 volume="42", 549 year="1992", 550 pages="153-159"} 551 552@inproceedings{bui93-partition, 553 author="T. Bui and C. Jones", 554 title="A heuristic for reducing fill-in in sparse matrix factorization", 555 booktitle="Proceedings of Sixth SIAM Conference on Parallel Processing ", 556 year="1993", 557 pages="445-452"} 558 559@article{geo73-nested, 560 author="J. A. George", 561 title="Nested dissection of a regular finite element mesh", 562 journal="SIAM J. Numer. Anal.", 563 volume="10", 564 year="1973", 565 pages="345-363"} 566 567@article{geo89-mindeg, 568 author="J.A. George and J. W. H. Liu", 569 title="The evolution of the minimum degree ordering algorithm", 570 journal="SIAM Review", 571 volume="31", 572 year="1989", 573 pages="1-19"} 574 575@techreport{goe95-partition, 576 author="T. Goehring and Y. Saad", 577 title="Heuristic algorithms for automatic graph partitioning", 578 number="", 579 institution="Computer Science Department, University of Minnesota", 580 address="Minnesota", 581 year="1995"} 582 583@article{hal35, 584 author = "P. Hall", 585 title = "On representatives of subsets", 586 journal = "J. London Math. Society", 587 volume = "10", 588 year = "1935", 589 pages = "26-30"} 590 591@article{Harwell-Boeing-Matrices, 592 author = "I.S. Duff and R.G. Grimes and J.G. Lewis", 593 title = "Sparse matrix test problems", 594 journal="ACM Trans. on Math. Software", 595 volume = "15", 596 year = "1989", 597 pages = "1-14"} 598 599@techreport{sparspak80, 600 author="J. A. George and J. W. H. Liu and E. G. Ng", 601 title="User's guide for {SPARSPAK}: {W}aterloo sparse linear 602 equations package", 603 number = "Tech. Rep. CS78-30(revised)", 604 institution = "Dept. of Computer Sciences, Univ. of Waterloo", 605 address="Waterloo, Ontario, Canada", 606 year = "1980"} 607 608@techreport{hen93-spectral, 609 author="B. Hendrickson and R. Leland", 610 title="Multidimensional spectral load balancing", 611 number="SAND93-074", 612 institution="Sandia National Laboratories", 613 address="Albuquerque, NM", 614 year="1993"} 615 616@techreport{kar95-kway, 617 author="G. Karypis and V. Kumar", 618 title="Multilevel $k$-way partitioning scheme for irregular graphs", 619 institution="Department of Computer Science, University of Minnesota", 620 address="Minnesota", 621 year="1995"} 622% number="Technical Report", 623 624@techreport{kar95-multilevel, 625 author="G. Karypis and V. Kumar", 626 title="A fast and high quality multilevel scheme for partitioning irregular graphs", 627 number="TR 95-035", 628 institution="Department of Computer Science, University of Minnesota", 629 address="Minnesota", 630 year="1995"} 631 632@techreport{kar95-metis, 633 author="G. Karypis and V. Kumar", 634 title="{METIS}: Unstructured graph partitioning and sparse matrix ordering system", 635 institution="Department of Computer Science, University of Minnesota", 636 address="Minnesota", 637 year="1995"} 638% number="TR 95-???", 639 640@techreport{kar95-partition, 641 author="G. Karypis and V. Kumar", 642 title="Analysis of multilevel graph partitioning", 643 number="TR 95-037", 644 institution="Department of Computer Science, University of Minnesota", 645 address="Minnesota", 646 year="1995"} 647 648@inproceedings{kar95, 649 author="G. Karypis and V. Kumar", 650 title="Multilevel graph partition and sparse matrix ordering", 651 booktitle="Intl. Conf. on Parallel Processing", 652 year="1995"} 653 654@article{lip79, 655 author="R. J. Lipton and R. E. Tarjan", 656 title="A separator theorem for planar graphs", 657 journal="SIAM J. Applied Math", 658 volume="36", 659 year="1979", 660 pages="177-189"} 661 662@techreport{mai94-partition, 663 author="H.S. Maini and K.G. Mehrotra and S. Ranka", 664 title="Genetic algorithms for graph partitioning and incremental 665 graph partitioning", 666 number="Technical report", 667 institution="Center for Science and Technology, Syracuse University", 668 address="Synracuse, N.Y.", 669 year="1994"} 670 671@article{pot90-triangular, 672 author="A. Pothen and C. Fan", 673 title="Computing the block triangular form of a sparse matrix", 674 journal="ACM Trans. on Math. Software", 675 volume="16", 676 year="1990", 677 pages="303-324"} 678 679@article{pot90-partition, 680 author="A. Pothen and H. Simon and K.P. Liou", 681 title="Partitioning sparse matrices with eigenvectors of graphs", 682 journal="SIAM J. Matrix Analysis and Applic.", 683 volume="11", 684 year="1990", 685 pages="430-452"} 686 687@book{aho83, 688 author="A. V. Aho and J. E. Hopcroft and J. D. Ullman", 689 title="Data Structures and Algorithms", 690 publisher="Addison-Wesley", 691 address="Reading, MA", 692 year="1983"} 693 694@book{ull84-vlsi, 695 author="J. D. Ullman", 696 title="Computational Aspects of VLSI", 697 publisher="Computer Science Press", 698 address="Rockville, Md", 699 year="1984"} 700 701@book{duf87-book, 702 author="I. S. Duff and A. M. Erisman and J. K. Reid", 703 title="Direct Methods for Sparse Matrices", 704 publisher="Oxford University Press", 705 address="London", 706 year="1987"} 707 708@book{zzzz99-book, 709 author="J. A. George and J. W. H. Liu", 710 title="Computer Solution of Large Sparse Positive Definite Systems", 711 publisher="Prentice-Hall", 712 address="Englewood Cliffs, NJ", 713 year="1981"} 714 715 716@article{arn85, 717 author="S. Arnborg", 718 title="Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey", 719 journal="BIT", 720 volume="25", 721 year="1985", 722 pages="2-23"} 723 724@techreport{bar81, 725 author="E. R. Barnes", 726 title="An algorithm for partitioning the nodes of a graph", 727 number="RC8690", 728 institution="IBM Thomas J. Watson Research Center", 729 address="Yorktown Heights, New York", 730 year="1981"} 731 732@inproceedings{bar85, 733 author="E. R. Barnes", 734 title="Partitioning the nodes of a graph", 735 booktitle="Graph Theory with Applications to Algorithms and Computer Science", 736 editor="Y. Alavi and G. Chartrand and D. Lick and C. Wall and L. Lesuiak", 737 publisher="John Wiley \& Sons Inc.", 738 address="New York", 739 year="1985", 740 pages="57-72"} 741 742@article{bha84, 743 author="S. N. Bhatt and F. T. Leighton", 744 title="A framework for solving {VLSI} graph layout problems", 745 journal="Journal of Computer \& Systems Sciences", 746 volume="28", 747 year="1984", 748 pages=""} 749 750@inproceedings{bre77, 751 author="M. A. Breuer", 752 title="A class of min-cut placement algorithms", 753 booktitle="Proc. 14th Design Automation Conference", 754 year="1977", 755 pages="284-290"} 756 757@inproceedings{bui84, 758 author="S. N. Bui and S. Chaudhuri and T. Leighton and M. Sipser", 759 title="Graph bisection algorithms with good average case behavior", 760 booktitle="Proceedings of the 25th Annual Symposium of Foundations of Computer Science", 761 year="1984", 762 pages="181-192"} 763 764@article{dji81, 765 author="H. N. Djidjev", 766 title="A separator theorem", 767 journal="Comptes rendus de l' Academie bulgare des Sciences", 768 volume="34", 769 year="1981", 770 pages="643-645"} 771 772@article{dji82-linear, 773 author="H. N. Djidjev", 774 title="A linear algorithm for partitioning graphs", 775 journal="Comptes rendus de l' Academie bulgare des Sciences", 776 volume="35", 777 year="1982", 778 pages="1053-1056"} 779 780@article{dji82-planar, 781 author="H. N. Djidjev", 782 title="On the problem of partitioning planar graphs", 783 journal="SIAM J. Alg. \& Disc. Meth.", 784 volume="3", 785 year="1982", 786 pages="229-240"} 787 788@article{don72, 789 author="W. E. Donath and A. J. Hoffman", 790 title="Algorithms for partitioning of graphs and computer logic based on eigenvectors of connection matrices", 791 journal="IBM Technical Disclosure Bulletin", 792 volume="15", 793 year="1972", 794 pages="938-944"} 795 796@article{don73, 797 author="W. E. Donath and A. J. Hoffman", 798 title="Lower bounds for the partitioning of graphs", 799 journal="IBM J. Res. Develop.", 800 volume="17", 801 year="1973", 802 pages="420-425"} 803 804@article{fie73, 805 author="M. Fiedler", 806 title="Algebraic connectivity of graphs", 807 journal="Czechoslovak Math J.", 808 volume="23", 809 year="1973", 810 pages="298-305"} 811 812@book{fre86, 813 author="G. N. Fredrickson and R. Janardan", 814 title="Separator-based strategies for efficient message routing", 815 booktitle="27th Annual Symposium on Foundation of Computer Science", 816 publisher="IEEE", 817 year="1986", 818 pages="428-437"} 819 820@book{gaz87, 821 author="H. Gazit and G. L. Miller", 822 title="A parallel algorithm for finding a separator in planar graphs", 823 booktitle="28th Annual Symposium on Foundation of Computer Science", 824 publisher="IEEE", 825 year="1987", 826 pages="238-248"} 827 828@techreport{gil80, 829 author="J. R. Gilbert", 830 title="Graph separator theorems and sparse {G}aussian elimination", 831 number="Ph.D. Thesis", 832 institution="DCS, Stanford University", 833 year="1980"} 834 835@article{gil84-genus, 836 author="J. R. Gilbert and J. P. Hutchinson and R. E. Tarjan", 837 title="A separator theorem for graphs of bounded genus", 838 journal="J. of Algorithms", 839 volume="5", 840 year="1984", 841 pages="391-407"} 842 843@article{gil84-chordal, 844 author="J. R. Gilbert and D. J. Rose and A. Edenbrandt", 845 title="A separator theorem for chordal graphs", 846 journal="SIAM J. Alg. \& Disc. Meth.", 847 volume="5", 848 year="1984", 849 pages="306-313"} 850 851@inproceedings{gol83, 852 author="M. K. Goldberg and M. Burstein", 853 title="Heuristic improvement technique for bisection of {VLSI} networks", 854 booktitle="Proc. IEEE International Conf. on Computer Design", 855 address="Port Chester, New York", 856 year="1983", 857 pages="122-125"} 858 859@techreport{gol87, 860 author="M. K. Goldberg and S. Lath and J. W. Roberts", 861 title="Heuristics for the graph bisection problem", 862 number="Report", 863 institution="Rensselaer Polytechnic Institute", 864 year="1987"} 865 866@techreport{hen92, 867 author="B. Hendrickson and R. Leland", 868 title="An improved spectral graph partitioning algorithm for mapping parallel computations", 869 number="SAND92-1460", 870 institution="Sandia National Laboratories", 871 address="Albuquerque, NM", 872 year="1992"} 873 874@techreport{hen93, 875 author="B. Hendrickson and R. Leland", 876 title="Multidimensional spectral load balancing", 877 number="SAND93-074", 878 institution="Sandia National Laboratories", 879 address="Albuquerque, NM", 880 year="1993"} 881 882@article{hu81, 883 author="T. C. Hu and M. T. Shing", 884 title="An O(n) algorithm to find a near-optimum partition", 885 journal="Journal of Algorithms", 886 volume="2", 887 year="1981", 888 pages="122-138"} 889 890@article{hu85, 891 author="T. C. Hu and M. T. Shing", 892 title="A decomposition algorithm for circuit routing", 893 journal="Math. Programming Study", 894 volume="24", 895 year="1985", 896 pages="87-103"} 897 898@article{hu86, 899 author="T. C. Hu and M. T. Shing", 900 title="A decomposition algorithm for multi-terminal network flows", 901 journal="J. Discrete Applied Math.", 902 volume="13", 903 year="1986", 904 pages="165-181"} 905 906@article{joh88, 907 author="D. S. Johnson and C. R. Aragon and L. A. McGeoch and C. Schevon", 908 title="Optimization by simulated annealing: an experimental evaluation", 909 journal="Operations Research", 910 note="((submitted))", 911 year="1988"} 912 913@article{kan91, 914 author="A. Kanevsky and V. Ramachandran", 915 title="Improved algorithms for graph four-connectivity", 916 journal="J. of Computer Science and Systems", 917 volume="42", 918 year="1991", 919 pages="288-306"} 920 921@article{kan9x, 922 author="A. Kanevsky", 923 title="Finding all minimum size vertex sets in a graph", 924 journal="J. of Networks", 925 year="199x"} 926 927@inproceedings{kan90, 928 author="A. Kanevsky", 929 title="On the number of minimum size separating vertex sets of a graph and how to find all of them", 930 booktitle="First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '90)", 931 year="January 22-24,1990", 932 pages="411-421"} 933 934@article{kao90, 935 author="M. Kao and F. Wan", 936 title="Not all planar digraphs have small cycle separators", 937 journal="Information Processing Letters", 938 year="1990"} 939 940@techreport{ker69, 941 author="B. W. Kernighan", 942 title="Some graph partitioning problems related to program segmentation", 943 number="Ph.D. Thesis", 944 institution="Princeton University", 945 year="1969"} 946 947@article{ker70, 948 author="B. W. Kernighan and S. Lin", 949 title="An efficient heuristic procedure for partitioning graphs", 950 journal="Bell System Technical Journal", 951 volume="49", 952 year="1970", 953 pages="291-307"} 954 955@article{kir83, 956 author="S. Kirkpatrick and C. D. Gelatt Jr. and M. P. Vecchi", 957 title="Optimization by simulated annealing", 958 journal="Science", 959 volume="220", 960 year="1983", 961 pages="671-680"} 962 963@article{kom85, 964 author="J. Komlos and M. T. Shing", 965 title="Probabilistic partitioning algorithms for the rectilinear Steiner problem", 966 journal="Networks", 967 volume="15", 968 year="1985", 969 pages="413-423"} 970 971@article{kri84, 972 author="B. Krishnamurthy", 973 title="An improved min-cut algorithm for partitioning {VLSI} networks", 974 journal="IEEE Trans. on Computers", 975 volume="C-33", 976 year="1984", 977 pages="438-446"} 978 979@article{kri87, 980 author="B. Krishnamurthy", 981 title="Constructing test cases for partitioning heuristics", 982 journal="IEEE Trans. on Computers", 983 volume="C-36", 984 year="198", 985 pages="1112-1114"} 986 987@inproceedings{lei82, 988 author="F. T. Leighton", 989 title="A layout strategy for {VLSI} which is provably good", 990 booktitle="Proceedings of the 14th Annual ACM Symposium on Theory of Computing", 991 year="1982", 992 pages="85-98"} 993 994@book{lei80, 995 author="C. Leiserson", 996 title="Area-efficient graph layout (for vlsi)", 997 booktitle="21st Annual Symposium on Foundation of Computer Science", 998 publisher="IEEE", 999 year="1980", 1000 pages="270-281"} 1001 1002@article{lin77, 1003 author="T. D. Lin and R. S. H. Mah", 1004 title="Hierarchical partition -- a new optimal pivoting algorithm", 1005 journal="Math. Programming", 1006 volume="12", 1007 year="1977", 1008 pages="260-278"} 1009 1010@article{lip80, 1011 author="R. J. Lipton and R. E. Tarjan", 1012 title="Applications of a planar separator theorem", 1013 journal="SICOMP", 1014 volume="9", 1015 year="1980", 1016 pages="615-627"} 1017 1018@techreport{mac78, 1019 author="R. M. Macgregor", 1020 title="On partitioning a graph: a theoretical and empirical study", 1021 number="UCB/ERL M78/14 (Ph.D. Thesis)", 1022 institution="Standford University", 1023 year="1978"} 1024 1025@inproceedings{mil84, 1026 author="G. L. Miller", 1027 title="Finding small simple cycle separators for 2-connected planar graphs", 1028 booktitle="Proceedings of the 16th Annual ACM Symposium on Theory of Computing", 1029 year="1984", 1030 pages="376-382"} 1031 1032@techreport{moo88, 1033 author="D. Moore", 1034 title="A round-robin parallel partitioning algorithm", 1035 number="TR 88-916", 1036 institution="DCS, Cornell University", 1037 year="1988"} 1038 1039@article{pai87, 1040 author="R. Paige and R. E. Tarjan", 1041 title="Three partition refinement algorithm", 1042 journal="SICOMP", 1043 volume="16", 1044 year="1987", 1045 pages="973-989"} 1046 1047@article{pow88, 1048 author="D. Powers", 1049 title="Graph partitioning by eigenvectors", 1050 journal="Lin. Alg. Appl.", 1051 volume="101", 1052 year="1988", 1053 pages="121-133"} 1054 1055@book{rao87, 1056 author="S. Rao", 1057 title="Finding near optimal separators in planar graphs", 1058 booktitle="28th Annual Symposium on Foundation of Computer Science", 1059 publisher="IEEE", 1060 year="1987", 1061 pages="225-237"} 1062 1063@article{rav87, 1064 author="S. Ravi and H. Hunt III", 1065 title="An application of the planar separator theorem to counting problem", 1066 journal="Inform. Process. Letters", 1067 volume="25", 1068 year="1987", 1069 pages="317-322"} 1070 1071@techreport{ren90, 1072 author="F. Rendl and H. Wolkowicz", 1073 title="A projection technique for partitioning the nodes of a graph", 1074 number="CORR 90-20", 1075 institution="University of Waterloo", 1076 address="Waterloo, Ontario", 1077 year="1990"} 1078 1079@inproceedings{san76, 1080 author="A. Sangiovanni-Vincentelli", 1081 title="An optimization problem arising from tearing methods", 1082 booktitle="Sparse Matrix Computations", 1083 editor="J.R. Bunch and D.J. Rose", 1084 publisher="Academic Press", 1085 year="1976", 1086 pages="97-110"} 1087 1088@inproceedings{sch79, 1089 author="D. G. Schweikert and B. W. Kernighan", 1090 title="A proper model for the partitioning of electrical circuits", 1091 booktitle="Proc. 9th Design Automation Workshop", 1092 year="1979", 1093 pages="57-62"} 1094 1095@article{sen92, 1096 author="A. Sen and H. Deng and S. Guha", 1097 title="On a graph partition problem with application to vlsi layout", 1098 journal="Information Processing Letters", 1099 year="1992", 1100 volume="43", 1101 pages="87-94"} 1102 1103@techreport{she87, 1104 author="T. J. Sheffler", 1105 title="A graph separator theorem and its application to {G}aussian elimination to optimize {B}oolean expression for parallel evaluation", 1106 number="CMU-CS-87-123", 1107 institution="DCS, Carnegie-Mellon University", 1108 year="1987"} 1109 1110@inproceedings{shi80, 1111 author="H. Shiraishi and F. Hirose", 1112 title="Efficient placement and routing for masterslice {LSI}", 1113 booktitle="Proc. 17th Design Automation Conference", 1114 year="1980", 1115 pages="458-464"} 1116 1117@article{sua88, 1118 author="P. Suaris and G. Kedem", 1119 title="An algorithm for quadrisection and its application to standard cell placement", 1120 journal="IEEE Trans. Circuits and Systems", 1121 volume="35", 1122 year="1988", 1123 pages="294-303"} 1124 1125@article{tar??, 1126 author="R. E. Tarjan", 1127 title="Decomposition by clique separators", 1128 journal="Discrete Math", 1129 year="to appear"} 1130 1131@article{ven87, 1132 author="S. Venkatesan", 1133 title="Improved constants for some separator theorems", 1134 journal="J. Algorithms", 1135 volume="8", 1136 year="1987", 1137 pages="572-578"} 1138 1139@article{wan91, 1140 author="F. Wan", 1141 title="A linear-processor algorithm for finding small cycle separators on undirected planar graphs", 1142 journal="SICOMP", 1143 year="1991?"} 1144 1145@article{whi81, 1146 author="S. H. Whitesides", 1147 title="An algorithm for finding clique cutsets", 1148 journal="Inf. Proc. Letters", 1149 volume="12", 1150 year="1981", 1151 pages="31-32"} 1152 1153@incollection{matrixmarket97, 1154 author="R. F. Boisvert and R. Pozo and K. Remington 1155 and R. F. Barrett and J. J. Dongarra", 1156 title="Matrix {M}arket: a web resource for test matrix collections", 1157 booktitle="The Quality of Numerical Software: 1158 Assessment and Enhancement", 1159 publisher="Chapman and Hall, London", 1160 year="1997", 1161 editor="R. F. Boisvert", 1162 pages="125-137"} 1163 1164@article{ne92-rook, 1165 author="L. Neal and G. Poole", 1166 title="A geometric analysis of {G}aussian elimination {II}.", 1167 journal="Linear Alg. and Appl.", 1168 volume="173", 1169 year="1992", 1170 pages="239-264"} 1171 1172@misc{fo96-rook, 1173 author="L. V. Foster", 1174 title="The growth factor and efficiency of {G}aussian 1175 elimination with rook pivoting", 1176 note="Accepted for publication in {\it J. Comp. and Appl. Math.}"} 1177 1178@incollection{ash93-fan-both, 1179 author="C. Ashcraft", 1180 booktitle="Graph Theory and Sparse Matrix Computation", 1181 title="The fan-both family of column-based distributed 1182 {C}holesky factorization algorithms", 1183 pages="159-190", 1184 publisher="Springer-Verlag", 1185 year="1993"} 1186 1187@article{ash90-fan-in, 1188 author="C. Ashcraft and S. Eisenstat and J. W. H. Liu", 1189 title="A fan-in algorithm for 1190 distributed sparse numerical factorization", 1191 journal="SIAM J. Sci. Stat. Comput.", 1192 volume="11", 1193 year="1990"} 1194 1195@proceedings{geo87-fan-out, 1196 author="J. A. George and J. W. H. Liu and E. Ng", 1197 title="Communication reduction in parallel 1198 sparse {C}holesky on a hypercube", 1199 booktitle="Hypercube Multiprocessors 1987", 1200 editor="M. Heath", 1201 publisher="SIAM Press", 1202 year="1987"} 1203 1204@article{sch82-etree, 1205 author="R. Schreiber", 1206 journal="ACM Trans. Math. Soft.", 1207 title="A new implementation of sparse {G}aussian elimination", 1208 pages="256-276", 1209 year="1982"} 1210 1211@book{hig96-asna, 1212 author="N. J. Higham", 1213 title="Accuracy and Stability of Numerical Algorithms", 1214 publisher="SIAM", 1215 year="1996"} 1216 1217@article{and90-random, 1218 author="S. L. Anderson", 1219 title="Random number generators on vector supercomputers 1220 and other advanced architectures", 1221 journal="SIAM Review", 1222 volume="32", 1223 year="1990", 1224 pages="221-251"} 1225 1226@misc{ash94-utah, 1227 author="C. Ashcraft and J. W. H. Liu", 1228 title="Generalized nested dissection: some recent progress", 1229 howpublished="Minisymposium presentation at 1230 the Fifth SIAM Conference on Applied Linear Algebra, 1231 Snowbird, Utah", 1232 year="June 18, 1994"} 1233 1234@misc{rothberg95, 1235 AUTHOR="E. Rothberg", 1236 howpublished="private communication", 1237 year="1995"} 1238 1239@article{gib76-profile, 1240 AUTHOR = {N. E. Gibbs and W. G. Poole Jr and P. K. Stockmeyer}, 1241 JOURNAL = {SIAM. J. Numer. Anal.}, 1242 KEY = {LLt band profile}, 1243 PAGES = {236-250}, 1244 TITLE = {An algorithm for reducing the bandwidth and profile 1245 of a sparse matrix}, 1246 VOLUME = {13}, 1247 YEAR = {1976} } 1248 1249@techreport{ame94-amdTR, 1250 author="P. Amestoy and T. Davis and I. Duff", 1251 title="An approximate minimum degree ordering algorithm", 1252 number = "TR-94-039", 1253 institution="University of Florida", 1254 year="1994"} 1255 1256@article{ame96-amd, 1257 author="P. Amestoy and T. Davis and I. Duff", 1258 title="An approximate minimum degree ordering algorithm", 1259 journal="SIAM J. Matrix Anal. Appl.", 1260 volume="17", 1261 pages="886-905", 1262 year="1996"} 1263 1264@techreport{ash95-pivoting, 1265 author="C. Ashcraft and R. G. Grimes and J. G. Lewis", 1266 title="Accurate symmetric indefinite linear equation solvers", 1267 number="ISSTECH-95-029", 1268 institution="Boeing Computer Services", 1269 year="1995"} 1270 1271@techreport{ash95-robust, 1272 author="C. Ashcraft and J. W. H. Liu", 1273 title="Robust ordering of sparse matrices using multisection", 1274 number="ISSTECH-96-002", 1275 institution="Boeing Computer Services", 1276 year="1996"} 1277 1278@techreport{ash93-compressed-graphs-TR, 1279 author="C. Ashcraft", 1280 title="Compressed graphs and the minimum degree algorithm", 1281 number="BCSTECH-93-024", 1282 institution="Boeing Computer Services", 1283 year="1993"} 1284 1285@article{ber90-mindeg, 1286 author="P. Berman and G. Schnitger", 1287 title="On the performance of the minimum degree ordering for 1288 {G}aussian elimination", 1289 journal="SIAM J. Matrix Analysis and Applic.", 1290 volume="11", 1291 year="1990", 1292 pages="83-88"} 1293 1294@phdthesis{dam92-compressed, 1295 author="A. C. Damhaug", 1296 title="Sparse Solution of Finite Element Equations", 1297 school="The Norwegian Institute of Technology", 1298 year="1992"} 1299 1300@inproceedings{eis76-elementModel, 1301 author="S. C. Eisenstat and M. H. Schultz and A. H. Sherman", 1302 title="Applications of an element model 1303 for {G}aussian elimination", 1304 booktitle="Sparse Matrix Computations", 1305 pages="85-96", 1306 publisher="Academic Press", 1307 year="1976", 1308 editor="J. R. Bunch and D. J. Rose"} 1309 1310@article{geo80-1way, 1311 author="J. A. George", 1312 title="An automatic one-way dissection algorithm for irregular finite 1313 element problems", 1314 journal="SIAM J. Numer. Anal.", 1315 volume="17", 1316 year="1980", 1317 pages="740-751"} 1318 1319@article{sparsematlab, 1320 author="J. Gilbert and C. Moler and R. Schreiber", 1321 title="Sparse matrices in {MATLAB}: design and implementation", 1322 journal="SIAM J. Matrix Analysis and Applic.", 1323 volume="13", 1324 year="1992", 1325 pages="335-356"} 1326 1327@techreport{hea92-dissection, 1328 author="M.T. Heath and P. Raghavan", 1329 title="A Cartesian nested dissection algorithm", 1330 number="UIUCDCS-R-92-1772", 1331 institution="Dept of Computer Science, University of Illinois", 1332 address="Urbana, IL", 1333 year="1992"} 1334 1335@techreport{hen92-partition, 1336 author="B. Hendrickson and R. Leland", 1337 title="An improved spectral graph partitioning algorithm for 1338mapping parallel computations", 1339 number="SAND92-1460", 1340 institution="Sandia National Laboratories", 1341 address="Albuquerque, NM", 1342 year="1992"} 1343 1344@article{ker70-partition, 1345 author="B. W. Kernighan and S. Lin", 1346 title="An efficient heuristic procedure for partitioning graphs", 1347 journal="Bell System Technical Journal", 1348 volume="49", 1349 year="1970", 1350 pages="291-307"} 1351 1352@article{lip79-separators, 1353 author="R. J. Lipton and R. E. Tarjan", 1354 title="A separator theorem for planar graphs", 1355 journal="SIAM J. Applied Math", 1356 volume="36", 1357 year="1979", 1358 pages="177-189"} 1359 1360@article{liu89-separators, 1361 author="J. W. H. Liu", 1362 title="A graph partitioning algorithm by node separators", 1363 journal="ACM Trans. on Math. Software", 1364 volume="15", 1365 year="1989", 1366 pages="198-219"} 1367 1368@article{liu85-mfstorage, 1369 author="J. W. H. Liu", 1370 title="On the storage requirement in the out-of-core 1371 multifrontal method for sparse factorization", 1372 journal="ACM Trans. on Math. Software", 1373 volume="12", 1374 year="1986", 1375 pages="249-264"} 1376 1377@article{liu89-mindeg, 1378 author="J. W. H. Liu", 1379 title="On the minimum degree ordering with constraints", 1380 journal="SIAM J. Sci. Stat. Comput.", 1381 volume="10", 1382 year="1989", 1383 pages="1136-1145"} 1384 1385@article{liu91-generalizedEnvelope, 1386 author="J. W. H. Liu", 1387 title="A generalized envelope method 1388 for sparse factorization by rows", 1389 journal="ACM Trans. on Math. Software", 1390 volume="17", 1391 year="1991", 1392 pages="112-129"} 1393 1394@article{mar57, 1395 author="H. M. Markowitz", 1396 title="The elimination form of the inverse and its application to 1397 linear programming", 1398 journal="Management Sci.", 1399 volume="3", 1400 year="1957", 1401 pages="255-269"} 1402 1403@mastersthesis{ng79-master, 1404 author="E. Ng", 1405 title="On one-way dissection schemes", 1406 school="Dept of Computer Science, University of Waterloo", 1407 address="Waterloo, Ontario", 1408 year="1979"} 1409 1410@techreport{rag93-separators, 1411 author="P. Raghavan", 1412 title="Line and plane separators", 1413 number="UIUCDCS-R-93-1794", 1414 institution="Dept of Computer Science, University of Illinois", 1415 address="Urbana, IL", 1416 year="1993"} 1417 1418@inproceedings{ros72-elimination, 1419 author="D. J. Rose", 1420 title="A graph-theoretic study of the numerical solution of sparse 1421 positive definite systems of linear equations", 1422 booktitle="Graph Theory and Computing", 1423 publisher="Academic Press", 1424 editor="R. Read", 1425 year="1972", 1426 pages="183-217"} 1427 1428@article{ros70-elimination, 1429 author="D. J. Rose", 1430 title="Triangulated graphs and the elimination process", 1431 journal="J. Math. Anal. & Appl.", 1432 volume="32", 1433 year="1970", 1434 pages="597-609"} 1435 1436@techreport{ten91-separators, 1437 author="S.H. Teng", 1438 title="Points, Spheres, and Separators", 1439 number="CMU-CS-91-184", 1440 institution="School of Computer Science, Carnegie Mellon University", 1441 address="Pittsburgh, PA", 1442 year="1991"} 1443 1444@article{tin67-order, 1445 author="W. F. Tinney and J. W. Walker", 1446 title="Direct solutions of sparse network equations by optimally ordered 1447 triangular factorization", 1448 journal="J Proc. IEEE", 1449 volume="55", 1450 year="1967", 1451 pages="1801-1809"} 1452 1453@book{aho83, 1454 author="A. V. Aho and J. E. Hopcroft and J. D. Ullman", 1455 title="Data Structures and Algorithms", 1456 publisher="Addison-Wesley", 1457 address="Reading, MA", 1458 year="1983"} 1459 1460@book{duf87-book, 1461 author="I. S. Duff and A. M. Erisman and J. K. Reid", 1462 title="Direct Methods for Sparse Matrices", 1463 publisher="Oxford University Press", 1464 address="London", 1465 year="1987"} 1466 1467@book{geo81-book, 1468 author="J. A. George and J. W. H. Liu", 1469 title="Computer Solution of Large Sparse Positive Definite Systems", 1470 publisher="Prentice-Hall", 1471 address="Englewood Cliffs, NJ", 1472 year="1981"} 1473 1474@article{ash87-progress, 1475 AUTHOR = {C. Ashcraft and R. Grimes and J. Lewis and B. Peyton 1476 and H. Simon}, 1477 JOURNAL = {Intern. J. of Supercomputer Applications}, 1478 KEY = {LLt vector}, 1479 PAGES = {10-30}, 1480 TITLE = {Progress in sparse matrix methods for large sparse 1481 linear systems on vector supercomputers}, 1482 VOLUME = {1}, 1483 YEAR = {1987} 1484} 1485 1486@techreport{ash90-partition, 1487 author="C. Ashcraft", 1488 title="The domain/segment partition for the factorization of sparse 1489symmetric positive definite matrices", 1490 number="ECA-TR-148", 1491 institution="Boeing Computer Services", 1492 address="Seattle, WA", 1493 year="1990"} 1494 1495@article{ash95-compressed-graphs, 1496 author="C. Ashcraft", 1497 title="Compressed graphs and the minimum degree algorithm", 1498 journal="SIAM J. Sci. Comput.", 1499 pages = "1404-1411", 1500 volume = 16, 1501 year="1995"} 1502 1503@techreport{AELS90-comparison, 1504 author="C. Ashcraft and S. Eisenstat and J. Liu and A. Sherman", 1505 title="A comparison of three distributed column based distributed 1506 factorization schemes", 1507 number="Technical Report YALEU/DCS/RR-810", 1508 institution="Department of Computer Science, Yale University", 1509 year="1990"} 1510 1511@inproceedings{ash94-multisection, 1512 author="C. Ashcraft and J. W. H. Liu", 1513 title="Generalized nested dissection: some recent progress", 1514 booktitle="Fifth SIAM Conference on Applied Linear Algebra", 1515 address="Snowbird, Utah", 1516 year="June 18, 1994"} 1517 1518@inproceedings{bar95-partition, 1519 author="S. T. Barnard and H. D. Simon", 1520 title="A parallel implementation of multilevel recursive spectral bisection for applications in adaptive unstructured meshes", 1521 booktitle="Proceedings of the seventh SIAM Conference on Parallel Processing for Scientific Computing", 1522 year="1995", 1523 pages="627-632"} 1524 1525@article{bui92-partition, 1526 author="T. Bui and C. Jones", 1527 title="Finding good approximate vertex and edge partitions is {NP}-hard", 1528 journal="Information Processing Letters", 1529 volume="42", 1530 year="1992", 1531 pages="153-159"} 1532 1533@article{geo89-mindeg, 1534 author="J.A. George and J. W. H. Liu", 1535 title="The evolution of the minimum degree ordering algorithm", 1536 journal="SIAM Review", 1537 volume="31", 1538 year="1989", 1539 pages="1-19"} 1540 1541@techreport{goe95-partition, 1542 author="T. Goehring and Y. Saad", 1543 title="Heuristic algorithms for automatic graph partitioning", 1544 number="", 1545 institution="Computer Science Department, University of Minnesota", 1546 address="Minnesota", 1547 year="1995"} 1548 1549@article{hal35, 1550 author = "P. Hall", 1551 title = "On representatives of subsets", 1552 journal = "J. London Math. Society", 1553 volume = "10", 1554 year = "1935", 1555 pages = "26-30"} 1556 1557@article{dul58, 1558 author = "A.L. Dulmage and N.S. Mendelsohn", 1559 title = "Coverings of bipartite graphs", 1560 journal="Can. J. Math", 1561 volume = "10", 1562 year = "1958", 1563 pages = "517-534"} 1564 1565@techreport{sparspak80, 1566 author="J. A. George and J. W. H. Liu and E. G. Ng", 1567 title="User's guide for {SPARSPAK}: {W}aterloo sparse linear 1568 equations package", 1569 number = "Tech. Rep. CS78-30(revised)", 1570 institution = "Dept. of Computer Sciences, Univ. of Waterloo", 1571 address="Waterloo, Ontario, Canada", 1572 year = "1980"} 1573 1574@techreport{hen93-chaco, 1575 author="B. Hendrickson and R. Leland", 1576 title="The {C}haco user's guide", 1577 number="SAND93-2339", 1578 institution="Sandia National Laboratories", 1579 address="Albuquerque, NM", 1580 year="1993"} 1581 1582@techreport{hen93-partition, 1583 author="B. Hendrickson and R. Leland", 1584 title="A multilevel algorithm for partitioning graphs", 1585 number="SAND93-1301", 1586 institution="Sandia National Laboratories", 1587 address="Albuquerque, NM", 1588 year="1993"} 1589 1590@techreport{hen93-spectral, 1591 author="B. Hendrickson and R. Leland", 1592 title="Multidimensional spectral load balancing", 1593 number="SAND93-074", 1594 institution="Sandia National Laboratories", 1595 address="Albuquerque, NM", 1596 year="1993"} 1597 1598@techreport{kar95-kway, 1599 author="G. Karypis and V. Kumar", 1600 title="Multilevel $k$-way partitioning scheme for irregular graphs", 1601 institution="Department of Computer Science, University of Minnesota", 1602 address="Minnesota", 1603 year="1995"} 1604 1605@techreport{kar95-partition, 1606 author="G. Karypis and V. Kumar", 1607 title="Analysis of multilevel graph partitioning", 1608 number="TR 95-037", 1609 institution="Department of Computer Science, University of Minnesota", 1610 address="Minnesota", 1611 year="1995"} 1612 1613@inproceedings{kar95, 1614 author="G. Karypis and V. Kumar", 1615 title="Multilevel graph partition and sparse matrix ordering", 1616 booktitle="Intl. Conf. on Parallel Processing", 1617 year="1995"} 1618 1619@article{lip79, 1620 author="R. J. Lipton and R. E. Tarjan", 1621 title="A separator theorem for planar graphs", 1622 journal="SIAM J. Applied Math", 1623 volume="36", 1624 year="1979", 1625 pages="177-189"} 1626 1627@techreport{mai94-partition, 1628 author="H.S. Maini and K.G. Mehrotra and S. Ranka", 1629 title="Genetic algorithms for graph partitioning and incremental 1630 graph partitioning", 1631 number="Technical report", 1632 institution="Center for Science and Technology, Syracuse University", 1633 address="Synracuse, N.Y.", 1634 year="1994"} 1635 1636@book{aho83, 1637 author="A. V. Aho and J. E. Hopcroft and J. D. Ullman", 1638 title="Data Structures and Algorithms", 1639 publisher="Addison-Wesley", 1640 address="Reading, MA", 1641 year="1983"} 1642 1643@book{ull84-vlsi, 1644 author="J. D. Ullman", 1645 title="Computational Aspects of VLSI", 1646 publisher="Computer Science Press", 1647 address="Rockville, Md", 1648 year="1984"} 1649 1650@book{duf87-book, 1651 author="I. S. Duff and A. M. Erisman and J. K. Reid", 1652 title="Direct Methods for Sparse Matrices", 1653 publisher="Oxford University Press", 1654 address="London", 1655 year="1987"} 1656 1657@book{zzzz99-book, 1658 author="J. A. George and J. W. H. Liu", 1659 title="Computer Solution of Large Sparse Positive Definite Systems", 1660 publisher="Prentice-Hall", 1661 address="Englewood Cliffs, NJ", 1662 year="1981"} 1663 1664 1665@article{arn85, 1666 author="S. Arnborg", 1667 title="Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey", 1668 journal="BIT", 1669 volume="25", 1670 year="1985", 1671 pages="2-23"} 1672 1673@techreport{bar81, 1674 author="E. R. Barnes", 1675 title="An algorithm for partitioning the nodes of a graph", 1676 number="RC8690", 1677 institution="IBM Thomas J. Watson Research Center", 1678 address="Yorktown Heights, New York", 1679 year="1981"} 1680 1681@inproceedings{bar85, 1682 author="E. R. Barnes", 1683 title="Partitioning the nodes of a graph", 1684 booktitle="Graph Theory with Applications to Algorithms and Computer Science", 1685 editor="Y. Alavi and G. Chartrand and D. Lick and C. Wall and L. Lesuiak", 1686 publisher="John Wiley \& Sons Inc.", 1687 address="New York", 1688 year="1985", 1689 pages="57-72"} 1690 1691@article{bha84, 1692 author="S. N. Bhatt and F. T. Leighton", 1693 title="A framework for solving {VLSI} graph layout problems", 1694 journal="Journal of Computer \& Systems Sciences", 1695 volume="28", 1696 year="1984", 1697 pages=""} 1698 1699@inproceedings{bre77, 1700 author="M. A. Breuer", 1701 title="A class of min-cut placement algorithms", 1702 booktitle="Proc. 14th Design Automation Conference", 1703 year="1977", 1704 pages="284-290"} 1705 1706@inproceedings{bui84, 1707 author="S. N. Bui and S. Chaudhuri and T. Leighton and M. Sipser", 1708 title="Graph bisection algorithms with good average case behavior", 1709 booktitle="Proceedings of the 25th Annual Symposium of Foundations of Computer Science", 1710 year="1984", 1711 pages="181-192"} 1712 1713@article{dji81, 1714 author="H. N. Djidjev", 1715 title="A separator theorem", 1716 journal="Comptes rendus de l' Academie bulgare des Sciences", 1717 volume="34", 1718 year="1981", 1719 pages="643-645"} 1720 1721@article{dji82-linear, 1722 author="H. N. Djidjev", 1723 title="A linear algorithm for partitioning graphs", 1724 journal="Comptes rendus de l' Academie bulgare des Sciences", 1725 volume="35", 1726 year="1982", 1727 pages="1053-1056"} 1728 1729@article{dji82-planar, 1730 author="H. N. Djidjev", 1731 title="On the problem of partitioning planar graphs", 1732 journal="SIAM J. Alg. \& Disc. Meth.", 1733 volume="3", 1734 year="1982", 1735 pages="229-240"} 1736 1737@article{don72, 1738 author="W. E. Donath and A. J. Hoffman", 1739 title="Algorithms for partitioning of graphs and computer logic based on eigenvectors of connection matrices", 1740 journal="IBM Technical Disclosure Bulletin", 1741 volume="15", 1742 year="1972", 1743 pages="938-944"} 1744 1745@article{don73, 1746 author="W. E. Donath and A. J. Hoffman", 1747 title="Lower bounds for the partitioning of graphs", 1748 journal="IBM J. Res. Develop.", 1749 volume="17", 1750 year="1973", 1751 pages="420-425"} 1752 1753@article{fie73, 1754 author="M. Fiedler", 1755 title="Algebraic connectivity of graphs", 1756 journal="Czechoslovak Math J.", 1757 volume="23", 1758 year="1973", 1759 pages="298-305"} 1760 1761@book{fre86, 1762 author="G. N. Fredrickson and R. Janardan", 1763 title="Separator-based strategies for efficient message routing", 1764 booktitle="27th Annual Symposium on Foundation of Computer Science", 1765 publisher="IEEE", 1766 year="1986", 1767 pages="428-437"} 1768 1769@book{gaz87, 1770 author="H. Gazit and G. L. Miller", 1771 title="A parallel algorithm for finding a separator in planar graphs", 1772 booktitle="28th Annual Symposium on Foundation of Computer Science", 1773 publisher="IEEE", 1774 year="1987", 1775 pages="238-248"} 1776 1777@techreport{gil80, 1778 author="J. R. Gilbert", 1779 title="Graph separator theorems and sparse {G}aussian elimination", 1780 number="Ph.D. Thesis", 1781 institution="DCS, Stanford University", 1782 year="1980"} 1783 1784@article{gil84-genus, 1785 author="J. R. Gilbert and J. P. Hutchinson and R. E. Tarjan", 1786 title="A separator theorem for graphs of bounded genus", 1787 journal="J. of Algorithms", 1788 volume="5", 1789 year="1984", 1790 pages="391-407"} 1791 1792@article{gil84-chordal, 1793 author="J. R. Gilbert and D. J. Rose and A. Edenbrandt", 1794 title="A separator theorem for chordal graphs", 1795 journal="SIAM J. Alg. \& Disc. Meth.", 1796 volume="5", 1797 year="1984", 1798 pages="306-313"} 1799 1800@inproceedings{gol83, 1801 author="M. K. Goldberg and M. Burstein", 1802 title="Heuristic improvement technique for bisection of {VLSI} networks", 1803 booktitle="Proc. IEEE International Conf. on Computer Design", 1804 address="Port Chester, New York", 1805 year="1983", 1806 pages="122-125"} 1807 1808@techreport{gol87, 1809 author="M. K. Goldberg and S. Lath and J. W. Roberts", 1810 title="Heuristics for the graph bisection problem", 1811 number="Report", 1812 institution="Rensselaer Polytechnic Institute", 1813 year="1987"} 1814 1815@techreport{hen92, 1816 author="B. Hendrickson and R. Leland", 1817 title="An improved spectral graph partitioning algorithm for mapping parallel computations", 1818 number="SAND92-1460", 1819 institution="Sandia National Laboratories", 1820 address="Albuquerque, NM", 1821 year="1992"} 1822 1823@techreport{hen93, 1824 author="B. Hendrickson and R. Leland", 1825 title="Multidimensional spectral load balancing", 1826 number="SAND93-074", 1827 institution="Sandia National Laboratories", 1828 address="Albuquerque, NM", 1829 year="1993"} 1830 1831@article{hu81, 1832 author="T. C. Hu and M. T. Shing", 1833 title="An O(n) algorithm to find a near-optimum partition", 1834 journal="Journal of Algorithms", 1835 volume="2", 1836 year="1981", 1837 pages="122-138"} 1838 1839@article{hu85, 1840 author="T. C. Hu and M. T. Shing", 1841 title="A decomposition algorithm for circuit routing", 1842 journal="Math. Programming Study", 1843 volume="24", 1844 year="1985", 1845 pages="87-103"} 1846 1847@article{hu86, 1848 author="T. C. Hu and M. T. Shing", 1849 title="A decomposition algorithm for multi-terminal network flows", 1850 journal="J. Discrete Applied Math.", 1851 volume="13", 1852 year="1986", 1853 pages="165-181"} 1854 1855@article{joh88, 1856 author="D. S. Johnson and C. R. Aragon and L. A. McGeoch and C. Schevon", 1857 title="Optimization by simulated annealing: an experimental evaluation", 1858 journal="Operations Research", 1859 note="((submitted))", 1860 year="1988"} 1861 1862@article{kan91, 1863 author="A. Kanevsky and V. Ramachandran", 1864 title="Improved algorithms for graph four-connectivity", 1865 journal="J. of Computer Science and Systems", 1866 volume="42", 1867 year="1991", 1868 pages="288-306"} 1869 1870@article{kan9x, 1871 author="A. Kanevsky", 1872 title="Finding all minimum size vertex sets in a graph", 1873 journal="J. of Networks", 1874 year="199x"} 1875 1876@inproceedings{kan90, 1877 author="A. Kanevsky", 1878 title="On the number of minimum size separating vertex sets of a graph and how to find all of them", 1879 booktitle="First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '90)", 1880 year="January 22-24,1990", 1881 pages="411-421"} 1882 1883@article{kao90, 1884 author="M. Kao and F. Wan", 1885 title="Not all planar digraphs have small cycle separators", 1886 journal="Information Processing Letters", 1887 year="1990"} 1888 1889@article{ker70, 1890 author="B. W. Kernighan and S. Lin", 1891 title="An efficient heuristic procedure for partitioning graphs", 1892 journal="Bell System Technical Journal", 1893 volume="49", 1894 year="1970", 1895 pages="291-307"} 1896 1897@article{kir83, 1898 author="S. Kirkpatrick and C. D. Gelatt Jr. and M. P. Vecchi", 1899 title="Optimization by simulated annealing", 1900 journal="Science", 1901 volume="220", 1902 year="1983", 1903 pages="671-680"} 1904 1905@article{kom85, 1906 author="J. Komlos and M. T. Shing", 1907 title="Probabilistic partitioning algorithms for the rectilinear Steiner problem", 1908 journal="Networks", 1909 volume="15", 1910 year="1985", 1911 pages="413-423"} 1912 1913@article{kri84, 1914 author="B. Krishnamurthy", 1915 title="An improved min-cut algorithm for partitioning {VLSI} networks", 1916 journal="IEEE Trans. on Computers", 1917 volume="C-33", 1918 year="1984", 1919 pages="438-446"} 1920 1921@article{kri87, 1922 author="B. Krishnamurthy", 1923 title="Constructing test cases for partitioning heuristics", 1924 journal="IEEE Trans. on Computers", 1925 volume="C-36", 1926 year="198", 1927 pages="1112-1114"} 1928 1929@inproceedings{lei82, 1930 author="F. T. Leighton", 1931 title="A layout strategy for {VLSI} which is provably good", 1932 booktitle="Proceedings of the 14th Annual ACM Symposium on Theory of Computing", 1933 year="1982", 1934 pages="85-98"} 1935 1936@book{lei80, 1937 author="C. Leiserson", 1938 title="Area-efficient graph layout (for vlsi)", 1939 booktitle="21st Annual Symposium on Foundation of Computer Science", 1940 publisher="IEEE", 1941 year="1980", 1942 pages="270-281"} 1943 1944@article{lin77, 1945 author="T. D. Lin and R. S. H. Mah", 1946 title="Hierarchical partition -- a new optimal pivoting algorithm", 1947 journal="Math. Programming", 1948 volume="12", 1949 year="1977", 1950 pages="260-278"} 1951 1952@article{lip80, 1953 author="R. J. Lipton and R. E. Tarjan", 1954 title="Applications of a planar separator theorem", 1955 journal="SICOMP", 1956 volume="9", 1957 year="1980", 1958 pages="615-627"} 1959 1960@techreport{mac78, 1961 author="R. M. Macgregor", 1962 title="On partitioning a graph: a theoretical and empirical study", 1963 number="UCB/ERL M78/14 (Ph.D. Thesis)", 1964 institution="Standford University", 1965 year="1978"} 1966 1967@inproceedings{mil84, 1968 author="G. L. Miller", 1969 title="Finding small simple cycle separators for 2-connected planar graphs", 1970 booktitle="Proceedings of the 16th Annual ACM Symposium on Theory of Computing", 1971 year="1984", 1972 pages="376-382"} 1973 1974@techreport{moo88, 1975 author="D. Moore", 1976 title="A round-robin parallel partitioning algorithm", 1977 number="TR 88-916", 1978 institution="DCS, Cornell University", 1979 year="1988"} 1980 1981@article{pai87, 1982 author="R. Paige and R. E. Tarjan", 1983 title="Three partition refinement algorithm", 1984 journal="SICOMP", 1985 volume="16", 1986 year="1987", 1987 pages="973-989"} 1988 1989@article{pow88, 1990 author="D. Powers", 1991 title="Graph partitioning by eigenvectors", 1992 journal="Lin. Alg. Appl.", 1993 volume="101", 1994 year="1988", 1995 pages="121-133"} 1996 1997@book{rao87, 1998 author="S. Rao", 1999 title="Finding near optimal separators in planar graphs", 2000 booktitle="28th Annual Symposium on Foundation of Computer Science", 2001 publisher="IEEE", 2002 year="1987", 2003 pages="225-237"} 2004 2005@article{rav87, 2006 author="S. Ravi and H. Hunt III", 2007 title="An application of the planar separator theorem to counting problem", 2008 journal="Inform. Process. Letters", 2009 volume="25", 2010 year="1987", 2011 pages="317-322"} 2012 2013@techreport{ren90, 2014 author="F. Rendl and H. Wolkowicz", 2015 title="A projection technique for partitioning the nodes of a graph", 2016 number="CORR 90-20", 2017 institution="University of Waterloo", 2018 address="Waterloo, Ontario", 2019 year="1990"} 2020 2021@inproceedings{san76, 2022 author="A. Sangiovanni-Vincentelli", 2023 title="An optimization problem arising from tearing methods", 2024 booktitle="Sparse Matrix Computations", 2025 editor="J.R. Bunch and D.J. Rose", 2026 publisher="Academic Press", 2027 year="1976", 2028 pages="97-110"} 2029 2030@inproceedings{sch79, 2031 author="D. G. Schweikert and B. W. Kernighan", 2032 title="A proper model for the partitioning of electrical circuits", 2033 booktitle="Proc. 9th Design Automation Workshop", 2034 year="1979", 2035 pages="57-62"} 2036 2037@article{sen92, 2038 author="A. Sen and H. Deng and S. Guha", 2039 title="On a graph partition problem with application to vlsi layout", 2040 journal="Information Processing Letters", 2041 year="1992", 2042 volume="43", 2043 pages="87-94"} 2044 2045@techreport{she87, 2046 author="T. J. Sheffler", 2047 title="A graph separator theorem and its application to {G}aussian elimination to optimize {B}oolean expression for parallel evaluation", 2048 number="CMU-CS-87-123", 2049 institution="DCS, Carnegie-Mellon University", 2050 year="1987"} 2051 2052@inproceedings{shi80, 2053 author="H. Shiraishi and F. Hirose", 2054 title="Efficient placement and routing for masterslice {LSI}", 2055 booktitle="Proc. 17th Design Automation Conference", 2056 year="1980", 2057 pages="458-464"} 2058 2059@article{sua88, 2060 author="P. Suaris and G. Kedem", 2061 title="An algorithm for quadrisection and its application to standard cell placement", 2062 journal="IEEE Trans. Circuits and Systems", 2063 volume="35", 2064 year="1988", 2065 pages="294-303"} 2066 2067@article{tar??, 2068 author="R. E. Tarjan", 2069 title="Decomposition by clique separators", 2070 journal="Discrete Math", 2071 year="to appear"} 2072 2073@article{ven87, 2074 author="S. Venkatesan", 2075 title="Improved constants for some separator theorems", 2076 journal="J. Algorithms", 2077 volume="8", 2078 year="1987", 2079 pages="572-578"} 2080 2081@article{wan91, 2082 author="F. Wan", 2083 title="A linear-processor algorithm for finding small cycle separators on undirected planar graphs", 2084 journal="SICOMP", 2085 year="1991?"} 2086 2087@article{whi81, 2088 author="S. H. Whitesides", 2089 title="An algorithm for finding clique cutsets", 2090 journal="Inf. Proc. Letters", 2091 volume="12", 2092 year="1981", 2093 pages="31-32"} 2094 2095@incollection{matrixmarket97, 2096 author="R. F. Boisvert and R. Pozo and K. Remington 2097 and R. F. Barrett and J. J. Dongarra", 2098 title="Matrix {M}arket: a web resource for test matrix collections", 2099 booktitle="The Quality of Numerical Software: 2100 Assessment and Enhancement", 2101 publisher="Chapman and Hall, London", 2102 year="1997", 2103 editor="R. F. Boisvert", 2104 pages="125-137"} 2105