%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%% BOOKS   %%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@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},
 }

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%% GENERAL MATCHING PAPERS %%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

@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},
 }

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%% VTX WTD MATCHING %%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

@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 }, 
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%% APPROX ALGORITHMS %%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@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},
 }

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%% PARALLEL MATCHING %%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@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},
 }


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%% APPLICATIONS %%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

@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},
}