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