A Collection of Reference Material on Matching

 

 

@BOOK{lovasz1,

 author = {L. Lovasz},

 title = {Matching Theory (North-Holland mathematics studies)},

 year = {1986},

 isbn = {0444879161},

 publisher = {Elsevier Science Ltd},

 }

 

@BOOK{penrose1,

 author = {Mathew Penrose},

 title = {Random Geometric Graphs},

 year = {2003},

 isbn = {0198506260},

 publisher = {Oxford University Press},

 }

 

@BOOK{lawler1,

 author = {Eugene Lawler},

 title = {Combinatorial Optimization: Networks and Matroids},

 year = {1976},

 publisher = {Dover Publications},

 address = {Mineola, New York},

 }

 

@INBOOK{ahuja2,

  author = {M.O. Ball and T.L. Magnanti and C.L. Monma and G.L. Nemhauser},

  chapter = {Applications of Network Optimization},

  title = {Network Models, Handbooks in Operations Research and Management Science},

  publisher = {North Holland Press},

  volume = {7},

  year = {1995},

  address = {Amsterdam},

 }

 

@INBOOK{gerards1,

  author = {M.O. Ball and T.L. Magnanti and C.L. Monma and G.L. Nemhauser},

  chapter = {Matching},

  title = {Network Models, Handbooks in Operations Research and Management Science},

  publisher = {North Holland Press},

  volume = {7},

  pages = {135--224},

  year = {1995},

  address = {Amsterdam},

}

 

@BOOK{schrijver1,

author = {Alexander Schrijver},

title = {Combinatorial Optimization - Polyhedra and Efficiency},

publisher = {Springer},

year = {2003},

}

 

@BOOK{cormen1,

 title = {Introduction to Algorithms},

 author = {Thomas H. Cormen and Charles E. Leiserson and Ronald L. Rivest and Clifford Stein},

 edition = {2nd},

 publisher = {The MIT Press},

 year = {2001},

}

 

@BOOK{wolsey1,

 author = {L.~Wolsey},

 title = {Integer Programming},

 publisher = {Wiley-Interscience Publication, John Wiley and Sons},

 year = {1998},

}

 

@BOOK{vazirani1,

 author = {Vijay V. Vazirani},

 title = {Approximation Algorithms},

 publisher = {Springer},

 year = {2003},

}

 

@BOOK{hochbaum1,

 editor = {Dorit S. Hochbaum},

 title = {Approximation algorithms for NP-hard problems},

 year = {1997},

 isbn = {0-534-94968-1},

 publisher = {PWS Publishing Co.},

 address = {Boston, MA, USA},

 }

 

@BOOK{papadimitriou1,

 author = {Christos H. Papadimitriou and Kenneth Steiglitz},

 title = {Combinatorial optimization: algorithms and complexity},

 year = {1982},

 isbn = {0-13-152462-3},

 publisher = {Prentice-Hall, Inc.},

 address = {Upper Saddle River, NJ, USA},

 }

 

@BOOK{auden1,

 author = {W. H. Auden and Louis Kronenberger},

 title = {The Viking Book of Aphorisms, A Personal Selection},

 year = {1981},

 publisher = {Dorset Press},

}

 

@BOOK{ahuja1,

 author = {Ahuja, Ravindra  K.  and Magnanti, Thomas  L.  and Orlin, James  B. },

 title = {Network Flows: Theory, Algorithms, and Applications},

 publisher = {Prentice Hall},

 year = {1993}

}

 

@BOOK{aho1,

 author = {Alfred V. Aho and John E. Hopcroft},

 title = {The  Design and Analysis of Computer Algorithms},

 year = {1974},

 isbn = {0201000296},

 publisher = {Addison-Wesley Longman Publishing Co., Inc.},

 address = {Boston, MA, USA},

}

 

@book{karpinski1,

 author = {Marek Karpinski and Wojciech Rytter},

 title = {Fast parallel algorithms for graph matching problems},

 year = {1998},

 isbn = {0-19-850162-5},

 publisher = {Oxford University Press, Inc.},

 address = {New York, NY, USA},

}

 

@book{grama1,

 author = {Vipin Kumar and Ananth Grama and Anshul Gupta and George Karypis},

 title = {Introduction to parallel computing: design and analysis of algorithms},

 year = {1994},

 isbn = {0-8053-3170-0},

 publisher = {Benjamin-Cummings Publishing Co., Inc.},

 address = {Redwood City, CA, USA},

}

 

@book{bisseling1,

 author = {Rob H. Bisseling},

 title = {Parallel Scientific Computation: A Structured Approach Using BSP and MPI},

 year = {2004},

 isbn = {0198529392},

 publisher = {Oxford University Press},

}

 

@book{snir1,

 author = {Marc Snir and Steve Otto},

 title = {MPI-The Complete Reference: The MPI Core},

 year = {1998},

 isbn = {0262692155},

 publisher = {MIT Press},

 address = {Cambridge, MA, USA},

 }

 

@book{bader1,

 author = {Davis A. Bader},

 title = {Petascale Computing: Algorithms and Applications},

 year = {2007},

 isbn = {1-58488-909-8},

 publisher = {Chapman and Hall/CRC},

 address = {New York, NY, USA},

 }

 

 

@article{kuhn1,

 author = {Kuhn, H. W. },

 title = {The {H}ungarian method for the assignment problem},

 journal = {Naval Research Logistic Quarterly},

 pages = {83--97},

 volume = {2},

 year = {1955},

}

 

@ARTICLE{galil1,

 author = {Zvi Galil},

 title = {Efficient algorithms for finding maximum matching in graphs},

 journal = {ACM Comput. Surv.},

 volume = {18},

 number = {1},

 year = {1986},

 issn = {0360-0300},

 pages = {23--38},

 doi = {http://doi.acm.org/10.1145/6462.6502},

 publisher = {ACM},

 address = {New York, NY, USA},

 }

 

@ARTICLE{hopcroft1,

 author = {J.E. Hopcroft and R.M. Karp},

 title = {A $n^{\frac{5}{2}}$ algorithm for maximum matchings in bipartite graphs},

 journal = {SIAM J. Comput.},

 volume = {2},

 year = {1973},

 pages = {225--231},

 publisher = {Society for Industrial and Applied Mathematics},

 address = {Philadelphia, PA, USA},

 }

 

@ARTICLE{gabow1,

 author = {Harold N. Gabow},

 title = {An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs},

 journal = {J. ACM},

 volume = {23},

 number = {2},

 year = {1976},

 issn = {0004-5411},

 pages = {221--234},

 doi = {http://doi.acm.org/10.1145/321941.321942},

 publisher = {ACM},

 address = {New York, NY, USA},

 }

 

@ARTICLE{galil2,

 author = {Zvi Galil and Silvio Micali and Harold Gabow},

 title = {An $O(EV \log V)$ algorithm for finding a maximal weighted matching in general graphs},

 journal = {SIAM J. Comput.},

 volume = {15},

 number = {1},

 year = {1986},

 issn = {0097-5397},

 pages = {120--130},

 doi = {http://dx.doi.org/10.1137/0215009},

 publisher = {Society for Industrial and Applied Mathematics},

 address = {Philadelphia, PA, USA},

 }

 

@ARTICLE{gabow2,

 author = {H. N. Gabow and R. E. Tarjan},

 title = {Faster scaling algorithms for network problems},

 journal = {SIAM J. Comput.},

 volume = {18},

 number = {5},

 year = {1989},

 issn = {0097-5397},

 pages = {1013--1036},

 doi = {http://dx.doi.org/10.1137/0218069},

 publisher = {Society for Industrial and Applied Mathematics},

 address = {Philadelphia, PA, USA},

 }

 

@techreport{vazirani5,

 author = {Vijay V. Vazirani},

 title = {A Theory of Alternating Paths and Blossoms for Proving Correctness of the $O(\sqrt{V}E)$ General Graph Matching Algorithm},

 year = {1989},

 source = {http://www.ncstrl.org:8900/ncstrl/servlet/search?formname=detail\&id=oai%3Ancstrlh%3Acornellcs%3ACORNELLCS%3ATR89-1035},

 publisher = {Cornell University},

 address = {Ithaca, NY, USA},

 }

 

@inproceedings{mehlhorn2,

 author = {Kurt Mehlhorn and Guido Sch\"{a}fer},

 title = {A Heuristic for Dijkstra's Algorithm with Many Targets and Its Use in Weighted Matching Algorithms},

 booktitle = {ESA '01: Proceedings of the 9th Annual European Symposium on Algorithms},

 year = {2001},

 isbn = {3-540-42493-8},

 pages = {242--253},

 publisher = {Springer-Verlag},

 address = {London, UK},

 }

 

@ARTICLE{cook1,

 author = {William Cook and Andre Rohe},

 title = {Computing Minimum-Weight Perfect Matchings},

 journal = {INFORMS J. on Computing},

 volume = {11},

 number = {2},

 year = {1999},

 issn = {1526-5528},

 pages = {138--148},

 publisher = {INFORMS},

 address = {Institute for Operations Research and the Management Sciences (INFORMS), Linthicum, Maryland, USA},

 }

 

@ARTICLE{motwani1,

 author = {Rajeev Motwani},

 title = {Average-case analysis of algorithms for matchings and related problems},

 journal = {J. ACM},

 volume = {41},

 number = {6},

 year = {1994},

 issn = {0004-5411},

 pages = {1329--1356},

 doi = {http://doi.acm.org/10.1145/195613.195663},

 publisher = {ACM},

 address = {New York, NY, USA},

 }

 

@ARTICLE{hanafi1,

 author = {Sa\"{\i}d Hanafi},

 title = {On the Convergence of Tabu Search},

 journal = {Journal of Heuristics},

 volume = {7},

 number = {1},

 year = {2001},

 issn = {1381-1231},

 pages = {47--58},

 doi = {http://dx.doi.org/10.1023/A:1026565712483},

 publisher = {Kluwer Academic Publishers},

 address = {Hingham, MA, USA},

 }

 

@ARTICLE{mehlhorn1,

 author = {Kurt Mehlhorn and Guido Sch\"{a}fer},

 title = {Implementation of $O(nm\log n)$ weighted matchings in general graphs: the power of data structures},

 journal = {J. Exp. Algorithmics},

 volume = {7},

 year = {2002},

 issn = {1084-6654},

 pages = {4},

 doi = {http://doi.acm.org/10.1145/944618.944622},

 publisher = {ACM},

 address = {New York, NY, USA},

 }

 

@ARTICLE{derigs1,

 author = {U. Derigs and A. Metz},

 title = {Solving (large scale) matching problems combinatorially},

 journal = {Math. Program.},

 volume = {50},

 number = {1},

 year = {1991},

 issn = {0025-5610},

 pages = {113--121},

 doi = {http://dx.doi.org/10.1007/BF01594929},

 publisher = {Springer-Verlag New York, Inc.},

 address = {Secaucus, NJ, USA},

 }

 

@inproceedings{vaidya1,

 author = {Pravin Vaidya},

 title = {Geometry helps in matching},

 booktitle = {STOC '88: Proceedings of the twentieth annual ACM symposium on Theory of computing},

 year = {1988},

 isbn = {0-89791-264-0},

 pages = {422--425},

 location = {Chicago, Illinois, United States},

 doi = {http://doi.acm.org/10.1145/62212.62253},

 publisher = {ACM},

 address = {New York, NY, USA},

 }

 

 

@inproceedings{spencer1,

 author = {Thomas H. Spencer and Ernst W. Mayr},

 title = {Node Weighted Matching},

 booktitle = {Proceedings of the 11th Colloquium on Automata, Languages and Programming},

 year = {1984},

 isbn = {3-540-13345-3},

 pages = {454--464},

 publisher = {Springer-Verlag},

 address = {London, UK},

 }

 

@inproceedings{mulmuley1,

 author = {Ketan Mulmuley and Umesh V. Vazirani and Vijay V. Vazirani},

 title = {Matching is as easy as matrix inversion},

 booktitle = {STOC '87: Proceedings of the nineteenth annual ACM conference on Theory of computing},

 year = {1987},

 isbn = {0-89791-221-7},

 pages = {345--354},

 location = {New York, New York, United States},

 doi = {http://doi.acm.org/10.1145/28395.383347},

 publisher = {ACM},

 address = {New York, NY, USA},

 }

 

@inproceedings{vazirani1,

 author = {U Vazirani and V V Vazirani},

 title = {The two-processor scheduling problem is in $R-NC$},

 booktitle = {STOC '85: Proceedings of the seventeenth annual ACM symposium on Theory of computing},

 year = {1985},

 isbn = {0-89791-151-2},

 pages = {11--21},

 location = {Providence, Rhode Island, United States},

 doi = {http://doi.acm.org/10.1145/22145.22147},

 publisher = {ACM},

 address = {New York, NY, USA},

 }

 

@ARTICLE{campelo1,

 author = {Manoel B. Camp\^{e}lo and Sulamita Klein},

 title = {Maximum vertex-weighted matching in strongly chordal graphs},

 journal = {Discrete Appl. Math.},

 volume = {84},

 number = {1-3},

 year = {1998},

 issn = {0166-218X},

 pages = {71--77},

 doi = {http://dx.doi.org/10.1016/S0166-218X(97)00136-4},

 publisher = {Elsevier Science Publishers B. V.},

 address = {Amsterdam, The Netherlands, The Netherlands},

 }

 

@ARTICLE{bell1,

 AUTHOR={Bell, Colin E.},

 TITLE={Weighted matching with vertex weights: An application to scheduling training sessions in NASA space shuttle cockpit simulators},

 JOURNAL={European Journal of Operational Research},

 YEAR={1994},

 VOLUME={73},

 NUMBER={3},

 PAGES={443-449},

 MONTH={March},

 NOTE={available at http://ideas.repec.org/a/eee/ejores/v73y1994i3p443-449.html}

}

 

@article{tabatabaee1,

 author = {Vahid Tabatabaee and Leonidas Georgiadis and Leandros Tassiulas},

 title = {QoS provisioning and tracking fluid policies in input queueing switches},

 journal = {IEEE/ACM Trans. Netw.},

 volume = {9},

 number = {5},

 year = {2001},

 issn = {1063-6692},

 pages = {605--617},

 doi = {http://dx.doi.org/10.1109/90.958329},

 publisher = {IEEE Press},

 address = {Piscataway, NJ, USA},

}

 

@ARTICLE{tabatabaee2,

 title={MNCM a new class of efficient scheduling algorithms for input-buffered switches with no speedup},

 author={Tabatabaee, V. and Tassiulas, L.},

 journal={INFOCOM 2003. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications Societies. IEEE},

 year={2003},

 month={March-3 April},

 volume={2},

 number={},

 pages={ 1406-1413 vol.2},

 doi={10.1109/INFCOM.2003.1208976},

 ISSN={0743-166X },

}

 

 

@article{avis1,

 author = {D Avis},

 title = {A survey of heuristics for the weighted matching problem},

 journal = {Network},

 volume = {13},

 year = {1983},

 pages = {475-493},

}

 

@article{monien1,

 author = {Burkhard Monien and Robert Preis and Ralph Diekmann},

 title = {Quality matching and local improvement for multilevel graph-partitioning},

 journal = {Parallel Comput.},

 volume = {26},

 number = {12},

 year = {2000},

 issn = {0167-8191},

 pages = {1609--1634},

 doi = {http://dx.doi.org/10.1016/S0167-8191(00)00049-1},

 publisher = {Elsevier Science Publishers B. V.},

 address = {Amsterdam, The Netherlands, The Netherlands},

 }

 

@ARTICLE{drake1,

 author = {Doratha E. Drake and Stefan Hougardy},

 title = {A simple approximation algorithm for the weighted matching problem},

 journal = {Inf. Process. Lett.},

 volume = {85},

 number = {4},

 year = {2003},

 issn = {0020-0190},

 pages = {211--213},

 doi = {http://dx.doi.org/10.1016/S0020-0190(02)00393-9},

 publisher = {Elsevier North-Holland, Inc.},

 address = {Amsterdam, The Netherlands, The Netherlands},

 }

 

@ARTICLE{drake2,

 author = {Doratha E. Drake Vinkemeier and Stefan Hougardy},

 title = {A linear-time approximation algorithm for weighted matchings in graphs},

 journal = {ACM Trans. Algorithms},

 volume = {1},

 number = {1},

 year = {2005},

 issn = {1549-6325},

 pages = {107--122},

 doi = {http://doi.acm.org/10.1145/1077464.1077472},

 publisher = {ACM},

 address = {New York, NY, USA},

 }

 

@ARTICLE{pettie1,

 author = {Seth Pettie and Peter Sanders},

 title = {A simpler linear time $\frac{2}{3} - \epsilon$ approximation for maximum weight matching},

 journal = {Inf. Process. Lett.},

 volume = {91},

 number = {6},

 year = {2004},

 issn = {0020-0190},

 pages = {271--276},

 doi = {http://dx.doi.org/10.1016/j.ipl.2004.05.007},

 publisher = {Elsevier North-Holland, Inc.},

 address = {Amsterdam, The Netherlands, The Netherlands},

 }

 

@ARTICLE{fekete1,

 author = {S\'{a}ndor P. Fekete and Henk Meijer and Andr\'{e} Rohe and Walter Tietze},

 title = {Solving a "Hard" problem to approximate an "Easy" one: heuristics for maximum matchings and maximum traveling salesman problems},

 journal = {J. Exp. Algorithmics},

 volume = {7},

 year = {2002},

 issn = {1084-6654},

 pages = {11},

 doi = {http://doi.acm.org/10.1145/944618.944629},

 publisher = {ACM},

 address = {New York, NY, USA},

 }

 

@ARTICLE{feigenbaum1,

 author = {Joan Feigenbaum and Sampath Kannan and Andrew McGregor and Siddharth Suri and Jian Zhang},

 title = {On graph problems in a semi-streaming model},

 journal = {Theor. Comput. Sci.},

 volume = {348},

 number = {2},

 year = {2005},

 issn = {0304-3975},

 pages = {207--216},

 doi = {http://dx.doi.org/10.1016/j.tcs.2005.09.013},

 publisher = {Elsevier Science Publishers Ltd.},

 address = {Essex, UK},

 }

 

@MISC{zelke1,

 author = {M. Zelke},

 title = {Weighted Matching in the Semi-Streaming Model},

 text = {(PrePrint)},

}

 

@article{bertsekas1,

 author = {Dimitri P. Bertsekas and David A. Casta\,{n}on},

 title = {A generic auction algorithm for the minimum cost network flow problem},

 journal = {Comput. Optim. Appl.},

 volume = {2},

 number = {3},

 year = {1993},

 issn = {0926-6003},

 pages = {229--260},

 doi = {http://dx.doi.org/10.1007/BF01299450},

 publisher = {Kluwer Academic Publishers},

 address = {Norwell, MA, USA},

 }

 

 

@inproceedings{luby1,

 author = {M Luby},

 title = {A simple parallel algorithm for the maximal independent set problem},

 booktitle = {STOC '85: Proceedings of the seventeenth annual ACM symposium on Theory of computing},

 year = {1985},

 isbn = {0-89791-151-2},

 pages = {1--10},

 location = {Providence, Rhode Island, United States},

 doi = {http://doi.acm.org/10.1145/22145.22146},

 publisher = {ACM},

 address = {New York, NY, USA},

 }

 

@article{han1,

 author = {Yijie Han},

 title = {An improvement on parallel computation of a maximal matching},

 journal = {Inf. Process. Lett.},

 volume = {56},

 number = {6},

 year = {1995},

 issn = {0020-0190},

 pages = {343--348},

 doi = {http://dx.doi.org/10.1016/0020-0190(95)00166-2},

 publisher = {Elsevier North-Holland, Inc.},

 address = {Amsterdam, The Netherlands, The Netherlands},

 }

 

@article{batagelj1,

    author = {Vladimir Batagelj and Andrej Mrvar},

    title = {Pajek - Program for Large Network Analysis},

    journal = {Connections},

    year = {1998},

    volume = {21},

    pages = {47--57}

}

 

@article{karypis1,

 author = {George Karypis and Vipin Kumar},

 title = {A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs},

 journal = {SIAM J. Sci. Comput.},

 volume = {20},

 number = {1},

 year = {1998},

 issn = {1064-8275},

 pages = {359--392},

 doi = {http://dx.doi.org/10.1137/S1064827595287997},

 publisher = {Society for Industrial and Applied Mathematics},

 address = {Philadelphia, PA, USA},

 }

 

@inproceedings{preis1,

 author = {Robert Preis},

 title = {Linear time $\frac{1}{2}$-approximation algorithm for maximum weighted matching in general graphs},

 booktitle = {16th Ann. Symp. on Theoretical Aspects of Computer Science (STACS)},

 year = {1999},

 pages = {259--269},

 }

 

@inproceedings{manne1,

 author = {Fredrik Manne and Rob H. Bisseling},

 title = {A Parallel Approximation Algorithm for the Weighted Maximum Matching Problem},

 booktitle = {The Seventh International Conference on Parallel Processing and Applied Mathematics},

 year = {2007},

 pages = {708--717},

}

 

@article{hoepman1,

  author    = {Jaap-Henk Hoepman},

  title     = {Simple Distributed Weighted Matchings},

  journal   = {CoRR},

  volume    = {cs.DC/0410047},

  year      = {2004},

  ee        = {http://arxiv.org/abs/cs.DC/0410047},

  bibsource = {DBLP, http://dblp.uni-trier.de}

}

 

@inproceedings{diaz1,

 author = {Josep D\'{\i}az and Dieter Mitsche and Xavier P\'{e}rez-Gim\'{e}nez},

 title = {On the connectivity of dynamic random geometric graphs},

 booktitle = {SODA '08: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms},

 year = {2008},

 pages = {601--610},

 location = {San Francisco, California},

 publisher = {Society for Industrial and Applied Mathematics},

 address = {Philadelphia, PA, USA},

 }

 

@article{diaz2,

 author = {Joseph D\'{\i}az and Mathew D. Penrose and Jordi Petit and Mar\'{\i}a Serna},

 title = {Approximating layout problems on random geometric graphs},

 journal = {J. Algorithms},

 volume = {39},

 number = {1},

 year = {2001},

 issn = {0196-6774},

 pages = {78--116},

 doi = {http://dx.doi.org/10.1006/jagm.2000.1149},

 publisher = {Academic Press, Inc.},

 address = {Duluth, MN, USA},

 }

 

@article{diaz3,

 author = {Josep D\'{\i}az and Mathew D. Penrose and Jordi Petit and Mar\'{\i}a Serna},

 title = {Convergence Theorems for Some Layout Measures on Random Lattice and Random Geometric Graphs},

 journal = {Comb. Probab. Comput.},

 volume = {9},

 number = {6},

 year = {2000},

 issn = {0963-5483},

 pages = {489--511},

 doi = {http://dx.doi.org/10.1017/S0963548300004454},

 publisher = {Cambridge University Press},

 address = {New York, NY, USA},

 }

 

@inproceedings{goel1,

 author = {Ashish Goel and Sanatan Rai and Bhaskar Krishnamachari},

 title = {Sharp thresholds For monotone properties in random geometric graphs},

 booktitle = {STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing},

 year = {2004},

 isbn = {1-58113-852-0},

 pages = {580--586},

 location = {Chicago, IL, USA},

 doi = {http://doi.acm.org/10.1145/1007352.1007441},

 publisher = {ACM},

 address = {New York, NY, USA},

}

 

@inproceedings{bader3,

 author = {D.A. Bader and K. Madduri},

 title = {Design and implementation of the HPCS graph analysis benchmark on symmetric multiprocessors},

 booktitle = {Lecture Notes in Computer Science},

 pages = {465-476},

 volume = {3769},

 year = {2005}

}

 

@article{uehara1,

 author = {Ryuhei Uehara and Zhi-Zhong Chen},

 title = {Parallel approximation algorithms for maximum weighted matching in general graphs},

 journal = {Inf. Process. Lett.},

 volume = {76},

 number = {1-2},

 year = {2000},

 issn = {0020-0190},

 pages = {13--17},

 doi = {http://dx.doi.org/10.1016/S0020-0190(00)00128-9},

 publisher = {Elsevier North-Holland, Inc.},

 address = {Amsterdam, The Netherlands, The Netherlands},

 }

 

@article{chan1,

 author = {Albert Chan and Frank Dehne and Prosenjit Bose and Markus Latzel},

 title = {Coarse grained parallel algorithms for graph matching},

 journal = {Parallel Comput.},

 volume = {34},

 number = {1},

 year = {2008},

 issn = {0167-8191},

 pages = {47--62},

 doi = {http://dx.doi.org/10.1016/j.parco.2007.11.004},

 publisher = {Elsevier Science Publishers B. V.},

 address = {Amsterdam, The Netherlands, The Netherlands},

 }

 

@techreport{kao1,

 author = {Ming Kao and Marek Karpinski and Andrzej Lingas},

 title = {Nearly Optimal Parallel Algorithm for Maximum Matching in Planar Graphs},

 year = {1990},

 publisher = {University of Bonn},

}

 

@inproceedings{valiant1,

 author = {T. Cheatham and A. Fahmy and D. C. Stefanescu and L. G. Valiant},

 title = {Bulk synchronous parallel computing-a paradigm for transportable software},

 booktitle = {HICSS '95: Proceedings of the 28th Hawaii International Conference on System Sciences (HICSS'95)},

 year = {1995},

 isbn = {0-8186-6935-7},

 pages = {268},

 publisher = {IEEE Computer Society},

 address = {Washington, DC, USA},

 }

 

@inproceedings{dehne1,

 author = {Frank Dehne and Andreas Fabri and Andrew Rau-Chaplin},

 title = {Scalable parallel geometric algorithms for coarse grained multicomputers},

 booktitle = {SCG '93: Proceedings of the ninth annual symposium on Computational geometry},

 year = {1993},

 isbn = {0-89791-582-8},

 pages = {298--307},

 location = {San Diego, California, United States},

 doi = {http://doi.acm.org/10.1145/160985.161154},

 publisher = {ACM},

 address = {New York, NY, USA},

 }

 

@inproceedings{lotker1,

 author = {Zvi Lotker and Boaz Patt-Shamir and Adi Rosen},

 title = {Distributed approximate matching},

 booktitle = {PODC '07: Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing},

 year = {2007},

 isbn = {978-1-59593-616-5},

 pages = {167--174},

 location = {Portland, Oregon, USA},

 doi = {http://doi.acm.org/10.1145/1281100.1281126},

 publisher = {ACM},

 address = {New York, NY, USA},

 }

 

@article{fischer1,

 author = {Ted Fischer and Andrew V. Goldberg and David J. Haglin and Serge Plotkin},

 title = {Approximating matchings in parallel},

 journal = {Inf. Process. Lett.},

 volume = {46},

 number = {3},

 year = {1993},

 issn = {0020-0190},

 pages = {115--118},

 doi = {http://dx.doi.org/10.1016/0020-0190(93)90055-E},

 publisher = {Elsevier North-Holland, Inc.},

 address = {Amsterdam, The Netherlands, The Netherlands},

 }

 

@ARTICLE{spencer2,

title={Parallel approximate matching},

author={Spencer, T.H.},

journal={System Sciences, 1993, Proceeding of the Twenty-Sixth Hawaii International Conference on},

year={1993},

month={Jan},

volume={ii},

pages={293-297 vol.2},

}

 

@article{hougardyp,

 author = {Stefan Hougardy and Doratha E. Vinkemeier},

 title = {Approximating weighted matchings in parallel},

 journal = {Inf. Process. Lett.},

 volume = {99},

 number = {3},

 year = {2006},

 issn = {0020-0190},

 pages = {119--123},

 doi = {http://dx.doi.org/10.1016/j.ipl.2006.03.005},

 publisher = {Elsevier North-Holland, Inc.},

 address = {Amsterdam, The Netherlands, The Netherlands},

 }

 

@article{zaki1,

 author = {Omer Zaki and Ewing Lusk and William Gropp and Deborah Swider},

 title = {Toward Scalable Performance Visualization with Jumpshot},

 journal = {Int. J. High Perform. Comput. Appl.},

 volume = {13},

 number = {3},

 year = {1999},

 issn = {1094-3420},

 pages = {277--288},

 doi = {http://dx.doi.org/10.1177/109434209901300310},

 publisher = {Sage Publications, Inc.},

 address = {Thousand Oaks, CA, USA},

 }

 

@article{storoy1,

 author = {S. Storoy and T. Sorevik},

 title = {Massively parallel augmenting path algorithms for the assignment problem},

 journal = {Computing},

 volume = {59},

 number = {1},

 year = {1997},

 issn = {0010-485X},

 pages = {1--16},

 doi = {http://dx.doi.org/10.1007/BF02684400},

 publisher = {Springer-Verlag New York, Inc.},

 address = {New York, NY, USA},

 }

 

@ARTICLE{zenios1,

title={Massively parallel auction algorithms for the assignment problem },

author={Wein, J.M. and Zenios, S.},

journal={Frontiers of Massively Parallel Computation, 1990. Proceedings., 3rd Symposium on the},

year={1990},

month={Oct},

volume={},

number={},

pages={90-99},

doi={10.1109/FMPC.1990.89444},

}

 

@article{bertsekasp1,

 author = {Dimitri P. Bertsekas and David A. Casta\,{n}on},

 title = {Parallel primal-dual methods for the minimum cost flow problem},

 journal = {Comput. Optim. Appl.},

 volume = {2},

 number = {4},

 year = {1993},

 issn = {0926-6003},

 pages = {317--336},

 doi = {http://dx.doi.org/10.1007/BF01299544},

 publisher = {Kluwer Academic Publishers},

 address = {Norwell, MA, USA},

}

 

@article{bertsekasp2,

  author    = {Dimitri P. Bertsekas and David A. Casta{\~n}on},

  title     = {Parallel synchronous and asynchronous implementations of the auction algorithm},

  journal   = {Parallel Computing},

  volume    = {17},

  number    = {6-7},

  year      = {1991},

  pages     = {707-732},

  bibsource = {DBLP, http://dblp.uni-trier.de}

}

 

@article{polymenakos1,

 author = {L. C. Polymenakos and D. P. Bertsekas},

 title = {Parallel shortest path auction algorithms},

 journal = {Parallel Comput.},

 volume = {20},

 number = {9},

 year = {1994},

 issn = {0167-8191},

 pages = {1221--1247},

 doi = {http://dx.doi.org/10.1016/0167-8191(94)90035-3},

 publisher = {Elsevier Science Publishers B. V.},

 address = {Amsterdam, The Netherlands, The Netherlands},

 }

 

@ARTICLE{hawk1,

title={Parallel implementation of the auction algorithm on the Intel hypercube},

author={Bagherzadeh, N. and Hawk, K.},

journal={Parallel Processing Symposium, 1992. Proceedings., Sixth International},

year={1992},

month={Mar},

volume={},

number={},

pages={443-447},

doi={10.1109/IPPS.1992.223005},

}

 

@article{cohen1,

 author = {Natalya Cohen and Jack Brassil},

 title = {A Parallel Pruning Technique for Highly Asymmetric Assignment Problems},

 journal = {IEEE Trans. Parallel Distrib. Syst.},

 volume = {11},

 number = {6},

 year = {2000},

 issn = {1045-9219},

 pages = {550--558},

 doi = {http://dx.doi.org/10.1109/71.862206},

 publisher = {IEEE Press},

 address = {Piscataway, NJ, USA},

 }

 

@article{mckeownp,

 author = {McKeown,, Nick},

 title = {The iSLIP scheduling algorithm for input-queued switches},

 journal = {IEEE/ACM Trans. Netw.},

 volume = {7},

 number = {2},

 year = {1999},

 issn = {1063-6692},

 pages = {188--201},

 doi = {http://dx.doi.org/10.1109/90.769767},

 publisher = {IEEE Press},

 address = {Piscataway, NJ, USA},

 }

 

@inproceedings{giaccone1,

 author = {Paolo Giaccone and Devavrat Shah and Balaji Prabhakar},

 title = {An Implementable Parallel Scheduler for Input-Queued Switches},

 booktitle = {HOTI '01: Proceedings of the The Ninth Symposium on High Performance Interconnects (HOTI '01)},

 year = {2001},

 isbn = {0-7695-1357-3},

 pages = {9},

 publisher = {IEEE Computer Society},

 address = {Washington, DC, USA},

 }

 

@inproceedings{nong1,

 author = {Ge Nong and Jogesh K. Muppala and Mounir Hamdi},

 title = {Performance Analysis of Input Queueing ATM Switches with Parallel Iterative Matching Scheduling},

 booktitle = {Proceedings of the IFIP TC6 WG6.3/WG6.4 Fifth International Workshop on Performance Modelling and Evaluation of ATM Networks},

 year = {2000},

 isbn = {0-412-83640-8},

 pages = {189--207},

 publisher = {Kluwer, B.V.},

 address = {Deventer, The Netherlands, The Netherlands},

 }

 

 

@article{ahuja3,

 author = {Ravindra K. Ahuja and James B. Orlin},

 title = {A faster algorithm for the inverse spanning tree problem},

 journal = {J. Algorithms},

 volume = {34},

 number = {1},

 year = {2000},

 issn = {0196-6774},

 pages = {177--193},

 doi = {http://dx.doi.org/10.1006/jagm.1999.1052},

 publisher = {Academic Press, Inc.},

 address = {Duluth, MN, USA},

 }

 

@phdthesis{pothen1,

 author = {Alex Pothen},

 title = {Sparse null bases and marriage theorems},

 year = {1984},

 order_no = {AAI8415425},

 school = {Cornell University},

 address = {Ithaca, NY, USA},

 }

 

@techreport{coleman2,

 author = {Thomas F. Coleman and Alex Pothen},

 title = {The Sparse Null Space Basis Problem},

 year = {1984},

 source = {http://www.ncstrl.org:8900/ncstrl/servlet/search?formname=detail\&id=oai%3Ancstrlh%3Acornellcs%3ACORNELLCS%3ATR84-598},

 publisher = {Cornell University},

 address = {Ithaca, NY, USA},

 }

 

@ARTICLE{coleman1,

 author = {Thomas F Coleman and Alex Pothen},

 title = {The null space problem I. complexity},

 journal = {SIAM J. Algebraic Discrete Methods},

 volume = {7},

 number = {4},

 year = {1986},

 issn = {0196-5212},

 pages = {527--537},

 publisher = {Society for Industrial and Applied Mathematics},

 address = {Philadelphia, PA, USA},

 }

 

@ARTICLE{coleman3,

 author = {T. F. Coleman and A. Pothen},

 title = {The null space problem II. Algorithms},

 journal = {SIAM J. Algebraic Discrete Methods},

 volume = {8},

 number = {4},

 year = {1987},

 issn = {0196-5212},

 pages = {544--563},

 publisher = {Society for Industrial and Applied Mathematics},

 address = {Philadelphia, PA, USA},

 }

 

@ARTICLE{pothen3,

 author = {Alex Pothen and Chin-Ju Fan},

 title = {Computing the block triangular form of a sparse matrix},

 journal = {ACM Trans. Math. Softw.},

 volume = {16},

 number = {4},

 year = {1990},

 issn = {0098-3500},

 pages = {303--324},

 doi = {http://doi.acm.org/10.1145/98267.98287},

 publisher = {ACM},

 address = {New York, NY, USA},

 }

 

@ARTICLE{duff1,

 author = {I. S. Duff and J. Koster},

 title = {On Algorithms For Permuting Large Entries to the Diagonal of a Sparse Matrix},

 journal = {SIAM J. Matrix Anal. Appl.},

 volume = {22},

 number = {4},

 year = {2000},

 issn = {0895-4798},

 pages = {973--996},

 doi = {http://dx.doi.org/10.1137/S0895479899358443},

 publisher = {Society for Industrial and Applied Mathematics},

 address = {Philadelphia, PA, USA},

 }

 

@inproceedings{li1,

 author = {Xiaoye S. Li and James W. Demmel},

 title = {Making sparse Gaussian elimination scalable by static pivoting},

 booktitle = {Supercomputing '98: Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM)},

 year = {1998},

 isbn = {0-89791-984-X},

 pages = {1--17},

 location = {San Jose, CA},

 publisher = {IEEE Computer Society},

 address = {Washington, DC, USA},

 }

 

@ARTICLE{duff2,

 author = {Iain S. Duff and Jacko Koster},

 title = {The Design and Use of Algorithms for Permuting Large Entries to the Diagonal of Sparse Matrices},

 journal = {SIAM J. Matrix Anal. Appl.},

 volume = {20},

 number = {4},

 year = {1999},

 issn = {0895-4798},

 pages = {889--901},

 doi = {http://dx.doi.org/10.1137/S0895479897317661},

 publisher = {Society for Industrial and Applied Mathematics},

 address = {Philadelphia, PA, USA},

 }

 

@ARTICLE{duff3,

 author = {Iain S. Duff and St\'{e}phane Pralet},

 title = {Strategies for Scaling and Pivoting for Sparse Symmetric Indefinite Problems},

 journal = {SIAM J. Matrix Anal. Appl.},

 volume = {27},

 number = {2},

 year = {2005},

 issn = {0895-4798},

 pages = {313--340},

 doi = {http://dx.doi.org/10.1137/04061043X},

 publisher = {Society for Industrial and Applied Mathematics},

 address = {Philadelphia, PA, USA},

 }

 

@inproceedings{karypis2,

 author = {George Karypis and Vipin Kumar},

 title = {Analysis of multilevel graph partitioning},

 booktitle = {Supercomputing '95: Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM)},

 year = {1995},

 isbn = {0-89791-816-9},

 pages = {29},

 location = {San Diego, California, United States},

 doi = {http://doi.acm.org/10.1145/224170.224229},

 publisher = {ACM},

 address = {New York, NY, USA},

 }

 

@ARTICLE{schenk1,

 author = {Olaf Schenk and Andreas W\"{a}chter and Michael Hagemann},

 title = {Matching-based preprocessing algorithms to the solution of saddle-point problems in large-scale nonconvex interior-point optimization},

 journal = {Comput. Optim. Appl.},

 volume = {36},

 number = {2-3},

 year = {2007},

 issn = {0926-6003},

 pages = {321--341},

 doi = {http://dx.doi.org/10.1007/s10589-006-9003-y},

 publisher = {Kluwer Academic Publishers},

 address = {Norwell, MA, USA},

 }

 

@ARTICLE{pinar1,

 author = {A. Pinar and E. Chow and A. Pothen},

 title = {Combinatorial Algorithms for Computing Column Space Bases that have Sparse Inverses},

 journal = {Electronic Transactions on Numerical Analysis},

 volume = {22},

 year = {2006},

 pages = {122--145},

}

 

@MISC{hendrickson1,

 author = {Bruce Hendrickson},

 title = {Combinatorial Scientific Computing: The Role of Discrete Algorithms in Computational Science and Engineering},

 booktitle = {Planery talk at SIAM CSE},

 year = {2003},

}

 

@inproceedings{hendrickson2,

 author = {Bruce Hendrickson and Alex Pothen},

 title = {Combinatorial Scientific Computing: The Enabling Power of Discrete Algorithms in Computational Science},

 booktitle = {Proceedings of the 7th International Meeting on High Performance Computing for Computational Science (VECPAR'06)},

 year = {2006},

 publisher = {Springer-Verlag},

 }

 

@MISC{keyes1,

 author = {David Keyes},

 title = {A Science-Based Case for Large-Scale Simulation, The SCaLes Report},

 note = {(http://www.pnl.gov/scales/)},

 year = {2003},

}

 

@article{mehta1,

 author = {Aranyak Mehta and Amin Saberi and Umesh Vazirani and Vijay Vazirani},

 title = {AdWords and generalized online matching},

 journal = {J. ACM},

 volume = {54},

 number = {5},

 year = {2007},

 issn = {0004-5411},

 pages = {22},

 doi = {http://doi.acm.org/10.1145/1284320.1284321},

 publisher = {ACM},

 address = {New York, NY, USA},

 }

 

@inproceedings{mckeown1,

  author    = {Nick McKeown and Venkat Anantharam and Jean C. Walrand},

  title     = {Achieving 100\% Throughput in an Input-Queued Switch},

  booktitle = {INFOCOM},

  year      = {1996},

  pages     = {296-302},

}

 

@inproceedings{ glover1,

    author = {Fred Glover and M. Laguna},

    title = {Tabu Search},

    booktitle = {Modern Heuristic Techniques for Combinatorial Problems},

    publisher = {Blackwell Scientific Publishing},

    address = {Oxford, England},

    editor = {C. Reeves},

    year = {1993},

}

 

Communication:

The current list is an adaptation from the references used in Mahantesh’s thesis; it is not a comprehensive list. Please contact us with your suggestions:

 

Mahantesh Halappanavar (mhalappa –at– odu –dot– edu)

Alex Pothen (apothen –at– purdue  –dot– edu)

Florin Dobrian (dobrain –at– cs –dot– odu –dot– edu)

 

Last updated ... May 19, 2009