@TechReport{SW05ext, author = {T. Schank and D. Wagner}, title = {Finding, counting and listing all triangles in large graphs, an experimental study}, institution = {Universit\"at Karlsruhe, Fakult\"at f\"ur Informatik}, year = {2005}, OPTkey = {}, OPTtype = {}, OPTnumber = {}, OPTaddress = {}, OPTmonth = {}, OPTnote = {}, OPTannote = {} } @InProceedings{SW05, author = {T. Schank and D. Wagner}, title = {Finding, counting and listing all triangles in large graphs, an experimental study.}, booktitle = {4th International Workshop on Experimental and Efficient Algorithms (WEA'05)}, OPTcrossref = {}, OPTkey = {}, OPTpages = {}, year = {2005}, OPTeditor = {}, volume = {3503}, OPTnumber = {}, series = {lncs}, OPTaddress = {}, OPTmonth = {}, OPTorganization = {}, publisher = {Springer}, OPTnote = {}, OPTannote = {} } @Article{WS98, author = {D.J. Watts and S. H. Strogatz}, title = {Collective dynamics of ``small-world'' networks}, journal = {Nature}, year = {1998}, OPTkey = {}, volume = {393}, OPTnumber = {}, pages = {440-442}, OPTmonth = {}, OPTnote = {}, OPTannote = {} } @InProceedings{LLMMS03, author = {L. Laura and S. Leonardi and S. Millozzi and U. Meyer and J. F. Sibeyn}, title = {Algorithms and Experiments for the Webgraph}, booktitle = proc # "11th " # esa, publisher = springer, series = lncs, OPTvolume = 2461, pages = "703--714", year = 2003, } @MastersThesis{AjwaniThesis, author = {D. Ajwani}, title = {Design, implementation and experimental study of external memory BFS algorithms}, school = {Universit\"at des Saarlandes}, year = {2005}, OPTkey = {}, OPTtype = {}, OPTaddress = {}, OPTmonth = {}, OPTnote = {}, OPTannote = {} } @article{MM93, author = "U. Manber and G. Myers", title = "Suffix Arrays: A New Method For On-Line String Searches", journal = sicomp, volume = 22, number = 5, year = 1993, month = oct, pages = "935--948" } @article{Haanpaa2004, author = {Harri Haanp\"a\"a}, journal = {Journal of Integer Sequences}, number = {2}, pages = {article 04.1.8}, title = {Minimum Sum and Difference Covers of {A}belian Groups}, volume = {7}, year = {2004}, } @Article{SS01, author = {K. Sadakane and T.Shibuya}, title = {Indexing Huge Genome Sequences for Solving Various Problems}, journal = {Genome Informatics}, year = {2001}, volume = {12}, pages = {175--183}, } @inproceedings{LSSY02, author = "T.-W. Lam and K. Sadakane and W.-K. Sung and Siu-Ming Yiu", title = "A Space and Time Efficient Algorithm for Constructing Compressed Suffix Arrays", booktitle = proc # "8th " # cocoon, publisher = springer, series = lncs, volume = 2387, year = 2002, pages = "401--410", } @InProceedings{MF02, author = "G. Manzini and P. Ferragina", title = "Engineering a lightweight suffix array construction algorithm", booktitle = proc # "10th " # esa, publisher = springer, series = lncs, volume = 2461, pages = "698--710", year = 2002, } @InCollection{GBYS92, author = "G. Gonnet and R. Baeza-Yates and T. Snider", title = "New Indices for Text: {PAT} trees and {PAT} arrays", booktitle = "Information Retrieval: Data Structures \& Algorithms", editor = "W. B. Frakes and R. Baeza-Yates", publisher = "Prentice-Hall", year = "1992", } @TechReport{BW94, author = "M. Burrows and D. J. Wheeler", title = "A block-sorting lossless data compression algorithm.", institution = "SRC (digital, Palo Alto)", type = "Technical Report", number = "124", month = may, year = "1994", } @Article{KarSan05, author = "J. K{\"a}rkk{\"a}inen and P. Sanders and S. Burkhardt", title = "Linear Work Suffix Array Construction", journal = "Journal of the ACM", year = 2005, note = "accepted for publication" } @InProceedings{KSPP03, title = "Linear-Time Construction of Suffix Arrays", author = "D. K. Kim and J. S. Sim and H. Park and K. Park", booktitle = proc # "14th " # cpm, publisher = "Springer", month = jun, series = lncs, volume = "2676", pages = "186-199", year = 2003, } @InProceedings{KA03, title = "Space Efficient Linear Time Construction of Suffix Arrays", author = "P. Ko and S. Aluru", booktitle = proc # "14th " # cpm, publisher = "Springer", series = lncs, volume = "2089", pages = "200--210", year = 2003, } @Article{CF02, author = "A. Crauser and P. Ferragina", title = "Theoretical and Experimental Study on the Construction of Suffix Arrays in External Memory", journal = "Algorithmica", volume = "32", number = "1", pages = "1--35", year = "2002", } @InProceedings{AKO02b, author = "M. I. Abouelhoda and S. Kurtz and E. Ohlebusch", title = "The Enhanced Suffix Array and Its Applications to Genome Analysis", booktitle = proc # "2nd " # "Workshop on Algorithms in Bioinformatics", series = lncs, volume = "2452", publisher = springer, pages = "449--463", year = "2002", } @Article{DKMS06, author = {R. Dementiev and J. K\"arkk\"ainen and J. Mehnert and P. Sanders}, title = {Better External Memory Suffix Array Construction}, journal = {ACM Journal of Experimental Algorithmics}, volume = X, year = 2006, note = "to appear" } @Article{Chazelle00, author = {B. Chazelle}, title = {A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity}, journal = {Journal of the ACM}, year = {2000}, key = {47}, OPTvolume = {}, OPTnumber = {}, pages = {1028-1047}, OPTmonth = {}, OPTnote = {}, OPTannote = {} } @Misc{DominikBachelor, OPTkey = {}, author = {D. Schultes}, title = {External memory minimum spanning trees}, howpublished = {Bachelor thesis, Max-Planck-Institut f. Informatik and Saarland University, {\url{http://www.dominik-schultes.de/emmst/}}}, month = {August}, year = {2003}, OPTnote = {}, OPTannote = {} } @InProceedings{BDIW02, author = {M. Bander and Z. Duan and J. Iacono and J. Wu}, title = {A locality-preserving cache-oblivious dynamic dictionary}, booktitle = {13th Annual ACM-SIAM Symposium On Descrete Algorithms (SODA-02)}, OPTcrossref = {}, OPTkey = {}, OPTpages = {}, year = {2002}, OPTeditor = {}, OPTvolume = {}, OPTnumber = {}, OPTseries = {}, OPTaddress = {}, OPTmonth = {}, OPTorganization = {}, OPTpublisher = {}, OPTnote = {}, OPTannote = {} } @InProceedings{BDB99, author = {Michael A. Olson and Keith Bostic and Margo Seltzer }, title = "{Berkeley DB}", booktitle = "{USENIX Annual Technical Conference}", OPTcrossref = {}, OPTkey = {}, pages = {183–192}, year = {1999}, OPTeditor = {}, OPTvolume = {}, OPTnumber = {}, OPTseries = {}, OPTaddress = {}, month = {June}, OPTorganization = {}, OPTpublisher = {}, OPTnote = {}, OPTannote = {} } @Article{BM72, author = {R. Bayer and E. McCreight}, title = {Organization and maintenance of large ordered indices}, journal = {Acta Informatica}, year = {1972}, OPTkey = {}, OPTvolume = {1}, OPTnumber = {1}, pages = {173–189}, OPTmonth = {}, OPTnote = {}, OPTannote = {} } @INPROCEEDINGS{Ajwani06, AUTHOR = {Ajwani, Deepak and Dementiev, Roman and Meyer, Ulrich}, TITLE = "{A computational study of external memory BFS algorithms}", BOOKTITLE = {ACM-SIAM Symposium on Discrete Algorithms (SODA-06)}, PUBLISHER = {ACM}, YEAR = {2006}, PAGES = {601-610}, ADDRESS = {Miami, USA}, } @TechReport{DKS05ext, author = {R. Dementiev and L. Kettner and P. Sanders}, title = "{Stxxl: Standard Template Library for XXL Data Sets}", institution = {Fakult\"at f\"ur Informatik, University of Karlsruhe}, year = {2005}, OPTkey = {}, OPTtype = {}, number = {18}, OPTaddress = {}, OPTmonth = {}, OPTnote = {}, OPTannote = {} } @Article{Finocchi05, author = {I. Finocchi and A. Panconesi and R. Silvestri}, title = {An Experimental Analysis of Simple, Distributed Vertex Coloring Algorithms}, journal = {Algorithmica}, year = {2005}, OPTkey = {}, volume = {41}, OPTnumber = {}, pages = {1-23}, OPTmonth = {}, OPTnote = {}, OPTannote = {} } @Misc{Culberson, OPTkey = {}, author = {J.C. Culberson}, OPTtitle = "{}", note = {\url{http://web.cs.ualberta.ca/~joe/Coloring/}}, OPTmonth = {}, OPTyear = {}, OPTnote = {}, OPTannote = {} } @TechReport{Allwright95, author = {J.R. Allwright and R. Bordawekar and P.D. Coddington and K. Dincer and C.L. Martin}, title = {A comparison of parallel graph coloring algorithms}, institution = {Northeast Parallel Architecture Center, Syracuse University}, year = {1995}, OPTkey = {}, OPTtype = {}, OPTnumber = {}, OPTaddress = {}, OPTmonth = {}, OPTnote = {}, OPTannote = {} } @Article{JonesPlassmann93, author = {M.T. Jones and P.E. Plassmann}, title = {A parallel graph coloring heuristics}, journal = {SIAM Joirnal on Scientific Computing}, year = {1993}, OPTkey = {}, volume = {14}, number = {3}, pages = {654-669}, OPTmonth = {}, OPTnote = {}, OPTannote = {} } @InProceedings{DKS05, author = {R. Dementiev and L. Kettner and P. Sanders}, title = "{Stxxl: Standard Template Library for XXL Data Sets}", booktitle = "{13th Ann. European Symposium on Algorithms (ESA)}", OPTcrossref = {}, OPTkey = {}, OPTeditor = {}, OPTaddress = {}, volume = 3669, year = 2005, series = "{LNCS}", OPTmonth = {}, OPTorganization = {}, publisher = {Springer}, OPTnote = {}, OPTannote = {}, pages = {640-651}, } @Article{Welsh67, author = {D. J. A. Welsh and M. B. Powel}, title = {An Upper Bound for the Chromatic Number of a Graph and its Application to Timetabling Problems}, journal = {Computing Journal}, year = {1967}, OPTkey = {}, volume = {10}, number = {85}, OPTpages = {}, OPTmonth = {}, OPTnote = {}, OPTannote = {} } @Book{Matula72, author = {D. W. Matula and G. Marble and J.D. Isaacson}, ALTeditor = {}, title = {Graph Coloring Algorithms}, publisher = {Academic Press}, year = {1972}, OPTkey = {}, OPTvolume = {}, OPTnumber = {}, OPTseries = {}, address = {New York}, OPTedition = {}, OPTmonth = {}, OPTnote = {}, OPTannote = {} } @InProceedings{AgarwalArgeYi2005, author = {Pankaj K. Agarwal and Lars Arge and Ke Yi}, title = "{I/O-Efficient Construction of Constrained Delaunay Triangulations}", booktitle = {13th European Symposium on Algorithms (ESA '05)}, OPTcrossref = {}, OPTkey = {}, pages = {355-366}, year = {2005}, OPTeditor = {}, OPTvolume = {}, number = {3669}, series = {LNCS}, OPTaddress = {}, OPTmonth = {}, OPTorganization = {}, OPTpublisher = {}, OPTnote = {}, OPTannote = {} } @Misc{StreamBench, OPTkey = {}, OPTauthor = {}, title = "{The STREAM Benchmark: Computer Memory Bandwidth.}", note = {\url{http://www.streambench.org/}}, OPTmonth = {}, OPTyear = {}, OPTnote = {}, OPTannote = {} } @Article{Garey76, author = {M. R. Garey and D. S. Johnson and L. Stockmeyer}, title = "{Some simplified NP-complete graph problems}", journal = {Theoret. Comput. Sci.}, year = {1976}, OPTkey = {}, volume = {1}, OPTnumber = {}, pages = {237-267}, OPTmonth = {}, OPTnote = {}, OPTannote = {} } @InProceedings{Robertson96, author = {Neil Robertson and Daniel P. Sanders and Paul Seymour and Robin Thomas}, title = {Efficiently four-coloring planar graphs}, booktitle = "{Twenty-eighth annual ACM symposium on Theory of computing}", OPTcrossref = {}, OPTkey = {}, pages = { 571 - 575}, year = {1996}, OPTeditor = {}, OPTvolume = {}, OPTnumber = {}, OPTseries = {}, OPTaddress = {}, OPTmonth = {}, OPTorganization = {}, OPTpublisher = {}, OPTnote = {}, OPTannote = {} } @Article{Frederickson84, author = {Greg N. Frederickson}, title = {On linear-time algorithms for five-coloring planar graphs}, journal = {Information Processing Letters}, year = {1984}, OPTkey = {}, volume = {19}, number = {5}, pages = {219 - 224}, month = {November}, OPTnote = {}, OPTannote = {} } @InProceedings{AlonColoring, author = "Noga Alon", title = "A simple algorithm for edge-coloring bipartite multigraphs", booktitle = "Information Processing Letters, Vol. 85, issue 6", pages = "301--302", year = 2003 } @article{Hagerup, author = {Torben Hagerup and Marek Chrobak and Krzysztof Diks}, title = {Optimal parallel 5-colouring of planar graphs}, journal = {SIAM J. Comput.}, volume = {18}, number = {2}, year = {1989}, issn = {0097-5397}, pages = {288--300}, publisher = {Society for Industrial and Applied Mathematics}, } @article{Boyar, author = {Joan F. Boyar and Howard J. Karloff}, title = {Coloring Planar Graphs in Parallel}, journal = {J. Algorithms}, volume = {8}, number = {4}, year = {1987}, pages = {470--479} } @InProceedings{Naor, author = "Joseph Naor", title = "A Fast Parallel COloring of Planar Graphs with five colors", booktitle = "Information Processing Letters, Vol. 25, issue ?", pages = "51--53", year = 1987 } @inproceedings{ Goldberg, author = "A. Goldberg and S. Plotkin and G. Shannon", title = "Parallel symmetry-breaking in sparse graphs", pages = "315--324", year = "1987" } @InProceedings{Bauernoeppel85, author = {F. Bauern\"oppel and H. Jung}, title = {Fast parallel vertex colouring}, booktitle = {5th International Conference on Fundamentals of Computational Theory}, OPTcrossref = {}, OPTkey = {}, pages = {28-35}, year = {1985}, OPTeditor = {}, OPTvolume = {}, OPTnumber = {}, series = {LNCS 199}, OPTaddress = {}, OPTmonth = {}, OPTorganization = {}, OPTpublisher = {}, OPTnote = {}, OPTannote = {} } @inproceedings( Diks, author= {Krzysztof Diks}, title= { A Fast Parallel Algorithm for Six-Colouring of Planar Graphs (Extended Abstract)}, booktitle= { Mathematical Foundations of Computer Science 1986 (Proceedings of the Twelfth Symposium Held in Bratislava, Czechoslovakia)}, year= 1986, editor= {J. Gruska and B. Rovan and J. Wiedermann}, pages= {273--282}, publisher= {Springer-Verlag}, address= {Berlin}, series= {LNCS}, volume= 233, keywords= {graph color}, mrnumbers= { 87m#68008}, classif= {Planar/Parallel Coloring} ) @MastersThesis{JensThesis, author = {Jens Mehnert}, title = "{External Memory Suffix Array Construction}", school = {University of Saarland, Germany}, year = {2004}, OPTkey = {}, OPTtype = {}, OPTaddress = {}, month = {November}, note = "{\url{http://algo2.iti.uka.de/dementiev/esuffix/docu/data/diplom.pdf}}", OPTannote = {} } @Article{HK79, author = {Frank Harary and Helene J. Kommel}, title = {Matrix measures for transitivity and balance}, journal = {Journal of Mathematical Sociology}, year = {1979}, OPTkey = {}, volume = {6}, OPTnumber = {}, pages = {199-210}, OPTmonth = {}, OPTnote = {}, OPTannote = {} } @Book{SzarneckiGenerProgr, author = {Krzysztof Czarnecki and Ulrich Eisenecker}, ALTeditor = {}, title = "{Generative Programming: Methods, Tools, and Applications}", publisher = "{Addison Wesley Professional}", year = {2000}, OPTkey = {}, OPTvolume = {}, OPTnumber = {}, OPTseries = {}, OPTaddress = {}, OPTedition = {}, OPTmonth = {}, note = "{\url{http://www.generative-programming.org/}}", OPTannote = {} } @InProceedings{FG05, author = {E. R. Davidson and T. H. Cormen}, title = "{Building on a Framework: Using FG for More Flexibility and Improved Performance in Parallel Programs}", booktitle = "{19th International Parallel and Distributed Processing Symposium (IPDPS 2005)}", OPTcrossref = {}, OPTkey = {}, OPTpages = {}, OPTyear = {}, OPTeditor = {}, OPTvolume = {}, OPTnumber = {}, OPTseries = {}, OPTaddress = {}, OPTmonth = {}, OPTorganization = {}, OPTpublisher = {}, note = {to appear}, OPTannote = {} } @Misc{SchultesCC03, author = {Dominik Schultes}, title = "{External Memory Spanning Forests and Connected Components}", howpublished = "{\url{http://i10www.ira.uka.de/dementiev/files/cc.pdf}}", month = {September}, year = {2003}, OPTnote = {}, OPTannote = {} } @InProceedings{Vengroff94, author = {D. E. Vengroff}, title = "{A Transparent Parallel I/O Environment}", booktitle = {Third DAGS Symposium on Parallel Computation}, OPTcrossref = {}, OPTkey = {}, pages = {117-134}, year = {1994}, OPTeditor = {}, OPTvolume = {}, OPTnumber = {}, OPTseries = {}, address = {Hanover, NH}, month = {July}, OPTorganization = {}, OPTpublisher = {}, OPTnote = {}, OPTannote = {} } @MastersThesis{Ajwani05, author = {Deepak Ajwani}, title = "{Design, Implementation and Experimental Study of External Memory BFS Algorithms}", school = "{Max-Planck-Institut f\"ur Informatik}", year = {2005}, OPTkey = {}, OPTtype = {}, address = "{Saarbr\"ucken, Germany}", month = {January}, OPTnote = {}, OPTannote = {} } @InProceedings{MM02, author = {K. Mehlhorn and U. Meyer}, title = "{External-Memory Breadth-First Search with Sublinear I/O}", booktitle = "{10th Ann. European Symposium on Algorithms (ESA)}", OPTcrossref = {}, OPTkey = {}, pages = {723-735}, year = {2002}, OPTeditor = {}, volume = {2461}, number = {723}, series = "{LNCS}", OPTaddress = {}, OPTmonth = {}, OPTorganization = {}, OPTpublisher = {}, OPTnote = {}, OPTannote = {} } @Article{Brengel00, author = {Klaus Brengel and Andreas Crauser and Paolo Ferragina and Ulrich Meyer}, title = {An Experimental Study of Priority Queues in External Memory}, journal = {ACM Journal of Experimental Algorithms}, year = {2000}, volume = {5}, number = {17}, OPTpages = {}, OPTmonth = {}, OPTnote = {}, OPTannote = {} } @PhdThesis{ZehPhd, author = {Norbert Ralf Zeh}, title = "{I/O Efficient Algorithms for Shortest Path Related Problems}", school = {Carleton University, Ottawa}, year = {2002}, OPTkey = {}, OPTtype = {}, OPTaddress = {}, month = {April}, OPTnote = {}, OPTannote = {} } @InProceedings{TPIEscientific96, author = {D. E. Vengroff and J. S. Vitter}, title = "{I/O-Efficient Scientific Computation using TPIE}", booktitle = {Goddard Conference on Mass Storage Systems and Technologies}, OPTcrossref = {}, OPTkey = {}, pages = {553--570}, year = {1996}, OPTeditor = {}, volume = {2}, OPTnumber = {}, OPTseries = {}, OPTaddress = {}, OPTmonth = {}, OPTorganization = {}, OPTpublisher = {}, note = {published in NASA Conference Publication 3340}, OPTannote = {} } @PhdThesis{ChiangPHD, author = {Y.-J. Chiang}, title = {Dynamic and I/O-Efficient Algorithms for Computational Geometry and Graph Algorithms}, school = {Brown University}, year = {1995} } @InProceedings{APV02, author = "L. Arge and O. Procopiuc and J. S. Vitter", title = "{Implementing I/O-efficient Data Structures Using TPIE}", booktitle = "10th European Symposium on Algorithms (ESA)", pages = "88--100", year = 2002, volume = 2461, series = "LNCS", publisher = "Springer" } @InProceedings{CraMeh99, author = "A. Crauser and K. Mehlhorn", title = "{LEDA-SM}, extending {LEDA} to Secondary Memory", booktitle = "3rd International Workshop on Algorithmic Engineering (WAE)", pages = "228--242", year = 1999, volume = 1668, series = "LNCS" } @Article{VitShr94both, author = "J. S. Vitter and E. A. M. Shriver", title = "Algorithms for parallel memory, {I/II}", journal = "Algorithmica", year = 1994, volume = 12, number = "2/3", pages = "110--169" } @InProceedings{Bkdtree03, author = {O. Procopiuc and P. K. Agarwal and L. Arge and J. S. Vitter}, title = "{Bkd-tree: A Dynamic Scalable KD-Tree}", booktitle = {Proc. 8th Int'l Symposium on Spatial and Temporal Databases (SSTD '03)}, pages = {46-65} } @InProceedings{DynRTrees99, author = {L. Arge and K. H. Hinrichs and J. Vahrenhold and J. S. Vitter}, title = "{Efficient Bulk Operations on Dynamic R-trees}", booktitle = {1st Workshop on Algorithm Engineering and Experimentation (ALENEX '99)}, OPTcrossref = {}, OPTkey = {}, pages = {328-348}, year = {1999}, OPTeditor = {}, OPTvolume = {}, OPTnumber = {}, series = {Lecture Notes in Computer Science}, OPTaddress = {}, OPTmonth = {}, OPTorganization = {}, publisher = {Springer-Verlag}, OPTnote = {}, OPTannote = {} } @InProceedings{CRBtree03, author = {P. K. Agarwal and L. Arge and S. Govindarajan}, title = "{CRB-Tree: An Efficient Indexing Scheme for Range Aggregate Queries}", booktitle = {Proc. 9th Int'l Conference on Database Theory (ICDT '03)}, OPTcrossref = {}, OPTkey = {}, pages = {143-157}, year = {2003}, OPTeditor = {}, OPTvolume = {}, OPTnumber = {}, OPTseries = {}, OPTaddress = {}, OPTmonth = {}, OPTorganization = {}, OPTpublisher = {}, OPTnote = {}, OPTannote = {} } @PHDTHESIS{andreas_diss, AUTHOR = {A. Crauser}, TITLE = "{LEDA-SM: External Memory Algorithms and Data Structures in Theory and Practice}", ADDRESS = {Saarbr{\"u}cken}, YEAR = {2001}, SCHOOL = {Universit{\"a}t des Saarlandes}, LOCATION = {Fachbereichsbibliothek Informatik}, BIBTYPE = {PHDTHESIS} } @manual{ ledasm_manual, author = "{Andreas Crauser, Kurt Mehlhorn}", title = "{LEDA-SM: A Platform for Secondary Memory Computation}", year = 1999 } @manual{ tpie_manual, author ="{Lars Arge, Rakesh Barve, David Hutchinson, Octavian Procopiuc, Laura Toma, Darren Erik Vengroff, Rajiv Wickeremesinghe}", title ="{TPIE: User manual and reference}", year = 2003, month = {November} } @techreport{ stepanov94standard, author = "A. A. Stepanov and M. Lee", title = "{The Standard Template Library}", number = "X3J16/94-0095, WG21/N0482", year = "1994", institution = "Silicon Graphics Inc., Hewlett Packard Laboratories" } @Misc{ Moore2000, author = {R. W. Moore}, title = {Enabling Petabyte Computing}, howpublished = {\url{http://www.nap.edu/html/whitepapers/ch-48.html}}, year = {2000} } @InBook{BillingLarge, author = {Andrew Hume}, title = {Handbook of massive data sets}, chapter = {Billing in the large}, publisher = {Kluwer Academic Publishers}, year = {2002}, pages = {895 -- 909} } Article{VitShr94both, author = "J. S. Vitter and E. A. M. Shriver", title = "Algorithms for parallel memory, {I/II}", journal = "Algorithmica", year = 1994, volume = 12, number = "2/3", pages = "110--169" } % Abkuerzungen @string{sicomp = "SIAM Journal on Computing"} @String{acmcs = "{ACM} Computing Surveys"} @String{uka = "Universit{\"a}t Karlsruhe"} @String{aint = "Artificial Intelligence"} @String{cacm = "Communications of the ACM"} @String{fgcs = "Future Generation Computing Systems"} @String{focs = "Foundations of Computer Science"} @String{icpp = "International Conference on Parallel Processing"} @String{ipps = "International Parallel Processing Symposium"} @String{ijpp = "International Journal of Parallel Programming"} @String{jacm = "Journal of the ACM"} @String{jpdc = "Journal of Parallel and Distributed Computing"} @String{paco = "Parallel Computing"} @String{pdpta = "International Conference on Parallel and Distributed Processing Techniques and Applications"} @String{tpds = "IEEE Transactions on Parallel and Distributed Systems"} @String{pami = "IEEE Transactions on Pattern Analysis and Machine Intelligence"} @String{ietc = "IEEE Transactions on Computers"} @String{ipl = "Information Processing Letters"} @String{spaa = "ACM Symposium on Parallel Architectures and Algorithms"} @String{stoc = "ACM Symposium on the Theory of Computing"} @BOOK{compiler, author = "Steven S. Muchnick", title = "Advanced {C}ompiler {D}esign and {I}mplementation", publisher = "Morgan Kaufmann Publishers", address = "San Francisco, Kalifornien", year = "1997" } @InProceedings{Itanium2-L2, author = {Reid Riedlinger and Tom Grutkowski}, title = {The {H}igh {B}andwidth, 256{KB} 2nd {L}evel {C}ache on an {I}tanium{\texttrademark} {M}icroprocessor}, booktitle = {Proceedings of the IEEE International Solid-State Circuits Conference}, month = feb, year = {2002}, address = {San Francisco} } @article{introsort, author = {David R. Musser}, title = {Introspective sorting and selection algorithms}, journal = {Softw. Pract. Exper.}, volume = {27}, number = {8}, year = {1997}, issn = {0038-0644}, pages = {983--993}, publisher = {John Wiley \& Sons, Inc.}, } @ARTICLE{intel-compiler, author = "Carole Dulong and Rakesh Krishnaiyer and Dattatraya Kulkarni and Daniel Lavery and Wei Li and John Ng and David Sehr", title = "An {O}verview of the {I}ntel {IA}-64 {C}ompiler", journal = "Intel Technology Journal", number = "Q4", year = 1999, } @article{SWP-survey, author = {Allan, V.H. and Jones, R.B. and Lee, R.M. and Allan, S.J.}, title = {{S}oftware {P}ipelining}, journal = {{C}omputing {S}urveys}, year = {1995}, month = sep, volume = {27}, number = {3}, pages = {367--432} } @manual{ita2opt, title = {Intel {I}tanium 2 {P}rocessor {R}eference Manual for {S}oftware Development and {O}ptimization}, organization = {Intel}, year = {2003}, month = apr } @InProceedings{SW04, author = "P. Sanders and S. Winkel", title = "Super Scalar Sample Sort", booktitle = "12th European Symposium on Algorithms (ESA)", year = 2004, publisher = "Springer", series = "LNCS", volume = "3221", pages = "784--796" } @InProceedings{SW04www, author = "P. Sanders and S. Winkel", title = "\htmladdnormallink{Super Scalar Sample Sort}{ssss.ps.gz}", booktitle = "12th European Symposium on Algorithms (ESA)", year = 2004, publisher = "Springer {\copyright}", series = "{\htmladdnormallink{LNCS}{http://www.springer.de/comp/lncs/index}}", volume = "3221", pages = "784--796" } @TechReport{PS04b, author = "S. Pettie and P. Sanders", title = "A Simpler Linear Time $2/3-\epsilon$ Approximation\\ for Maximum Weight Matching", institution = "MPII", year = 2004, number = "MPI-I-2004-1-002" } @Article{PS04, author = "S. Pettie and P. Sanders", title = "A Simpler Linear Time $2/3-\epsilon$ Approximation\\ for Maximum Weight Matching", note = "in press", journal = "Information Processing Letters", year = 2004 } @InProceedings{San04awww, author = "P. Sanders", title = "\htmladdnormallink{Algorithms for Scalable Storage Servers}{storage.ps.gz}", booktitle = "SOFSEM 2004: Theory and Practice of Computer Science", pages = "82--101", publisher = "Springer {\copyright}", series = "{\htmladdnormallink{LNCS}{http://www.springer.de/comp/lncs/index.html}}", year = 2004, volume = 2932 } @InProceedings{San04a, author = "P. Sanders", title = "Algorithms for Scalable Storage Servers", booktitle = "SOFSEM 2004: Theory and Practice of Computer Science", pages = "82--101", publisher = "Springer", series = "LNCS", year = 2004, volume = 2932 } @Unpublished{Dem03, author = "R. Dementiev", title = "The \stxxl library", note = "Documentation and download at {\url{http://stxxl.sourceforge.net/}}", OPTkey = "", OPTmonth = "", OPTyear = "2003", OPTannote = "" } @InProceedings{DKMS05www, author = "R. Dementiev and J. Mehnert and J. K{\"a}rkk{\"a}inen and P. Sanders", title = "\htmladdnormallink{Better External Memory Suffix Array Construction}{DKMS05.pdf}", booktitle = "Workshop on Algorithm Engineering {\&} Experiments", year = 2005, address = "Vancouver" } @InProceedings{DKMS05, author = "R. Dementiev and J. Mehnert and J. K{\"a}rkk{\"a}inen and P. Sanders", title = "{Better External Memory Suffix Array Construction}", booktitle = "Workshop on Algorithm Engineering {\&} Experiments", year = 2005, address = "Vancouver", note = "\url{http://i10www.ira.uka.de/dementiev/files/DKMS05.pdf}" } @InProceedings{DKMS04, author = "R. Dementiev and L. Kettner and J. Mehnert and P. Sanders", title = "Engineering a Sorted List Data Structure for 32 Bit Keys", booktitle = "Workshop on Algorithm Engineering {\&} Experiments", year = 2004, address = "New Orleans", } @InProceedings{DKMS04www, author = "R. Dementiev and L. Kettner and J. Mehnert and P. Sanders", title = "\htmladdnormallink{Engineering a Sorted List Data Structure for 32 Bit Keys}{veb.ps.gz}", booktitle = "Workshop on Algorithm Engineering {\&} Experiments", year = 2004, address = "New Orleans", pages = "142--151" } @InProceedings{KarSan03, author = "J. K{\"a}rkk{\"a}inen and P. Sanders", title = "Simple Linear Work Suffix Array Construction", booktitle = "30th International Colloquium on Automata, Languages and Programming", series = "LNCS", year = 2003, pages = "943--955", number = 2719, } @InProceedings{KarSan03www, author = "J. K{\"a}rkk{\"a}inen and P. Sanders", title = "\htmladdnormallink{Simple Linear Work Suffix Array Construction}{suffix.ps.gz}", booktitle = "30th International Colloquium on Automata, Languages and Programming", year = 2003, pages = "943--955", publisher = "Springer {\copyright}", series = "{\htmladdnormallink{LNCS}{http://www.springer.de/comp/lncs/index.html}}", number = 2719, } @Book{MSS03www, editor = "U. Meyer and P. Sanders and J. Sibeyn", title = "\htmladdnormallink{Algorithms for Memory Hierarchies}{http://link.springer-ny.com/link/service/series/0558/tocs/t2625.htm}", publisher = "Springer", year = 2003, volume = 2625, series = "LNCS Tutorial" } @Book{MSS03, editor = "U. Meyer and P. Sanders and J. Sibeyn", title = "Algorithms for Memory Hierarchies", publisher = "Springer", year = 2003, volume = 2625, series = "LNCS Tutorial" } @TECHREPORT{KSV03, AUTHOR = {Krysta, P. and Sanders, P. and V{\"o}cking, B.}, TITLE = {Scheduling and Traffic Allocation for Tasks with Bounded Splittability }, TYPE = {Research Report}, INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik}, NUMBER = {MPI-I-2003-1-002}, MONTH = {February}, YEAR = {2003}, ISSN = {0946-011X}, } @InProceedings{KSV03a, author = "Krysta, P. and Sanders, P. and V{\"o}cking, B.", title = "Scheduling and Traffic Allocation for Tasks with Bounded Splittability", booktitle = "28th International Symposium on Mathematical Foundations of Computer Science", pages = "500--510", year = 2003, series = "LNCS", number = 2747, publisher = "Springer" } @InBook{San03a, author = "P. Sanders", title = "Algorithms for Memory Hierarchies", chapter = "1: Memory Hierarchies --- Models and Lower Bounds", publisher = "Springer", year = 2003, volume = 2625, series = "LNCS Tutorial", pages = "1--13" } @InProceedings{SanFle00, author = "P. Sanders and R. Fleischer", title = "Asymptotic Complexity from Experiments? A Case Study for Randomized Algorithms", booktitle = "Workshop on Algorithm Engineering", year = 2000, series = "LNCS", number = 1982, pages = "135--146", } @InProceedings{SanFle00www, author = "P. Sanders and R. Fleischer", pages = "135--146", title = "\htmladdnormallink{Asymptotic Complexity from Experiments? {A} Case Study for Randomized Algorithms}{wae00.ps.gz}", booktitle = "Workshop on Algorithm Engineering", year = 2000, number = 1982, publisher = "Springer {\copyright}", series = "{\htmladdnormallink{LNCS}{http://www.springer.de/comp/lncs/index.html}}", } @InProceedings{DemSan03www, author = "R. Dementiev and P. Sanders", title = "\htmladdnormallink{Asynchronous Parallel Disk Sorting}{asyncsort.ps.gz}", booktitle = "15th ACM Symposium on Parallelism in Algorithms and Architectures", year = 2003, pages = "138--148", address = "San Diego", } @InProceedings{DemSan03, author = "R. Dementiev and P. Sanders", title = "Asynchronous Parallel Disk Sorting", booktitle = "15th ACM Symposium on Parallelism in Algorithms and Architectures", pages = "138--148", year = 2003, address = "San Diego", } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Ich @Article{BecBelSan88, author = "B. Beckert and A. Bell and P. Sanders", title = "Gedichtgenerator --- {E}in {A}nwendungsbeispiel f{\"u}r nat{\"u}rlichsprachliche {T}exterzeugung", journal = "Junge Wissenschaft", year = 1988, volume = 3, number = 10, pages = "28--37" } @Manual{San88, title = "Benutzerhandbuch: Easy-{GEM} Library", organization = "Omikron Software", year = 1988 } @InCollection{BecBelSan90, author = "B. Beckert and A. Bell and P. Sanders", title = "Gedichtgenerator --- {E}in {A}nwendungsbeispiel f{\"u}r nat{\"u}rlichsprachliche {T}exterzeugung", booktitle = "Aus Neugier wird Wissenschaft -- Illustrierte Teilnehmerbeitr{\"a}ge aus 25 Jahren Jugend forscht", publisher = "Elektor Verlag", year = 1990 } @InCollection{BBS8890e, author = "B. Beckert and A. Bell and P. Sanders", title = "Gedichtgenerator --- {E}in {A}nwendungsbeispiel f{\"u}r nat{\"u}rlichsprachliche {T}exterzeugung", booktitle = "Aus Neugier wird Wissenschaft -- Illustrierte Teilnehmerbeitr{\"a}ge aus 25 Jahren Jugend forscht", publisher = "Elektor Verlag", note = "also in {\em Junge Wissenschaft}, 3(10):28--37, 1988", year = 1990 } @InCollection{BBS8890, author = "B. Beckert and A. Bell and P. Sanders", title = "Gedichtgenerator --- {E}in {A}nwendungsbeispiel f{\"u}r nat{\"u}rlichsprachliche {T}exterzeugung", booktitle = "Aus Neugier wird Wissenschaft -- Illustrierte Teilnehmerbeitr{\"a}ge aus 25 Jahren Jugend forscht", publisher = "Elektor Verlag", note = "auch in {\em Junge Wissenschaft}, 3(10):28--37, 1988", year = 1990 } @InCollection{San90, author = "P. Sanders", title = "Mr.\ {L}ine lernt {S}chreiben --- {G}rafiktexte mit {{\tt TXTGRA}}", booktitle = "Die Grafik-Connection", publisher = "Heim Verlag", year = 1990, editor = "S. Egner and M. Sperber", pages = "131--154" } @InProceedings{San93b, author = "P. Sanders", title = "A Case Study in Object Oriented Programming: Algebraic Data Structures in {E}iffel", editor = "R. Ege and M. Singh and B. Meyer", number = 11, series = "TOOLS", pages = "379--388", booktitle = "Technology of Object-Oriented Languages and Systems", year = 1993, publisher = "Prentice Hall", address = "Santa Barbara" } @Unpublished{San91, author = "P. Sanders", title = "Unifikation im typisierten {$\lambda$-Kalk\"ul --- Objektorientierte Implementation und Erweiterung um AC-Unifikation und Polymorphismus}", note = "Studienarbeit am FZI-Karlsruhe bei Prof. G. Goos und F. Weber", year = 1991 } @InProceedings{San93bwww, author = "P. Sanders", title = "{\htmladdnormallink{A Case Study in Object Oriented Programming: Algebraic Data Structures in {E}iffel}{algebra.ps.gz}}", editor = "R. Ege and M. Singh and B. Meyer", number = 11, series = "TOOLS", pages = "379--388", booktitle = "Technology of Object-Oriented Languages and Systems", year = 1993, publisher = "Prentice Hall", address = "Santa Barbara" } @MastersThesis{San93amix, author = "P. Sanders", title = "{S}uchalgorithmen auf {SIMD}-{R}echnern -- {W}eitere {E}rgebnisse zu {P}olyautomaten", school = "University of Karlsruhe", type = "Diplomarbeit", year = 1993, month = "August" } @MastersThesis{San93ae, author = "P. Sanders", title = "{S}uchalgorithmen auf {SIMD}-{R}echnern -- {W}eitere {E}rgebnisse zu {P}olyautomaten", school = "University of Karlsruhe", year = 1993, month = "August" } @MastersThesis{San93a, author = "P. Sanders", title = "{S}uchalgorithmen auf {SIMD}-{R}echnern -- {W}eitere {E}rgebnisse zu {P}olyautomaten", school = "Universit{\"a}t Karlsruhe", type = "Diplomarbeit", year = 1993, month = "August" } @MastersThesis{San93awww, author = "P. Sanders", title = "{\htmladdnormallink{{S}uchalgorithmen auf {SIMD}-{R}echnern -- {W}eitere {E}rgebnisse zu {P}olyautomaten}{da.ps.gz}}", school = "Universit{\"a}t Karlsruhe", type = "Diplomarbeit", year = 1993, month = "August" } @InProceedings{San94awww, author = "P. Sanders", title = "{\htmladdnormallink{Emulating {MIMD} behavior on {SIMD} machines}{delft.ps.gz}}", booktitle = "International Conference Massively Parallel Processing Applications and Development", address = "Delft", pages = "313--321", year = 1994, publisher = "Elsevier" } @InProceedings{San94a, author = "P. Sanders", title = "Emulating {MIMD} behavior on {SIMD} machines", booktitle = "International Conference Massively Parallel Processing Applications and Development", address = "Delft", pages = "313--321", year = 1994, publisher = "Elsevier" } @InProceedings{San94b, author = "P. Sanders", title = "Portable {p}arallele {B}aumsuchverfahren: {E}ntwurf {e}iner {e}ffizienten {B}ibliothek", booktitle = "Parallelrechner Anwender Treffen (TAT)", pages = "168--177", year = 1994, address = "Aachen", publisher = "IOS Press" } @InProceedings{San94bwww, author = "P. Sanders", title = "{\htmladdnormallink{Portable {p}arallele {B}aumsuchverfahren: {E}ntwurf {e}iner {e}ffizienten {B}ibliothek}{tat.ps.gz}}", booktitle = "Transputer Anwender Treffen", pages = "168--177", year = 1994, address = "Aachen", publisher = "IOS Press" } @InProceedings{San94c, author = "P. Sanders", title = "Massively Parallel Search for Transition-Tables of Polyautomata", booktitle = "Parcella 94, VI. International Workshop on Parallel Proccessing by Cellular Automata and Arrays", pages = "99--108", year = 1994, address = "Potsdam" } @InProceedings{San94cwww, author = "P. Sanders", title = "{\htmladdnormallink{Massively Parallel Search for Transition-Tables of Polyautomata}{parcella94.ps.gz}}", booktitle = "Parcella 94, VI. International Workshop on Parallel Proccessing by Cellular Automata and Array", pages = "99--108", year = 1994, address = "Potsdam" } @InProceedings{San94cs, author = "P. Sanders", title = "Massively Parallel Search for Transition-Tables of Polyautomata", booktitle = "VI. International Workshop on Parallel Proccessing by Cellular Automata and Arrays", year = 1994, } @InProceedings{San94cswww, author = "P. Sanders", title = "{\htmladdnormallink{Massively Parallel Search for Transition-Tables of Polyautomata}{parcella94.ps.gz}}", booktitle = "VI. International Workshop on Parallel Proccessing by Cellular Automata and Arrays", year = 1994, } @Article{Fly66, author = "M. Flynn", year = "1966", title = "Very High Speed Computing", journal = "Proceedings of the IEEE", pages = "1901--1909", kwds = "prll, simd, mimd, sisd", } @TechReport{San94d, author = "P. Sanders", title = "Analysis of Random Polling Dynamic Load Balancing", institution = "Universit{\"a}t Karlsruhe, Fakult{\"a}t f{\"u}r Informatik", year = 1994, number = "IB 12/94", month = "April" } @Article{Alo03, author = "N. Alon", title = "A simple algorithm for edge-coloring bipartite multigraphs", journal = "Information Processing Letters", year = 2003, volume = 85, pages = "301--302" } @TechReport{NAlon87, author = "N. Alon and B. Schieber", title = "Optimal preprocessing for answering on-line product queries", institution = "Tel Aviv University", year = 1987, number = "TR 71/87" } @TechReport{San94dwww, author = "P. Sanders", title = "{\htmladdnormallink{Analysis of Random Polling Dynamic Load Balancing}{trrp.ps.gz}}", institution = "Universit{\"a}t Karlsruhe, Fakult{\"a}t f{\"u}r Informatik", year = 1994, number = "IB 12/94", month = "April" } @InProceedings{San94e, author = "P. Sanders", title = "Flaschenhalsfreie parallele {P}riority queues", number = 13, series = "PARS Mitteilungen", booktitle = "PARS Workshop, Potsdam", pages = "10--19", month = "September", year = "1994" } @InProceedings{San94ewww, author = "P. Sanders", title = "{\htmladdnormallink{Flaschenhalsfreie parallele {P}riority queues}{pars94.ps.gz}}", number = 13, series = "PARS Mitteilungen", booktitle = "PARS Workshop, Potsdam", pages = "10--19", month = "September", year = "1994", note = "Improved results in Irregular'95 and JPDC" } @InProceedings{San94f, author = "P. Sanders", title = "Randomized static load balancing for tree shaped computations", series = "TR Universit{\"a}t Clausthal", pages = "58--69", issn = "0943-3805", note = "ISSN 0943-3805", booktitle = "Workshop on Parallel Processing", year = "1994", address = "Lessach, {\"O}sterreich" } @InProceedings{San94fwww, author = "P. Sanders", title = "{\htmladdnormallink{Randomized static load balancing for tree shaped computations}{lessach.ps.gz}}", series = "TR Universit{\"a}t Clausthal", pages = "58--69", issn = "0943-3805", note = "ISSN 0943-3805", booktitle = "Workshop on Parallel Processing", year = "1994", address = "Lessach, {\"O}sterreich" } @InProceedings{San94fjb, author = "P. Sanders", title = "Randomized static load balancing for tree shaped computations", editor = "K. Ecker and J. Aspel", number = "95/1", series = "Informatik-Bericht", pages = "58--69", issn = "0943-3805", OPTbooktitle = "Workshop {\"u}ber Parallelverarbeitung", year = 1995, OPTpublisher = "Universit{\"a}t Clausthal", OPTaddress = "Lessach, {\"O}sterreich", month = "September 1994" } @InProceedings{San94fe, author = "P. Sanders", title = "Randomized static load balancing for tree shaped computations", series = "TR University of Clausthal", number = "95/1", issn = "0943-3805", booktitle = "Workshop on Parallel Processing", year = 1994, address = "Lessach, Austria" } @InProceedings{San94g, author = "P. Sanders", title = "A Detailed Analysis of Random Polling Dynamic Load Balancing", booktitle = "International Symposium on Parallel Architectures, Algorithms and Networks", year = 1994, pages = "382--389", address = "Kanazawa, Japan", publisher = "IEEE, Los Alamitos, CA" } @InProceedings{San94gwww, author = "P. Sanders", title = "{\htmladdnormallink{A Detailed Analysis of Random Polling Dynamic Load Balancing}{ispan.ps.gz}}", booktitle = "International Symposium on Parallel Architectures, Algorithms and Networks", year = 1994, pages = "382--389", address = "Kanazawa, Japan" } @Unpublished{San94he, author = "P. Sanders", title = "Efficient emulation of {MIMD} behavior on {SIMD} machines", note = "submitted for publication", year = 1994, month = "August" } @TechReport{San95e, author = "P. Sanders", title = "Efficient emulation of {MIMD} behavior on {SIMD} machines", institution = "Universit{\"a}t Karlsruhe, Fakult{\"a}t f{\"u}r Informatik", year = 1995, number = "IB 29/95" } @TechReport{San95ee, author = "P. Sanders", title = "Efficient emulation of {MIMD} behavior on {SIMD} machines", institution = "University of Karlsruhe, Department of Computer Science", year = 1995, number = "IB 29/95" } @TechReport{San95a, author = "P. Sanders", title = "Towards Better Algorithms for Parallel Backtracking", institution = "Universit{\"a}t Karlsruhe, Fakult{\"a}t f{\"u}r Informatik", year = 1995, number = "IB 6/95", month = "Jan" } @InProceedings{San95b, author = "P. Sanders", title = "Better Algorithms for Parallel Backtracking", series = "LNCS", number = "980", pages = "333--347", booktitle = "Workshop on Algorithms for Irregularly Structured Problems", year = 1995, publisher = "Springer-Verlag Berlin", address = "Lyon, France, 4--6 September" } @InProceedings{San95bwww, author = "P. Sanders", title = "{\htmladdnormallink{Better Algorithms for Parallel Backtracking}{shuffleeabs.ps.gz}}", series = "{\htmladdnormallink{LNCS}{http://www.springer.de/comp/lncs/index.html}}", number = "980", pages = "333--347", booktitle = "Workshop on Algorithms for Irregularly Structured Problems", year = 1995, publisher = "Springer {\copyright}", address = "Lyon", note = "{\htmladdnormallink{Extended version}{shufflefull.ps.gz}}" } @InProceedings{San95bs, author = "P. Sanders", title = "Better Algorithms for Parallel Backtracking", series = "LNCS", number = "980", pages = "333--347", booktitle = "Workshop on Algorithms for Irregularly Structured Problems", year = 1995 } @InProceedings{San95cwww, author = "P. Sanders", title = "Fast Priority Queues for Parallel Branch-and-Bound", series = "{\htmladdnormallink{LNCS}{http://www.springer.de/comp/lncs/index.html}}", number = "980", pages = "379--393", booktitle = "Workshop on Algorithms for Irregularly Structured Problems", year = 1995, publisher = "Springer {\copyright}", address = "Lyon", note = "Improved version in JPDC, {\htmladdnormallink{extended version}{http://www.mpi-sb.mpg.de/{\%7e}anders/papers/1997-7.ps.gz}}" } @InProceedings{San95c, author = "P. Sanders", title = "Fast Priority Queues for Parallel Branch-and-Bound", series = "LNCS", number = "980", pages = "379--393", booktitle = "Workshop on Algorithms for Irregularly Structured Problems", year = 1995, publisher = "Springer", address = "Lyon" } @InProceedings{HopSan95, author = "H. Hopp and P. Sanders", title = "Parallel Game Tree Search on {SIMD} Machines", series = "LNCS", number = "980", pages = "349--361", booktitle = "Workshop on Algorithms for Irregularly Structured Problems", year = 1995, publisher = "Springer", address = "Lyon" } @InProceedings{HopSan95www, author = "H. Hopp and P. Sanders", title = "{\htmladdnormallink{Parallel Game Tree Search on {SIMD} Machines}{gamet.ps.gz}}", series = "{\htmladdnormallink{LNCS}{http://www.springer.de/comp/lncs/index.html}}", number = "980", pages = "349--361", booktitle = "Workshop on Algorithms for Irregularly Structured Problems", year = 1995, publisher = "Springer {\copyright}", address = "Lyon", note = "{\htmladdnormallink{Holger Hopp's Diploma thesis}{http://wwwipd.ira.uka.de/{\%7e}hopp/gts/dipl.ps.gz}} (in German), University of Karlsruhe, 1995. " } @Unpublished{San95d, author = "P. Sanders", title = "A Scalable Parallel Tree Search Library", note = "SuParCup '95", year = 1995 } @TechReport{San95f, author = "P. Sanders", title = "Some Implementation Results on Random Polling Dynamic Load Balancing", institution = "Universit{\"a}t Karlsruhe, Fakult{\"a}t f{\"u}r Informatik", year = 1995, number = "40/95", month = "August" } @InProceedings{San96a, author = "P. Sanders", title = "On the Competitive Analysis of Randomized Static Load Balancing", booktitle = "First Workshop on Randomized Parallel Algorithms", editor = "S. Rajasekaran", year = 1996, address = "Honolulu, Hawaii, 16 April" } @InProceedings{San96awww, author = "P. Sanders", title = "{\htmladdnormallink{On the Competitive Analysis of Randomized Static Load Balancing}{rand96.ps.gz}}", booktitle = "First Workshop on Randomized Parallel Algorithms", editor = "S. Rajasekaran", year = 1996, address = "Honolulu, Hawaii, 16 April" } @InProceedings{San96ahab, author = "P. Sanders", title = "On the Competitive Analysis of Randomized Static Load Balancing", booktitle = "First Workshop on Randomized Parallel Algorithms", editor = "S. Rajasekaran", year = 1996, address = "Honolulu, Hawaii, 16 April", note = "{\url{http://www.mpi-sb.mpg.de/~sanders/papers/rand96.ps.gz}}" } @InProceedings{San96b, author = "P. Sanders", title = "A Scalable Parallel Tree Search Library", booktitle = "2nd Workshop on Solving Irregular Problems on Distributed Memory Machines", year = 1996, note = "{\url{http://www.mpi-sb.mpg.de/~sanders/papers/irreg96.ps.gz}}", editor = "S. Ranka", address = "Honolulu, Hawaii, 16 April" } @InProceedings{San96bwww, author = "P. Sanders", title = "{\htmladdnormallink{A Scalable Parallel Tree Search Library}{irreg96.ps.gz}}", booktitle = "2nd Workshop on Solving Irregular Problems on Distributed Memory Machines", year = 1996, editor = "S. Ranka", address = "Honolulu, Hawaii" } @InProceedings{San96bhab, author = "P. Sanders", title = "{\htmladdnormallink{A Scalable Parallel Tree Search Library}{irreg96.ps.gz}}", booktitle = "2nd Workshop on Solving Irregular Problems on Distributed Memory Machines", year = 1996, editor = "S. Ranka", address = "Honolulu, Hawaii", note = "{\url{http://www.mpi-sb.mpg.de/~sanders/papers/irreg96.ps.gz}}" } @Article{DGKS96, author = "O. Devillers and M. Golin and K. Kedem and S. Schirra", title = "Queries on {V}oronoi Diagrams of Moving Points", journal = "Computational Geometry: Theory and Applications", year = 1996, volume = 6, pages = "315--327" } @Article{San00aboth, author = "P. Sanders", title = "Asynchronous Scheduling of Redundant Disk Arrays", journal = "IEEE Transactions on Computers", year = 2003, volume = 52, number = 9, pages = "1170--1184", note = "short version in 12th ACM Symposium on Parallel Algorithms and Architectures, pages 89--98, 2000" } @Article{San02a, author = "P. Sanders", title = "Asynchronous Scheduling of Redundant Disk Arrays", journal = "IEEE Transactions on Computers", year = 2003, volume = 52, number = 9, pages = "1170--1184", } @InProceedings{SET03www, author = "P. Sanders and S. Egner and L. Tolhuizen", title = "\htmladdnormallink{Polynomial Time Algorithms For Network Information Flow}{infoflow.ps.gz}", booktitle = "15th ACM Symposium on Parallel Algorithms and Architectures", year = 2003, pages = "286--294", } @InProceedings{SET03, author = "P. Sanders and S. Egner and L. Tolhuizen", title = "Polynomial Time Algorithms For Network Information Flow", booktitle = "15th ACM Symposium on Parallel Algorithms and Architectures", pages = "286--294", year = 2003, } @Unpublished{SET02www, author = "P. Sanders and S. Egner and L. Tolhuizen", title = "{\htmladdnormallink{Polynomial Time Algorithms For Network Information Flow}{incremental.ps}}", note = " ", month = "October", year = 2002 } @TechReport{KST02www, author = "I. Katriel and P. Sanders and J. L. Tr{\"a}ff", title = "{\htmladdnormallink{A Practical Minimum Spanning Tree Algorithm Using the Cycle Property}{primfilterTR.ps.gz}}", institution = "MPI Informatik, Germany", year = 2002, number = "MPI-I-2002-1-003", month = "October" } @TechReport{DemSan03a, author = "R. Dementiev and P. Sanders", title = "Asynchronous Parallel Disk Sorting", institution = "MPI Informatik, Germany", year = 2003, number = "MPI-I-2003-1-001" } @TechReport{KST02, author = "I. Katriel and P. Sanders and J. L. Tr{\"a}ff", title = "A Practical Minimum Spanning Tree Algorithm Using the Cycle Property", institution = "MPI Informatik, Germany", year = 2002, number = "MPI-I-2002-1-003", month = "October" } @InProceedings{KST03, author = "I. Katriel and P. Sanders and J. L. Tr{\"a}ff", title = "A Practical Minimum Spanning Tree Algorithm Using the Cycle Property", booktitle = "11th European Symposium on Algorithms (ESA)", year = 2003, publisher = "Springer", pages = "679--690", series = "LNCS", number = "2832" } @InProceedings{KST03www, author = "I. Katriel and P. Sanders and J. L. Tr{\"a}ff", title = "{\htmladdnormallink{A Practical Minimum Spanning Tree Algorithm Using the Cycle Property}{filter.ps.gz}}", booktitle = "11th European Symposium on Algorithms (ESA)", year = 2003, pages = "679--690", publisher = "Springer", series = "LNCS", number = "2832" } @TechReport{DGKS94, author = "O. Devillers and M. Golin and K. Kedem and S. Schirra", year = "1994", title = "Revenge of the Dog: Queries on {V}oronoi Diagrams of Moving Points", type = "Technical Report", number = "MPI-I-94-149", url = "ftp://ftp.mpi-sb.mpg.de/pub/papers/reports/MPI-I-94-149.ps.gz", institution = "Max-Planck-Institut f{\"u}r Informatik", address = "Saarbr{\"u}cken", annote = "submitted to Comp.Geom.:Theory and Appl.", abstract = "Suppose we are given $n$ moving postmen described by their motion equations $p_i(t) = s_i + v_it,$ $i=1,\ldots, n$, where $s_i \in \R^2$ is the position of the $i$'th postman at time $t=0$, and $v_i \in \R^2$ is his velocity . The problem we address is how to preprocess the postmen data so as to be able to efficiently answer two types of nearest neighbor queries. The first one asks ``who is the nearest postman at time $t_q$ to a dog located at point $s_q$. In the second type a fast query dog is located a point $s_q$ at time $t_q$, its velocity is $v_q$ where $v_q>|v_i|$ for all $i=1, \ldots , n$, and we want to know which postman the dog can catch first. We present two solutions to these problems. Both solutions use deterministic data structures.", } @Unpublished{San96cf, author = {P. Sanders}, title = {On the efficiency of nearest neighbor load balancing for random loads (extended version)}, note = {{\tt http://liinwww.ira.uka.de/$\sim$sanders/}}, year = 1996 } @InProceedings{San96c, author = "P. Sanders", title = "On the Efficiency of Nearest Neighbor Load Balancing for Random Loads", booktitle = "Parcella 96, VII. International Workshop on Parallel Proccessing by Cellular Automata and Arrays", year = 1996, pages = "120--127", publisher = "Akademie Verlag", address = "Berlin" } @InProceedings{San96cwww, author = "P. Sanders", title = "On the Efficiency of Nearest Neighbor Load Balancing for Random Loads", booktitle = "Parcella 96, VII. International Workshop on Parallel Proccessing by Cellular Automata and Arrays", year = 1996, pages = "120--127", publisher = "Akademie Verlag", address = "Berlin", note = "{\htmladdnormallink{Extended version}{diffuse.ps.gz}}" } @Unpublished{San96df, author = {P. Sanders}, title = {Optimizing the emulation of {MIMD} behavior on {SIMD} machines (extended version)}, note = {{\tt http://liinwww.ira.uka.de/$\sim$sanders/}}, year = 1996 } @InProceedings{San96d, author = "P. Sanders", title = "Optimizing the Emulation of {MIMD} Behavior on {SIMD} Machines", booktitle = "Parcella 96, VII. International Workshop on Parallel Proccessing by Cellular Automata and Arrays", year = 1996, publisher = "Akademie Verlag", address = "Berlin" } @InProceedings{San96dwww, author = "P. Sanders", title = "Optimizing the Emulation of {MIMD} Behavior on {SIMD} Machines", booktitle = "Parcella 96, VII. International Workshop on Parallel Proccessing by Cellular Automata and Arrays", year = 1996, publisher = "Akademie Verlag", address = "Berlin", note = "{\htmladdnormallink{Extended version}{simdp96.ps.gz}}" } @PhdThesis{San96ee, author = "P. Sanders", title = "Lastverteilungsalgorithmen f{\"u}r parallele Tiefensuche", school = "University of Karlsruhe", year = 1996 } @PhdThesis{San96e, author = "P. Sanders", title = "Lastverteilungsalgorithmen f{\"u}r parallele Tiefensuche", type = "Dissertation", school = "Universit{\"a}t Karlsruhe", year = 1996 } @Article{MehSan03, author = "K. Mehlhorn and P. Sanders", title = "Scanning Multiple Sequences Via Cache Memory", journal = "Algorithmica", year = 2003, volume = 35, number = 1, pages = "75--93", } @Book{San97a, author = "P. Sanders", title = "Load Balancing Algorithms for Parallel Depth First Search (In German: Lastverteilungsalgorithmen f{\"u}r parallele Tiefensuche)", publisher = "VDI Verlag, Berlin", isbn = "3-18-346310-5", year = 1997, number = 463, series = "Fortschrittsberichte, Reihe 10", } @PhdThesis{San97a-phd, author = "P. Sanders", title = "Lastverteilungsalgorithmen f{\"u}r parallele Tiefensuche", school = "University of Karlsruhe", year = 1997 } @TechReport{San97b, author = "P. Sanders", title = "Randomized Priority Queues for Fast Parallel Access", institution = "Universit{\"a}t Karlsruhe, Fakult{\"a}t f{\"u}r Informatik", year = "1997", number = "IB 7/97", } @TechReport{NieSan96, author = "R. Niedermeier and P. Sanders", title = "On the {M}anhattan-Distance Between Points on Space-Filling Mesh-Indexings", institution = "Universit{\"a}t Karlsruhe, Fakult{\"a}t f{\"u}r Informatik", year = 1996, number = "IB 18/96" } @TechReport{NieSan96e, author = "R. Niedermeier and P. Sanders", title = "On the {M}anhattan-Distance Between Points on Space-Filling Mesh-Indexings", institution = "University of Karlsruhe, Department of Computer Science", year = 1996, number = "IB 18/96" } @Article{NieReiSan02, author = "R. Niedermeier and K. Reinhard and P. Sanders", title = "Towards Optimal Locality in Mesh-Indexings", journal = "Discrete Applied Mathematics", volume = 117, pages = "211--237", month = "march", year = 2002, } @InProceedings{NieReiSan97, author = "R. Niedermeier and K. Reinhard and P. Sanders", title = "Towards Optimal Locality in Mesh-Indexings", booktitle = "Fundamentals of Computation Theory", editor = "B. S. Chlebus and L. Czaja", number = "1279", series = "LNCS", year = 1997, address = "Krakow", pages = "364--375" } @TechReport{NieReiSan97a, author = "R. Niedermeier and K. Reinhard and P. Sanders", title = "Towards Optimal Locality in Mesh-Indexings", institution = "University of Karlsruhe", year = 1997, number = "IB 12/97" } @InProceedings{SanSte05www, author = "P. Sanders and D. Steurer", title = "\htmladdnormallink{An Asymptotic Approximation Scheme for Multigraph Edge Coloring}{SanSte05.ps.gz}", booktitle = "16th ACM-SIAM Symposium on Discrete Algorithms", year = 2005 } @Unpublished{SS04www, author = "P. Sanders and D. Steurer", title = "\htmladdnormallink{An Asymptotic Approximation Scheme for Multigraph Edge Coloring}{edgecoloring.ps.gz}", note = "submitted for publication", month = "July", year = 2004 } @InProceedings{SanTra02www, author = "Sanders, Peter and Tr{\"a}ff, Jesper Larsson", title = "The Factor Algorithm for Regular All-to-all Communication on Clusters of {SMP} Nodes", booktitle = "8th Europar", publisher = "Springer {\copyright}", number = 2400, pages = "799--803", year = 2002, series = "{\htmladdnormallink{LNCS}{http://www.springer.de/comp/lncs/index}}", note = "{\htmladdnormallink{full paper}{europar2.ps.gz}}" } @Article{RST01, author = "R. Reussner and P. Sanders and J. Tr{\"a}ff", title = "{SKaMPI}: A Comprehensive Benchmark for Public Benchmarking of {MPI}", journal = "Scientific Programming", year = 2001, volume = 10, number = 1, pages = "55--65", } @InProceedings{SanTra02, author = "Sanders, Peter and Tr{\"a}ff, Jesper Larsson", title = "The Factor Algorithm for regular All-to-all Communication on Clusters of {SMP} Nodes", booktitle = "8th Europar", year = 2002, series = "LNCS", number = 2400, pages = "799--803", publisher = "Springer", } @Article{NieReiSan00www, author = "R. Niedermeier and K. Reinhard and P. Sanders", title = "Towards Optimal Locality in Mesh-Indexings", journal = "Discrete Applied Mathematics", volume = 117, number = "1--3", pages = "211--237", year = 2002, } @Unpublished{NieReiSan97d, author = "R. Niedermeier and K. Reinhard and P. Sanders", title = "Towards Optimal Locality in Mesh-Indexings", year = 1996, note = "Zur Ver{\"o}ffentlichung eingereicht" } @Unpublished{San97x, author = "P. Sanders", title = "High Performance Computing Aspects of Airline Crew Scheduling Optimization", note = "working paper", year = 1997, month = "October", annote = "Abschlussaufschrieb in Goeteborg" } @InProceedings{NieReiSan97www, author = "R. Niedermeier and K. Reinhard and P. Sanders", title = "Towards Optimal Locality in Mesh-Indexings", booktitle = "Fundamentals of Computation Theory", editor = "B. S. Chlebus and L. Czaja", number = "1279", series = "{\htmladdnormallink{LNCS}{http://www.springer.de/comp/lncs/index.html}}", year = 1997, address = "Krakow", pages = "364--375", note = "{\htmladdnormallink{Extended version}{1997-12.ps.gz}} as Technical Report IB 12/97, University of Karlsruhe, 1997" } @Unpublished{NieReiSan98, author = "R. Niedermeier and K. Reinhard and P. Sanders", title = "Towards Optimal Locality in Mesh-Indexings", note = "{\url{http://www.mpi-sb.mpg.de/~sanders/papers/1997-12.ps.gz}}" } @InProceedings{SanHan97e, author = "P. Sanders and T. Hansch", title = "On the Efficient Implementation of Massively Parallel Quicksort", booktitle = "4th International Symposium on Solving Irregularly Structured Problems in Parallel", editor = "G. Bilardi and A. Ferreira and R. L{\"u}ling and J. Rolim", number = 1253, series = "LNCS", issn = "0302-9743", year = 1997, pages = "13--24", publisher = "Springer" } @InProceedings{SanHan97ewww, author = "P. Sanders and T. Hansch", title = "{\htmladdnormallink{On the Efficient Implementation of Massively Parallel Quicksort}{qsort.ps.gz}}", booktitle = "4th International Symposium on Solving Irregularly Structured Problems in Parallel", number = 1253, series = "{\htmladdnormallink{LNCS}{http://www.springer.de/comp/lncs/index.html}}", year = 1997, pages = "13--24", publisher = "Springer {\copyright}", note = "Thomas Hansch's {\htmladdnormallink{Diploma thesis}{Han97.ps.gz}} (in German), University of Karlsruhe, 1996. {\htmladdnormallink{Complete set of data sheets (English translation)}{Han97data.ps.gz}}" } @Unpublished{SanHan97d, author = "P. Sanders and T. Hansch", title = "On the Efficient Implementation of Massively Parallel Quicksort", note = "Zur Ver{\"o}ffentlichung eingereicht", year = 1996 } @InProceedings{SanWor95, author = "P. Sanders and T. Worsch", title = "Konvergente lokale {L}astverteilungsverfahren und ihre {M}odellierung durch {Z}ellularautomaten", number = 14, series = "PARS Mitteilungen", pages = "285--291", booktitle = "PARS Workshop", year = 1995 } @InProceedings{SanWor95www, author = "P. Sanders and T. Worsch", title = "{\htmladdnormallink{Konvergente lokale {L}astverteilungsverfahren und ihre {M}odellierung durch {Z}ellularautomaten}{pars95.ps.gz}}", number = 14, series = "PARS Mitteilungen", pages = "285--291", booktitle = "PARS Workshop", year = 1995 } @Unpublished{SanWor96, author = "P. Sanders and T. Worsch", title = "Praktikum nachrichtengekoppelte Parallelrechner mit MPI", note = "Praktikumsunterlagen, Universit{\"a}t Karlsruhe", year = 1996 } @Book{SanWor97, author = "P. Sanders and T. Worsch", title = "Parallele Programmierung mit MPI -- ein Praktikum", publisher = "Logos Verlag Berlin", year = 1997, note = "ISBN 3-931216-76-4" } @Book{SanWor97vorl, author = "P. Sanders and T. Worsch", title = "Parallele Programmierung mit MPI -- ein Praktikum", publisher = "Logos Verlag Berlin", year = 1997, note = "f{\"u}r Leute, die etwas zur Vorlesung programmieren m{\"o}chten" } @Book{SanWor97www, author = "P. Sanders and T. Worsch", title = "{\htmladdnormallink{Parallele Programmierung mit MPI -- ein Praktikum}{http://liinwww.ira.uka.de/mpibook/}}", publisher = "Logos Verlag Berlin", year = 1997, note = "ISBN 3-931216-76-4" } @TechReport{BSP97, author = "J. M. D. Hill et al.", title = "BSPlib: The BSP Programming Library", institution = "Oxford University Computing Laboratory", year = 1997, number = "PRG-TR-29-97", note = "{\url{http://www.BSP-Worldwide.org/implmnts/oxtool/}}" } @InProceedings{PUB99, author = "O. Bonorden and B. Juurlink and I. von Otte and I. Rieping", title = "The Paderborn University BSP (PUB) Library - Design, Implementation and Performance", booktitle = "IPPS/SPDP", year = 1999, note = "{\url{http://www.uni-paderborn.de/~pub/}}" } @InProceedings{RSPM98link, author = "R. Reussner and P. Sanders and L. Prechelt and M. M{\"u}ller", title = "{SKaMPI}: A Detailed, Accurate {MPI} Benchmark", number = "1497", series = "LNCS", pages = "52--59", booktitle = "EuroPVM/MPI see also {\url{http://liinwww.ira.uka.de/~skampi/}}", year = 1998 } @InProceedings{RSPM98, author = "R. Reussner and P. Sanders and L. Prechelt and M. M{\"u}ller", title = "{SKaMPI}: A Detailed, Accurate {MPI} Benchmark", number = "1497", series = "LNCS", pages = "52--59", booktitle = "EuroPVM/MPI", year = 1998 } @InProceedings{RSPM98www, author = "R. Reussner and P. Sanders and L. Prechelt and M. M{\"u}ller", title = "{\htmladdnormallink{SKaMPI: A Detailed, Accurate MPI Benchmark}{europvm-mpi98.ps.gz}}", number = "1497", series = "{\htmladdnormallink{LNCS}{http://www.springer.de/comp/lncs/index.html}}", pages = "52--59", booktitle = "EuroPVM/MPI", year = 1998, note = "\htmladdnormallink{(SKaMPI Home Page)}{http://wwwipd.ira.uka.de/{\%7e}skampi/}" } @Article{San98c, author = "P. Sanders", title = "Random Permutations on Distributed, External and Hierarchical Memory", volume = 67, number = 6, journal = "Information Processing Letters", pages = "305--310", year = 1998, } @Unpublished{Han95a, author = "T. Hansch", title = "Segmentierte kollektive {O}perationen auf {G}ittern mit {H}ilbertnumerierung", note = "Studienarbeit", year = 1995 } @Unpublished{Han96, author = "T. Hansch", title = "Sortieren gro{\ss}er {D}atenmengen auf {G}ittern mit {Q}uicksort", note = "Diplomarbeit", year = 1996 } @MastersThesis{Hop95, author = "H. Hopp", title = "Parallele {S}pielbaumsuche auf {SIMD}-{R}echnern", school = "Universit{\"a}t Karlsruhe", year = 1995, type = "Diplomarbeit" } @Manual{DieSan95, title = "PIGSel Manual", author = "P. Diefenbach and P. Sanders", organization = "Universit{\"a}t Karlsruhe, LIIN", year = 1995 } @MastersThesis{Die96e, author = "P. Diefenbach", title = "Lastverteilung mit {V}erdr{\"a}ngung in parallelen {S}pielbaumsuchverfahren auf {MIMD}-{R}echnern", school = "University of Karlsruhe", year = 1996, } @TechReport{SanVolWor97a, AUTHOR = "Peter Sanders and Roland Vollmar and Thomas Worsch", TITLE = "Feasible Models of Computation: Three-Dimensionality and Energy Consumption", INSTITUTION = "Universit{\"a}t Karlsruhe, Fakult{\"a}t f{\"u}r Informatik", YEAR = "1997", type = "Technical report", number = "2/97", } @InProceedings{SanVolWor97b, author = "Peter Sanders and Roland Vollmar and Thomas Worsch", title = "Feasible Models of Computation: Three-Dimensionality and Energy Consumption", editor = "C. Lengauer and M. Griebl and S. Gorlatch", number = 1300, series = "LNCS", pages = "384--388", booktitle = "Euro-Par", year = 1997, publisher = "Springer", address = "Passau" } @InProceedings{SanVolWor97bwww, author = "Peter Sanders and Roland Vollmar and Thomas Worsch", title = "Feasible Models of Computation: Three-Dimensionality and Energy Consumption", editor = "C. Lengauer and M. Griebl and S. Gorlatch", number = 1300, note = "{\htmladdnormallink{Extended version}{1997-2.ps.gz}} as Technical Report IB 2/97, University of Karlsruhe, 1997", series = "LNCS", pages = "384--388", booktitle = "Euro-Par", year = 1997, publisher = "Springer {\copyright}", address = "Passau" } @Article{SanVolWor00, author = "P. Sanders and R. Vollmar and T. Worsch", title = "Feasible Models of Computation: Three-Dimensionality and Energy Consumption", journal = "Fundamenta Informaticae", year = 2002, volume = 52, number = "1--3", pages = "233--248" } @InProceedings{SanVolWor97bfullurl, author = "Peter Sanders and Roland Vollmar and Thomas Worsch", title = "Feasible Models of Computation: Three-Dimensionality and Energy Consumption", editor = "C. Lengauer and M. Griebl and S. Gorlatch", number = 1300, note = "{\htmladdnormallink{Extended version}{http://www.mpi-sb.mpg.de/{\%7e}sanders/papers/1997-2.ps.gz}} as Technical Report IB 2/97, University of Karlsruhe, 1997", series = "LNCS", pages = "384--388", booktitle = "Euro-Par", year = 1997, publisher = "Springer {\copyright}", address = "Passau" } @Unpublished{San98d, author = "P. Sanders", title = "Randomized Receiver Initiated Load Balancing Algorithms for Tree Shaped Computations", year = 1998 } @Unpublished{San98dwww, author = "P. Sanders", title = "\htmladdnormallink{Randomized Receiver Initiated Load Balancing Algorithms for Tree Shaped Computations}{submit.ps.gz}", note = "submitted for publication", year = 1998 } @Unpublished{San98dsub, author = "P. Sanders", title = "Randomized Receiver Initiated Load Balancing Algorithms for Tree Shaped Computations", note = "{\url{http://www.mpi-sb.mpg.de/~sanders/papers/submit.ps.gz}}", year = 1998 } @Article{San98a, author = "P. Sanders", title = "Randomized Priority Queues for Fast Parallel Access", volume = 49, pages = "86--97", journal = "Journal Parallel and Distributed Computing, Special Issue on Parallel and Distributed Data Structures", year = 1998, } @Article{San98awww, author = "P. Sanders", title = "Randomized Priority Queues for Fast Parallel Access", volume = 49, pages = "86--97", journal = "Journal Parallel and Distributed Computing, Special Issue on Parallel and Distributed Data Structures", year = 1998, note = "{\htmladdnormallink{Extended version}{1997-7.ps.gz}}" } @Article{San98a-s, author = "P. Sanders", title = "Randomized Priority Queues for Fast Parallel Access", volume = 49, pages = "86--97", journal = "Journal Parallel and Distributed Computing", year = 1998, } @Article{San98a-e, author = "P. Sanders", title = "Randomized Priority Queues for Fast Parallel Access", journal = "Journal Parallel and Distributed Computing, Special Issue on Parallel and Distributed Data Structures", year = 1998, note = "to appear, extended version: \url{http://www.mpi-sb.mpg.de/~sanders/papers/1997-7.ps.gz}" } @TechReport{AKE00, author = "J. Aerts and J. Korst and S. Egner", title = "Random duplicate storage strategies for load balancing in multimedia servers", institution = "Philips Research Laboratories", year = 2000, number = "NL-MS 20.314" } @InProceedings{SanEgnKor00, author = "P. Sanders and S. Egner and J. Korst", title = "Fast Concurrent Access to Parallel Disks", booktitle = "11th ACM-SIAM Symposium on Discrete Algorithms", year = 2000, pages = "849--858", } @InProceedings{SGNG00, author = "S. W. Schlosser and J. L. Griffin and D. F. Nagle and G. R. Ganger", title = "Designing Computer Systems with {MEMS}-based Storage", booktitle = "9th International Conference on Architectural Support for Programming Languages and Operating Systems", pages = "1--12", note = "SIGPLAN Notices 35(11)", year = 2000, annote = "propesed to go between main memory and disks" } @Unpublished{San00c, author = "P. Sanders", title = "Asynchronous Scheduling of Redundant Disk Arrays", note = "{\url{http://www.mpi-sb.mpg.de/~sanders/papers/spaa00-full.ps.gz}}" } @InProceedings{San00aalcom, author = "P. Sanders", title = "Asynchronous Scheduling of Redundant Disk Arrays", booktitle = "12th ACM Symposium on Parallel Algorithms and Architectures", year = 2000, note = "also report ALCOMFT-TR-01-99", pages = "89--98", } @InProceedings{San00awww, author = "P. Sanders", title = "\htmladdnormallink{Asynchronous Scheduling of Redundant Disk Arrays}{asyncpardisk.ps.gz}", booktitle = "12th ACM Symposium on Parallel Algorithms and Architectures", year = 2000, pages = "89--98", } @InProceedings{San00a, author = "P. Sanders", title = "Asynchronous Scheduling of Redundant Disk Arrays", booktitle = "12th ACM Symposium on Parallel Algorithms and Architectures", year = 2000, pages = "89--98", } @Unpublished{SanEgnKor00b, author = "P. Sanders and S. Egner and J. Korst", title = "Fast Concurrent Access to Parallel Disks", note = "{\url{http://www.mpi-sb.mpg.de/~sanders/papers/full-pardisk.ps.gz}}" } @InProceedings{SanEgnKor00www, author = "P. Sanders and S. Egner and J. Korst", title = "\htmladdnormallink{Fast Concurrent Access to Parallel Disks}{soda00.ps.gz}", booktitle = "11th ACM-SIAM Symposium on Discrete Algorithms", pages = "849--858", year = 2000, note = "{\htmladdnormallink{full paper}{full-pardisk.ps.gz}}" } @Unpublished{SanSib00a, author = "P. Sanders and J. Sibeyn", title = "A Bandwidth Latency Tradeoff for Broadcast and Reduction", note = "{\url{http://www.mpi-sb.mpg.de/~sanders/papers/ipl.ps.gz}}", year = 2000 } @InProceedings{SanSib00, author = "P. Sanders and J. Sibeyn", title = "A Bandwidth Latency Tradeoff for Broadcast and Reduction", booktitle = "6th Euro-Par", number = 1900, series = "LNCS", pages = "918--926", year = 2000, } @Article{SanSib02, author = "P. Sanders and J. Sibeyn", title = "A Bandwidth Latency Tradeoff for Broadcast and Reduction", journal = "Information Processing Letters", year = 2003, volume = 86, pages = "33--38", number = 1, } @InProceedings{SanSib00www, author = "P. Sanders and J. Sibeyn", title = "{\htmladdnormallink{A Bandwidth Latency Tradeoff for Broadcast and Reduction}{bcast.ps.gz}}", series = "{\htmladdnormallink{LNCS}{http://www.springer.de/comp/lncs/index.html}}", publisher = "Springer {\copyright}", booktitle = "6th Euro-Par", number = 1900, pages = "918--926", year = 2000, } @InProceedings{MeySan00www, author = "U. Meyer and P. Sanders", title = "{\htmladdnormallink{Parallel Shortest Path for Arbitrary Graphs}{spath00.ps.gz}}", series = "{\htmladdnormallink{LNCS}{http://www.springer.de/comp/lncs/index.html}}", publisher = "Springer {\copyright}", booktitle = "6th Euro-Par", number = 1900, pages = "461--470", year = 2000, } @InProceedings{MeySan00, author = "U. Meyer and P. Sanders", title = "Parallel Shortest Path for Arbitrary Graphs", booktitle = "6th Euro-Par", series = "LNCS", number = 1900, pages = "461--470", year = 2000, } @Unpublished{SanSol00a, author = "P. Sanders and R. Solis-Oba", title = "How Helpers Hasten $h$-Relations", note = "{\url{http://www.mpi-sb.mpg.de/~sanders/papers/allall9.ps.gz}}" } @Article{SanSol01, author = "P. Sanders and R. Solis-Oba", title = "How Helpers Hasten $h$-Relations", journal = "Journal of Algorithms", year = 2001, volume = 41, pages = "86--98", } @InProceedings{SanSol00, author = "P. Sanders and R. Solis-Oba", title = "How Helpers Hasten $h$-Relations", booktitle = "8th European Symposium on Algorithms (ESA)", publisher = "Springer {\copyright}", series = "LNCS", year = 2000, number = 1879, pages = "392--402", } @InProceedings{SanSol00www, author = "P. Sanders and R. Solis-Oba", title = "\htmladdnormallink{How Helpers Hasten $h$-Relations}{esa00.ps.gz}", booktitle = "8th European Symposium on Algorithms (ESA)", series = "{\htmladdnormallink{LNCS}{http://www.springer.de/comp/lncs/index.html}}", year = 2000, number = 1879, pages = "392--402", note = "{\htmladdnormallink{final paper}{allall10.ps.gz}}" } @Article{San01c, author = "P. Sanders", title = "Reconciling Simplicity and Realism in Parallel Disk Models", journal = "Parallel Computing", year = 2002, volume = 28, number = 5, pages = "705--723", note = "Special Issue on Parallel Data Intensive Algorithms and Applications" } @Article{San01cboth, author = "P. Sanders", title = "Reconciling Simplicity and Realism in Parallel Disk Models", journal = "Parallel Computing", year = 2002, volume = 28, number = 5, pages = "705--723", note = "short version in 12th SODA, p. 67--76, 2001." } @TechReport{SanSol01a, author = "P. Sanders and R. Solis-Oba", title = "How helpers hasten $h$-relations", institution = "The University of Western Ontario, Department of Computer Science", year = 2001, number = "559", month = "March" } @InProceedings{FMS03, author = "S. Funke and D. Matijevic and P. Sanders", title = "Approximating Energy Efficient Paths in Multi-Hop Networks", booktitle = "11th European Symposium on Algorithms (ESA)", year = 2003, publisher = "Springer", series = "LNCS", number = "2832" } @InProceedings{FMS03www, author = "S. Funke and D. Matijevic and P. Sanders", title = "{\htmladdnormallink{Approximating Energy Efficient Paths in Multi-Hop Networks}{http://www.mpi-sb.mpg.de/~funke/RadioESA03long.ps.gz}}", booktitle = "11th European Symposium on Algorithms (ESA)", year = 2003, publisher = "Springer", series = "LNCS", number = "2832" } @InProceedings{BSS02, author = "R. Beier and P. Sanders and N. Sivadasan", title = "Energy Optimal Routing in Radio Networks Using Geometric Data Structures", booktitle = "29th International Colloquium on Automata, Languages and Programming", year = 2002, publisher = "Springer", number = 2380, pages = "366--376", } @InProceedings{BSS02www, author = "R. Beier and P. Sanders and N. Sivadasan", title = "{\htmladdnormallink{Energy Optimal Routing in Radio Networks Using Geometric Data Structures}{icalp02.ps.gz}}", booktitle = "29th International Colloquium on Automata, Languages and Programming", series = "{\htmladdnormallink{LNCS}{http://www.springer.de/comp/lncs/index}}", number = 2380, pages = "366--376", publisher = "Springer {\copyright}", year = 2002, } @Article{San00bwww, author = "P. Sanders", title = "{\htmladdnormallink{Fast Priority Queues for Cached Memory}{http://www.mpi-sb.mpg.de/{\%7e}sanders/papers/spqjea.ps.gz}}", journal = "ACM Journal of ExperimentalAlgorithmics", volume = 5, year = 2000, } @InProceedings{SanVoe02www, author = "P. Sanders and B. V{\"o}cking", title = "{\htmladdnormallink{Random Arc Allocation and Applications to Disks, Drums and DRAMs}{swat02.ps.gz}}", booktitle = "8th Scandinavian Workshop on Algorithm Theory", series = "{\htmladdnormallink{LNCS}{http://www.springer.de/comp/lncs/index}}", publisher = "Springer {\copyright}", number = 2368, pages = "121--130", year = 2002, note = "{\htmladdnormallink{full paper}{swat02full.ps.gz}}" } @PhdThesis{Ric94, author = "Ivan L. M. Ricarte", school = "University of Maryland College Park", title = "Performance and Scalability of Parallel Database Systems", year = "1994", abstract-url = "http://www.dca.fee.unicamp.br/~ricarte/Papers/papers.html#phddiss", address = "College Park, MD, USA", url = "ftp://ftp.dca.fee.unicamp.br/pub/docs/ricarte/papers/phddiss.ps.gz", keywords = "Parallel processing, relational databases, parallel external sorting, parallel join", month = jan, parallelissues = "defined", scope = "rel", } @Article{SanVoe03, author = "P. Sanders and B. V{\"o}cking", title = "Tail Bounds And Expectations For Random Arc Allocation And Applications", journal = "Combinatorics Probability and Computing", year = 2003, volume = 12, number = 3, pages = "301--318" } @InProceedings{SanVoe02, author = "P. Sanders and B. V{\"o}cking", title = "Random Arc Allocation and Applications", booktitle = "8th Scandinavian Workshop on Algorithm Theory", number = 2368, series = "LNCS", pages = "121--130", publisher = "Springer", year = 2001 } @InProceedings{San01aalcom, author = "P. Sanders", title = "Reconciling Simplicity and Realism in Parallel Disk Models", booktitle = "12th ACM-SIAM Symposium on Discrete Algorithms", year = 2001, note = "also report ALCOMFT-TR-01-82", address = "Washington DC", pages = "67--76" } @InProceedings{San01a, author = "P. Sanders", title = "Reconciling Simplicity and Realism in Parallel Disk Models", booktitle = "12th ACM-SIAM Symposium on Discrete Algorithms", year = 2001, address = "Washington DC", pages = "67--76" } @InProceedings{San01awww, author = "P. Sanders", title = "\htmladdnormallink{Reconciling Simplicity and Realism in Parallel Disk Models}{realism-short.ps}", booktitle = "12th ACM-SIAM Symposium on Discrete Algorithms", year = 2001, address = "Washington DC", pages = "67--76" } @InCollection{San01b, author = "P. Sanders", title = "Presenting Data from Experiments in Algorithmics", booktitle = "Experimental Algorithmics --- From Algorithm Design to Robust and Efficient Software", volume = 2547, series = "LNCS", pages = "181--196", publisher = "Springer", year = 2002, } @InCollection{San02bwww, author = "P. Sanders", title = "{\htmladdnormallink{Presenting Data from Experiments in Algorithmics}{mess.ps.gz}}", series = "{\htmladdnormallink{LNCS}{http://www.springer.de/comp/lncs/index}}", booktitle = "Experimental Algorithmics --- From Algorithm Design to Robust and Efficient Software", pages = "181--196", volume = 2547, publisher = "Springer {\copyright}", year = 2002, } @InProceedings{HagRam92, author = "T. Hagerup and R. Raman", title = "Waste makes haste: Tight bounds for loose parallel sorting", booktitle = "33rd IEEE Symposium on Foundations of Computing", pages = "628--637", year = 1992 } @InCollection{MSFCP02www, author = "C. McGeoch and P. Sanders and R. Fleischer and P. R. Cohen and D. Precup", title = "{\htmladdnormallink{Searching for Big-Oh in the Data: Inferring Asymptotic Complexity from Experiments}{bigoh.ps.gz}}", series = "{\htmladdnormallink{LNCS}{http://www.springer.de/comp/lncs/index}}", booktitle = "Experimental Algorithmics --- From Algorithm Design to Robust and Efficient Software", volume = 2547, publisher = "Springer {\copyright}", year = 2002, } @InCollection{MSFCP02, author = "C. McGeoch and P. Sanders and R. Fleischer and P. R. Cohen and D. Precup", title = "Using Finite Experiments to Study Asymptotic Performance", booktitle = "Experimental Algorithmics --- From Algorithm Design to Robust and Efficient Software", volume = 2547, pages = "1--23", series = "LNCS", publisher = "Springer", year = 2002, } @Article{KPH98, author = "K. Keeton and D. A. Patterson and J. M. Hellerstein", title = "A Case for Intelligent Disks ({IDISK}s)", journal = "SIGMOD Record", year = 1998, volume = 27, number = 3 } @InProceedings{HutSanVit01bwww, author = "D. A. Hutchinson and P. Sanders and J. S. Vitter", title = "{\htmladdnormallink{Duality Between Prefetching and Queued Writing with Parallel Disks}{esa01.ps.gz}}", booktitle = "9th European Symposium on Algorithms (ESA)", year = 2001, series = "{\htmladdnormallink{LNCS}{http://www.springer.de/comp/lncs/index.html}}", publisher = "Springer{\copyright}", number = 2161, pages = "62--73", } @InProceedings{HutSanVit01b, author = "D. A. Hutchinson and P. Sanders and J. S. Vitter", title = "Duality Between Prefetching and Queued Writing with Parallel Disks", booktitle = "9th European Symposium on Algorithms (ESA)", year = 2001, number = 2161, pages = "62--73", series = "LNCS", publisher = "Springer", } @Article{LYC02, author = "S.-Y. R. Li and R. W. Yeung and N. Cai", title = "Linear network coding", journal = "IEEE Transactions on Information Theory", year = 2003, pages = "371--381", volume = 49, number = 2, } @InProceedings{CaiYeu02, author = "N. Cai and R. W. Yeung", title = "Network coding and error correction.", booktitle = "Information Theory Workshop", pages = "119--122", year = 2002, address = "Bangalore" } @BOOK{McW88, AUTHOR = {MacWilliams, F.J. and Sloane, N.J.A.}, TITLE = {Theory of error-correcting codes}, PUBLISHER = {North-Holland}, YEAR = {1988}, PLACE = {Natlab-Bib, PB 151}, COMMENT = {Standardwerk ueber Codierungstheorie} } @TECHREPORT{GibEtAl88, AUTHOR = { Gibson, G. A. and Hellerstein, L. and Karp, R. M. and Katz, R. H. and Patterson, D. A. }, TITLE = { Coding Techniques for Handling Failures in Large Disk Arrays, {CSD}-88-477 }, YEAR = {1988}, INSTITUTION = {U. C. Berkley}, URL = {http://cs-tr.cs.berkeley.edu/TR/UCB:CSD-88-477}, COMMENT = { Use linear Maximum Distance Separable (MDS) codes to redundantly store data on disk arrays to protect the data against disk failure. } } @Unpublished{RasLehLeh, author = "A. Rasala~Lehman and E. Lehman.", title = "Complexity Classification of Network Information Flow Problems", note = "manuscript", month = "April", year = 2003, } @InProceedings{HoKMKE03, author = "T. Ho. and R. Koetter and M. M{\'e}dard and D. Karger, M. Effros", title = "The Benefits of Coding over Routing in a Randomized Setting", booktitle = "International Symposium on Information Theory", year = 2003 } @InProceedings{KoeMed02, author = "R. Koetter and M. Medard", title = "An Algebraic Approach to Network Coding", booktitle = "Proceedings of {INFOCOM}", year = 2002 } @Article{ACLY00, author = "R. Ahlswede and N. Cai and S.-Y. R. Li and R. W. Yeung", title = "Network Information Flow", journal = "IEEE Transactions on Information Theory", volume = "46", pages = "1204-1216", number = 4, year = "2000", } @InProceedings{HutSanVit01balcom, author = "D. A. Hutchinson and P. Sanders and J. S. Vitter", title = "Duality Between Prefetching and Queued Writing with Parallel Disks", booktitle = "9th European Symposium on Algorithms (ESA)", year = 2001, series = "LNCS", publisher = "Springer", note = "to appear, also report ALCOMFT-TR-01-79", } @InProceedings{HutSanVit01a, author = "D. A. Hutchinson and P. Sanders and J. S. Vitter", title = "The Power of Duality for Prefetching and Sorting with Parallel Disks", booktitle = "12th ACM Symposium on Parallel Algorithms and Architectures (SPAA Revue)", year = 2001, pages = "334--335" } @Unpublished{SedGon01, author = "A. Sedeno-Noda and C. Gonzales-Martin", title = "A Two-Phase Double Capacity-Scaling Algorithm to Solve the Maximum Flow Problem", note = " " } @InCollection{BadBor93, author = "T. Badics and E. Boros", title = "Implementing a Maximum Flow Algorithm: Experiments with Dynamic Trees", booktitle = "First {DIMACS} Implementation Challenge --- Network Flows and Matching", pages = "43--63", publisher = "DIMACS", year = 1993, volume = 12, series = "{DIMACS} Series in Discrete Mathematics and Theoretical Computer Science" } @InProceedings{Mey01, author = "U. Meyer", title = "Single-Source Shortest-Paths on Arbitrary Directed Graphs in Linear Average-Case Time", booktitle = "Proc. 12th Symposium on Discrete Algorithms", pages = "797--806", year = 2001 } 2.Meyer, U., Single-Source Shortest-Paths on Arbitrary Directed Graphs in Linear Average-Case Time Proc. 12th Symposium on Discrete Algorithms (SODA 2001), pp. 797-806, ACM-SIAM , 2001. @Article{GolRao98, author = "Andrew V. Goldberg and Satish Rao", title = "Beyond the flow decomposition barrier", journal = "Journal of the ACM", volume = "45", number = "5", pages = "1--15", month = sep, year = "1998", coden = "JACOAH", ISSN = "0004-5411", bibdate = "Wed Dec 16 07:11:23 MST 1998", url = "http://www.acm.org:80/pubs/citations/journals/jacm/1998-45-5/p1-goldberg/", abstract = "We introduce a new approach to the maximum flow problem. This approach is based on assigning arc lengths based on the residual flow value and the residual arc capacities. Our approach leads to an {\em O\/}(min({\em n\/}2/3, {\em m\/}1/2){\em m\/} log({\em n\/}2/{\em m\/}) log {\em U\/}) time bound for a network with {\em n\/} vertices, {\em m\/} arcs, and integral arc capacities in the range [1, ..., {\em U\/}]. This is a fundamental improvement over the previous time bounds. We also improve bounds for the Gomory-Hu tree problem, the parametric flow problem, and the approximate {\em s-t\/} cut problem.", acknowledgement = ack-nhfb, keywords = "algorithms", subject = "{\bf F.2.2} Theory of Computation, ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY, Nonnumerical Algorithms and Problems. {\bf G.2.2} Mathematics of Computing, DISCRETE MATHEMATICS, Graph Theory.", xxnote = "Check pages??", } @InProceedings{GolRao97, author = "A. V. Goldberg and S. Rao", title = "Beyond the Flow Decomposition Barrier", pages = "2--11", ISBN = "0-8186-8197-7", booktitle = "Proceedings of the 38th Annual Symposium on Foundations of Computer Science ({FOCS}-97)", month = oct # "20--22~", publisher = "IEEE Computer Society Press", address = "Los Alamitos", year = "1997", } @InProceedings{MehZie00, author = {K. Mehlhorn and M. Ziegelmann}, title = {Resource Constrained Shortest Paths}, booktitle = {7th Annual European Symposium on Algorithms (ESA2000), LNCS 1879}, pages = {326--337}, year = 2000 } @Article{Cheriyan:1996:TAM, author = "Joseph Cheriyan and Torben Hagerup and Kurt Mehlhorn", title = "An $o(n^3)$-Time Algorithm Maximum-Flow Algorithm", journal = "SIAM Journal on Computing", volume = "25", number = "6", pages = "1144--1170", month = dec, year = "1996", coden = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", mrclass = "90C35 (68Q22 68Q25 68R10)", mrnumber = "1 417 893", bibdate = "Sat Dec 5 17:26:53 MST 1998", url = "http://epubs.siam.org/sam-bin/dbq/article/27837", acknowledgement = ack-nhfb, xxtitle = "An $o(n^3)$-time maximum-flow algorithm", } @Unpublished{Hag98, author = "T. Hagerup", title = "Goldberg and Rao's New Maxumum-Flow Algoirthm", note = "MPII noon seminar", year = 1997 } @Unpublished{Nae03, author = "Stefan N{\"a}her", title = "Comparison of Search-Tree Data Structures in {LEDA}", note = "personal communication", } @Article{MehNae90, author = "Kurt Mehlhorn and Stefan N{\"a}her", title = "Bounded Ordered Dictionaries in {$O(\log \log N)$} Time and {$O(n)$} Space", journal = "Information Processing Letters", year = 1990, volume = 35, number = 4, pages = "183--189" } @Article{Emde77, author = "Peter van Emde Boas", title = "Preserving Order in a Forest in Less than Logarithmic Time", journal = "Information Processing Letters", volume = "6", number = "3", pages = "80--82", year = "1977", } @InProceedings{HagSanTra98, author = "T. Hagerup and P. Sanders and J. L. Tr{\"a}ff", title = "An Implementation of the Binary Blocking Flow Algorithm", editor = "K. Mehlhorn", number = "MPI-I-98-1-019, ISSN: 0946-011X", pages = "143--154", series = "Research Reports MPII", booktitle = "2nd Workshop on Algorithm Engineering", year = 1998 } @InProceedings{HagSanTra98www, author = "T. Hagerup and P. Sanders and J. L. Tr{\"a}ff", title = "{\htmladdnormallink{An Implementation of the Binary Blocking Flow Algorithm}{http://www.mpi-sb.mpg.de/{\%7e}wae98/PROCEEDINGS/PAPERS/pap23.ps.gz}}", editor = "K. Mehlhorn", number = "MPI-I-98-1-019, ISSN: 0946-011X", series = "Research Reports MPII", booktitle = "{\htmladdnormallink{2nd Workshop on Algorithm Engineering}{http://www.mpi-sb.mpg.de/{\%7e}wae98/PROCEEDINGS/toc.html}}", year = 1998 } @TechReport{CraEtAl98, author = "A. Crauser and K. Mehlhorn and U. Meyer and P. Sanders", title = "Parallelizing {D}ijkstra's Shortest Path Algorithm", institution = "MPI-Informatik", year = 1998, note = "in preparation" } @InCollection{GraPom00, author = "J. F. Grantham and C. Pomerance", title = "Prime Numbers", booktitle = "Handbook of Discrete and Combinatorial Mathematics", pages = "236--254", publisher = "CRC Press", year = 2000, editor = "K. H. Rosen", chapter = "4.4" } @Book{AWK88, author = "A. V. Aho and B. W. Kernighan and P. J. Weinberger", title = "The {AWK} Programming Language", publisher = "Addison-Wesley", year = 1988 } @Book{WCO00, author = "L. Wall and T. Christiansen and J. Orwant", title = "Programming Perl", publisher = "O'Reilly", year = 2000, edition = "3rd" } @Article{ASTW00, author = "P. Alefragis and P. Sanders and T. Takkula and D. Wedelin", title = "Parallel Integer Optimization for Crew Scheduling", journal = "Annals of Operations Research", year = 2000, volume = 99, number = 1, pages = "141--166", } @InProceedings{AGHSTW98, author = "P. Alefragis and C. Goumopoulos and E. Housos and P. Sanders and T. Takkula and D. Wedelin", title = "Parallel Crew Scheduling in {PAROS}", number = 1470, series = "LNCS", pages = "1104--1113", booktitle = "4th Euro-Par", year = 1998, publisher = "Springer {\copyright}" } @InProceedings{CraEtAl98b, author = "A. Crauser and K. Mehlhorn and U. Meyer and P. Sanders", title = "A Parallelization of {D}ijkstra's Shortest Path Algorithm", series = "LNCS", number = 1450, pages = "722--731", booktitle = "23rd Symposium on Mathematical Foundations of Computer Science", year = 1998, publisher = "Springer", address = "Brno, Czech Republic" } @InProceedings{CraEtAl98bwww, author = "A. Crauser and K. Mehlhorn and U. Meyer and P. Sanders", title = "{\htmladdnormallink{A Parallelization of {D}ijkstra's Shortest Path Algorithm}{wcons_main.ps.gz}}", series = "{\htmladdnormallink{LNCS}{http://www.springer.de/comp/lncs/index.html}}", number = 1450, pages = "722--731", booktitle = "23rd Symposium on Mathematical Foundations of Computer Science", year = 1998, publisher = "Springer {\copyright}", address = "Brno, Czech Republic" } @InProceedings{San99jwww, author = "P. Sanders", title = "{\htmladdnormallink{Parallelizing {NP}-Complete Problems Using Tree Shaped Computations}{http://www.mpi-sb.mpg.de/\%7esanders/papers/jim.ps.gz}}", booktitle = "Journ{\'e}es de l'Informatique Messine (JIM)", year = 1999, address = "Metz", month = "may", note = "invited talk" } @InProceedings{San99j, author = "P. Sanders", title = "Parallelizing {NP}-Complete Problems Using Tree Shaped Computations", booktitle = "Journ{\'e}es de l'Informatique Messine (JIM)", year = 1999, address = "Metz", month = "may", note = "invited talk, {\url{http://www.mpi-sb.mpg.de/~sanders/papers/jim.ps.gz}}" } @Article{MeySan03, author = "U. Meyer and P. Sanders", title = "{$\Delta$}-Stepping: A Parallelizable Shortest Path Algorithm", journal = "Journal of Algorithms", year = 2003, note = "in press" } @Unpublished{MeySan99a, author = "U. Meyer and P. Sanders", title = "{$\Delta$}-Stepping: A Parallelizable Shortest Path Algorithm", note = "{\url{http://www.mpi-sb.mpg.de/~sanders/papers/long-delta.ps.gz}}", year = 1999 } @Unpublished{MeySan99ahab, author = "U. Meyer and P. Sanders", title = "{$\Delta$}-Stepping: A Parallelizable Shortest Path Algorithm", note = "Eingeladen f{\"u}r Journal of Algorithms, {\url{http://www.mpi-sb.mpg.de/~sanders/papers/long-delta.ps.gz}}", } @InProceedings{MeySan98a, author = "U. Meyer and P. Sanders", title = "{$\Delta$}-Stepping: A Parallel Shortest Path Algorithm", series = "LNCS", number = 1461, pages = "393--404", booktitle = "6th European Symposium on Algorithms (ESA)", year = 1998, publisher = "Springer" } @InProceedings{MeySan98awww, author = "U. Meyer and P. Sanders", title = "{\htmladdnormallink{{$\Delta$}-Stepping: A Parallel Shortest Path Algorithm}{wmain.ps.gz}}", series = "{\htmladdnormallink{LNCS}{http://www.springer.de/comp/lncs/index.html}}", number = 1461, pages = "393--404", booktitle = "6th European Symposium on Algorithms (ESA)", year = 1998, publisher = "Springer {\copyright}" } @InProceedings{San98b, author = "P. Sanders", title = "Tree Shaped Computations as a Model for Parallel Applications", booktitle = "ALV'98 Workshop on Application Based Load Balancing", address = "Munich, Germany, 25--26 March", number = "TUM-INFO-02-I9806-100/1.-FI", year = 1998, organization = "SFB 342", series = "TR TU Munich, Germany", note = "{\url{http://www.mpi-sb.mpg.de/~sanders/papers/alv.ps.gz}}" } @InProceedings{San98bs, author = "P. Sanders", title = "Tree Shaped Computations as a Model for Parallel Applications", booktitle = "ALV'98 Workshop on application based load balancing", year = 1998, organization = "SFB 342", publisher = "TU M{\"u}nchen, Germany", note = "{\url{http://www.mpi-sb.mpg.de/~sanders/papers/alv.ps.gz}}" } @InProceedings{San98bwww, author = "P. Sanders", title = "{\htmladdnormallink{Tree Shaped Computations as a Model for Parallel Applications}{alv.ps.gz}}", booktitle = "{\htmladdnormallink{ALV'98 Workshop on application based load balancing}{http://wwwpaul.informatik.tu-muenchen.de/projekte/sfb342/alv/ALV98.html}}", year = 1998, pages = "123--132", organization = "SFB 342", publisher = "TU M{\"u}nchen, Germany", month = "March" } @InProceedings{San99a, author = "P. Sanders", title = "Fast Priority Queues for Cached Memory", series = "LNCS", number = 1619, booktitle = "ALENEX '99, Workshop on Algorithm Engineering and Experimentation ", year = 1999, pages = "312--327", publisher = "Springer" } @InProceedings{San99awww, author = "Peter Sanders", title = "{\htmladdnormallink{Fast Priority Queues for Cached Memory}{falenex.ps.gz}}", series = "{\htmladdnormallink{LNCS}{http://www.springer.de/comp/lncs/index.html}}", booktitle = "ALENEX '99, Workshop on Algorithm Engineering and Experimentation ", year = 1999, note = "{\htmladdnormallink{Extended version in ACM Journal of Experimental Algorithmics}{spqjea.ps.gz}}", number = 1619, pages = "312--327", publisher = "Springer {\copyright}" } @Article{San00b, author = "Peter Sanders", title = "Fast Priority Queues for Cached Memory", journal = "ACM Journal of Experimental Algorithmics", volume = 5, year = 2000, } @Unpublished{San99ahab, author = "P. Sanders", title = "Fast Priority Queues for Cached Memory", note = "Eingeladen f{\"u}r ACM Journal of Experimental Algorithmics, {\url{http://www.mpi-sb.mpg.de/~sanders/papers/falenex.ps.gz}}" } @InProceedings{San99asub, author = "Peter Sanders", title = "{\htmladdnormallink{Fast Priority Queues for Cached Memory}{falenex.ps.gz}}", series = "{\htmladdnormallink{LNCS}{http://www.springer.de/comp/lncs/index.html}}", booktitle = "ALENEX '99, Workshop on Algorithm Engineering and Experimentation ", year = 1999, note = "{\htmladdnormallink{Extended version in ACM Journal of Experimental Algorithmics}{spqjea.ps.gz}}", number = 1619, pages = "312--327", publisher = "Springer {\copyright}" } @InProceedings{San98cpars, author = "P. Sanders", title = "Random Permutations on Distributed, External and Hierarchical Memory", number = 17, series = "PARS-Mitteilungen", pages = "160--165", booktitle = "PARS-Workshop", year = 1998, organization = "GI-ITG: Parallel-Algorithmen, -Rechnerstrukturen und -Systemsoftware", month = "September" } @InProceedings{Tho00, author = "Mikkel Thorup", title = "Even strongly universal hashing is pretty fast.", pages = "496--497", booktitle = "Proceedings of the Eleventh Annual {ACM}-{SIAM} Symposium on Discrete Algorithms", month = jan # "~9--11", publisher = "ACM Press", address = "N.Y.", year = "2000", } @Article{Cle84, author = "J. G. Cleary", title = "Compact Hash Tables Using Bidirectional Linear Probing", journal = "IEEE Transactions on Computers", year = 1984, volume = "C-33", number = 9, pages = "828--834" } @Article{Pearson90, author = "P. K. Pearson.", title = "Fast Hashing of Variable Length Strings.", journal = "Comm. A.C.M.", volume = "33", number = "6", month = jun, year = "1990", keywords = "perfect, hash, hashing, string", abstract = "He discusses use of hash functions of the form: h = 0; n = length(string); for i = 1 through n do h = Table [ h XOR string [i]]; enddo; return h; where Table is a 256-byte array. Each character in the string hashed costs an XOR operation and an indexed read from memory (above the costs of reading the character). This function can {"}sometimes be modified to produce a minimal perfect hashing function over a modest list of words.{"}", } @InProceedings{San99b, author = "P. Sanders", title = "Accessing Multiple Sequences Through Set Associative Caches", series = "LNCS", booktitle = "ICALP", number = 1644, pages = "655--664", year = 1999, } @InProceedings{San99bwww, author = "P. Sanders", title = "\htmladdnormallink{Accessing Multiple Sequences Through Set Associative Caches}{icalp55.ps.gz}", series = "{\htmladdnormallink{LNCS}{http://www.springer.de/comp/lncs/index.html}}", booktitle = "ICALP", number = 1644, pages = "655--664", year = 1999, publisher = "Springer {\copyright}", note = "{\htmladdnormallink{extended version (with K. Mehlhorn)}{icalpfull.ps.gz}}" } @InCollection{BMS02www, series = "{\htmladdnormallink{LNCS}{http://www.springer.de/comp/lncs/index}}", publisher = "Springer {\copyright}", author = "D. Bader and B. Moret and P. Sanders", booktitle = "Experimental Algorithmics From Algorithm Design to Robust and Efficient Software", volume = 2547, pages = "1--23", title = "{\htmladdnormallink{Algorithm Engineering for Parallel Computation}{parallel-algen.ps.gz}}", year = 2002 } @InCollection{BMS02, author = "D. Bader and B. Moret and P. Sanders", booktitle = "Dagstuhl Seminar on Experimental Algorithmics (2000)", title = "Algorithm Engineering for Parallel Computation", booktitle = "Experimental Algorithmics --- From Algorithm Design to Robust and Efficient Software", volume = 2547, pages = "1--23", series = "LNCS", publisher = "Springer", year = 2002 } @Unpublished{BMS02a, author = "D. Bader and B. Moret and P. Sanders", title = "High-Performance Algorithm Engineering for Parallel Computation", note = " ", year = 2002 } @Unpublished{MehSan00a, author = "K. Mehlhorn and P. Sanders", title = "Scanning Multiple Sequences Via Cache Memory", note = "{\url{http://www.mpi-sb.mpg.de/~sanders/papers/icalpfull.ps.gz}}, short version: ICALP '99, pages 655--664" } @Article{San99c, author = "P. Sanders", title = "Analysis of Nearest Neighbor Load Balancing Algorithms for Random Loads", journal = "Parallel Computing", year = 1999, volume = 25, pages = "1013--1033" } @InCollection{San99dwww, author = "P. Sanders", title = "\htmladdnormallink{Berechnungen mit gro{\ss}en {D}atenmengen}{jahrbuch.ps.gz}", booktitle = "Jahrbuch der Max-Planck-Gesellschaft", publisher = "MPG", year = 1999, pages = "534--540", } @InCollection{San99d, author = "P. Sanders", title = "Berechnungen mit gro{\ss}en Datenmengen", booktitle = "Jahrbuch der Max-Planck-Gesellschaft", publisher = "MPG", year = 1999, pages = "534--540", } @InProceedings{San99e, author = "P. Sanders", title = "Asynchronous Random Polling Dynamic Load Balancing", booktitle = "ISAAC: 10th International Symposium on Algorithms and Computation", year = 1999, pages = "37--48", series = "LNCS", number = "1741", address = "Chennai, India, 16--18 December", month = "Dec.", publisher = "Springer-Verlag Berlin", } @InProceedings{San99ewww, author = "P. Sanders", title = "\htmladdnormallink{Asynchronous Random Polling Dynamic Load Balancing}{isaac99.ps.gz}", pages = "37--48", booktitle = "ISAAC: 10th International Symposium on Algorithms and Computation", year = 1999, series = "LNCS", address = "Chennai, India", month = "Dec.", publisher = "Springer {\copyright}", note = "\htmladdnormallink{full paper}{submit.ps.gz}" } @Article{San02b, author = "Peter Sanders", title = "Randomized Receiver Initiated Load Balancing Algorithms for Tree Shaped Computations", journal = "The Computer Journal", year = 2002, pages = "561--573", volume = 45, number = "5", } @InProceedings{FPSS03www, author = "D. Fotakis and R. Pagh and P. Sanders and P. Spirakis", title = "Space Efficient Hash Tables With Worst Case Constant Access Time\htmladdnormallink{full paper}{d-cuckoo.ps.gz}", booktitle = "20th International Symposium on Theoretical Aspects of Computer Science", year = 2003, series = "LNCS", address = "Berlin", publisher = "Springer", pages = "271--282", number = 2607 } @InProceedings{FPSS03, author = "D. Fotakis and R. Pagh and P. Sanders and P. Spirakis", title = "Space Efficient Hash Tables With Worst Case Constant Access Time", booktitle = "20th International Symposium on Theoretical Aspects of Computer Science", year = 2003, series = "LNCS", address = "Berlin", publisher = "Springer", pages = "271--282", number = 2607 } @Article{SanEgnKorboth, author = "P. Sanders and S. Egner and Jan Korst", title = "Fast Concurrent Access to Parallel Disks", journal = "Algorithmica", year = 2003, volume = 35, number = 1, pages = "21--55", note = "short version in 11th SODA, pages 849--858, 2000." } @Article{SanEgnKor03, author = "P. Sanders and S. Egner and Jan Korst", title = "Fast Concurrent Access to Parallel Disks", journal = "Algorithmica", year = 2003, volume = 35, number = 1, pages = "21--55" } @TechReport{SanEgnKor99, author = "P. Sanders and S. Egner and Jan Korst", title = "Fast Concurrent Access to Parallel Disks", institution = "Max-Planck-Institute for Computer Science", year = 1999, number = "MPI-I-1999-1-003", month = "June" } @TechReport{SanEgnKor99www, author = "P. Sanders and S. Egner and Jan Korst", title = "\htmladdnormallink{Fast Concurrent Access to Parallel Disks}{tr-pardisk.ps.gz}", institution = "Max-Planck-Institute for Computer Science", year = 1999, note = "{\htmladdnormallink{updated version}{full-pardisk.ps.gz}}", number = "MPI-I-1999-1-003", month = "June" } @Article{RatSanKni99, author = "U. Rathe and P. Sanders and P. Knight", title = "A Case Study in Scalability: an {ADI} Method for the Two-Dimensional Time-Dependent {D}irac Equation", journal = paco, number = 5, volume = 25, pages = "525--534", month = "may", year = 1999, } @InProceedings{SanTakWed99a, author = "P. Sanders and T. Takkula and D. Wedelin", title = "{\htmladdnormallink{High Performance Integer Optimization for Crew Scheduling}{hpcn.ps.gz}}", booktitle = "7th International Conference on High Performance Computing and Networking Europe", year = 1999, number = 1593, series = "{\htmladdnormallink{LNCS}{http://www.springer.de/comp/lncs/index.html}}", publisher = "Springer {\copyright}", pages = "3--12", note = "{\htmladdnormallink{full paper}{hpcnfull.ps.gz}}" } @InProceedings{DSSS04www, author = "R. Dementiev and P. Sanders and D. Schultes and J. Sibeyn", title = "\htmladdnormallink{Engineering an External Memory Minimum Spanning Tree Algorithm}{emst.ps.gz}", booktitle = "IFIP TCS", year = 2004, address = "Toulouse", } @InProceedings{DSSS04, author = "R. Dementiev and P. Sanders and D. Schultes and J. Sibeyn", title = "{Engineering an External Memory Minimum Spanning Tree Algorithm}", booktitle = "IFIP TCS", year = 2004, address = "Toulouse", pages = {195-208} } @Unpublished{SanTra01, author = "P. Sanders and J. L. Tr{\"a}ff", title = "The Factor Algorithm for All-to-all Communication on Clusters of {SMP} Nodes", note = "Manuscript", year = 2001 } @Unpublished{Sch03, author = "D. Schultes", title = "External Memory Minimum Spanning Trees", note = "Bachelor thesis, Max-Planck-Institut f. Informatik and Saarland University, {\url{???}}", month = "August", year = 2003 } @Unpublished{Tak97, author = "T. Takkula", title = "OPT1/2 1.0, classes dealing with mixed integer problem data", note = "Paros Documentation", year = 1997, annote = "alte Version" } @PhdThesis{Nie96a, author = "R. Niedermeier", title = "Towards Realistic and Simple Models of Parallel Computation", school = "University of T{\"u}bingen", year = 1996, type = "Dissertation" } @Unpublished{Lux98, author = "Luxburg, Ulrike von", title = "Lokalit{\"atsma\ss}e von Peanokurven", note = "Studienarbeit Uni T{\"u}bingen, Betreuer K. Reinhard", year = 1998 } @Unpublished{Nie96, author = "R. Niedermeier", title = "Exact Determination of the Manhattan Distance for Hilbert Indexings of Grids", year = 1995 } @Article{Pan03, author = "A. Panholzer", title = "Analysis of Multiple Quickselect Variants", journal = "Theoretical Computer Science", year = 2003, volume = 302, pages = "45--91" } @Article{MG91, author = "J. Misra and D. Gries", title = "A Constructive Proof of Vizing's Theorem", journal = "Inf. Process. Lett.", year = 1991, volume = 41, number = 3, pages = "131--133" } Jayadev Misra, David Gries: A Constructive Proof of Vizing's Theorem. Inf. Process. Lett. 41(3): 131-133 (1992). 1991. @Misc{Par96, author = "Parcella 96", title = "List of Participants", year = 1996 } @InProceedings{CheRot94, author = "L. T. Chen and D. Rotem", title = "Optimal response time retrieval of replicated data (extended abstract)", booktitle = "13th {ACM} Symposium on Principles of Database Systems", volume = "13", publisher = "ACM Press", ISBN = "0-89791-642-5", pages = "36--44", year = "1994", bibdate = "Wed Oct 25 12:40:13 MDT 2000", url = "http://www.acm.org/pubs/articles/proceedings/pods/182591/p36-chen/p36-chen.pdf; http://www.acm.org/pubs/citations/proceedings/pods/182591/p36-chen/; http://www.acm.org:80/pubs/citations/proceedings/pods/182591/p36-chen/", abstract = "This work deals with the problem of finding efficient access plans for retrieving a set of pages from a multi-disk system with replicated data. This paper contains two results related to this problem: (a) We solve the problem of finding an optimal access path by transforming it into a network flow problem. We also indicate how our method may be employed in dynamic environments where some (or all) of the disks have a preexisting load, are heterogeneous, and reside on different servers. (b) We present a lower bound for the worst case response time of a request under all replication schemes, and also discuss the replication scheme that results in this lower bound. We then use simulation to show how this replication scheme can also greatly reduce the average case response time.", acknowledgement = ack-nhfb, generalterms = "Algorithms; Design; Performance; Theory; Verification", keywords = "ACM; algorithms; computability; database systems; design; performance; SIGACT; SIGART; SIGMOD; theory; verification", subject = "{\bf G.2.2} Mathematics of Computing, DISCRETE MATHEMATICS, Graph Theory, Network problems. {\bf H.2.2} Information Systems, DATABASE MANAGEMENT, Physical Design, Access methods. {\bf F.2.2} Theory of Computation, ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY, Nonnumerical Algorithms and Problems, Computations on discrete structures.", } @Article{EdeRotWel89, author = "H. Edelsbrunner and G. Rote and E. Welzl", title = "Testing the Necklace Condition for Shortest tours and Optimal Factors in the Plane", journal = "Theoretical Computer Science", year = 1989, volume = 66, pages = "157--180" } @Unpublished{Wel01, author = "E. Welzl", title = "Combinatorial Methods for Linear Programming and Related Problems", note = "course notes, ADFOCS 01", year = 2001, annote = "LP type problem" } @Article{AsaEtAl97, title = "Space-filling curves and their use in the design of geometric data structures", author = "Tetsuo Asano and Desh Ranjan and Thomas Roos and Emo Welzl and Peter Widmayer", pages = "3--15", journal = "Theoretical Computer Science", year = "1997", volume = "181", number = "1", } @InProceedings{AsaEtAl95, author = "T. Asano and D. Ranjan and T. Roos and E. Welzl and P. Widmayer", title = "Space Filling Curves and Their Use in the Design of Geometric Data Structures", booktitle = "{LATIN} '95: theoretical informatics: second Latin American Symposium", number = 911, series = "LNCS", year = 1995, address = "Valparaiso, Chile", month = "April", pages = "36ff" } @Article{AsaEtAl95, author = "T. Asano and D. Ranjan and T. Roos and E. Welzl and P. Widmayer", title = "Space Filling Curves and Their Use in the Design of Geometric Data Structures", journal = "??", year = 1995, annote = "'verdrehte' Hilbertkurve ermoeglichen es mit max. 3 Zugriffen asympt. optimaler Groesse auf eine Datei ein quadratisches Teilgebiet zu lesen." } @Article{ GotLin96, author = {C. Gotsman and M. Lindenbaum}, title = {On the Metric Properties of Discrete Space-Filling Curves}, journal = {IEEE Transactions on Image Processing}, volume = {5}, number = {5}, pages = {794--797}, month = {May}, year = {1996} } @Article{BhaCai93, author = "S. Bhatt and Jin-Yi Cai", title = "Taking Random Walks to Grow Trees in Hypercubes", journal = jacm, year = 1993, volume = 40, number = 3, pages = "741--764", annote = "Ergebnis schlechter als Leighton und Co. Warum zitieren sie ihn? Verdacht: Nur preprint gelesen." } @InProceedings{SevAluFut00, author = "F. E. Sevilgen and S. Aluru and N. Futamura", title = "A Provably Optimal, Distribution-Independent Parallel Fast Multipole Method", booktitle = "Proc. IPDPS", pages = "77--84", year = 2000, annote = "schoenes Papier. Relativ theoretisch. Gutes Beispiel fuer mein Lieblingsparallelmodell mit kollektiven Operationen als Basis. Verfahren ohne Lastverteilung. Offene Frage: kann man auf Maschinen mit sublinearer Bisektionsbreite mit LV Beweisbar besser sein?" } @InProceedings{LiuBha94, author = "P. Liu and S. N. Bhatt", title = "Experiences with Parallel N-body Simulation", pages = "122--131", booktitle = spaa, year = 1994, address = "Cape May, New Jersey", annote = "Referenz auf Verwendung variabler Zeitschritte, Barnes Hut wird als Konkurrenzfaehig gegen Multipole dargestellt. (Quadrupolmomente werden allerdings benutzt.), Singh wird kleingemacht, Referenz auf library fuer n-body abstraktionen. Wenig Cach aendereungen im seq, Teil werden nachgewiesen." } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Allgemeines @Unpublished{Ach94, author = "Alf-Christian Achilles", title = "Eine L{\"o}sung auf der Suche nach Problemen", year = 1994 } @InProceedings{Ach95a, author = "Alf-Christian Achilles", title = "Optimal Emulation of Meshes on Meshes-of-Trees", booktitle = "{EURO-PAR} International Conference on Parallel Processing", year = 1995, pages = "193--204" } @PhdThesis{Ach95b, author = "Alf-Christian Achilles", title = "Effiziente Emulation von Verbindungsnetzwerken", school = uka, year = 1995, type = "Dissertation" } @Misc{Ach95c, author = "Alf-Christian Achilles", title = "A Collection of Computer Science Bibliographies", howpublished = "{\tt http://liinwww/bibliography/index.html}", year = 1995 } @Article{AfeEtAl96, author = "Y. Afek and B. Awerbuch and S. Plotkin and M. Saks", title = "Local Management of a Global Recource in Communication Network", journal = jacm, year = 1996, volume = 43, number = 1, pages = "1--19", annote = "verteilter Algorithmus der hoechstens M Einheiten einer globalen Ressource zuteilt aber hoechstens dann eine Zuteilung ablehnt, wenn weniger als M-W zugeteilt worden sein werden :-). Legen besonderen Werte auf geringe nachrichtenkomplexitaet" } @Book{Akl89, author = "S. G. Akl", title = "The Design and Analysis of Parallel Algorithms", publisher = "Prentice-Hall", year = 1989 } @Book{BroSem79, author = "I. N. Bronstein and K. A. Semendjajew", title = "Taschenbuch der Mathematik", publisher = "Teubner", year = 1979 } @Article{Bro88, author = "R. Brown", title = "Calendar Queues: A Fast {$O(1)$} Priority Queue Implementation for the Simulation Event Set Problem", journal = cacm, year = 1988, volume = 31, number = 10, pages = "1220--1227", annote = "Leistung nur empirisch fuer bestimmte Verteilungen gemessen. Einordnung in Buckets." } @InProceedings{EriLadLaM94, author = "K. B. Erickson and R. E. Ladner and A. LaMarca", title = "Optimizing Static Calendar Queues", pages = "732--743", ISBN = "0-8186-6580-7", editor = "Shafi Goldwasser", booktitle = "Proceedings of the 35th Annual Symposium on Foundations of Computer Science", month = nov, publisher = "IEEE Computer Society Press", address = "Los Alamitos, CA, USA", year = "1994", } @Article{FisPat94, author = "M. J. Fischer and M. S. Paterson", title = "Fishspear: A Priority Queue Algorithm", journal = jacm, year = 1994, volume = 41, number = 1, pages = "3--30" } @Article{JuuWij98, author = "B. Juurlink and H. A.G. Wijshoff", title = "A Quantitative Comparison of Parallel Computation Models", journal = "ACM Transactions on Computer Systems", year = 1998, volume = 16, number = 3, pages = "271--318" } @InProceedings{CulEtAl93, author = "D. Culler and R. Karp and D. Patterson and A. Sahay and K. E. Schauser and E. Santos and R. Subramonian and T. v. Eicken", title = "{LogP}: Towards a Realistic Model of Parallel Computation", booktitle = "Fourth {ACM} {SIGPLAN} Symposium on Principles and Practice of Parallel Programming", year = 1993, pages = "1--12", address = "San Diego, CA, 19--22 May", publisher = "ACM, New York", annote = "Lokale Kommunikation wird nicht belohnt. Lange Nachrichten passen irgendwie nicht ins Bild." } @Article{AISS97, author = "Albert Alexandrov and Mihai F. Ionescu and Klaus E. Schauser and Chris Scheiman", title = "{LogGP}: Incorporating Long Messages into the {LogP} Model for Parallel Computation", journal = "Journal of Parallel and Distributed Computing", volume = "44", number = "1", pages = "71--79", day = "10", month = jul, year = "1997", coden = "JPDCER", ISSN = "0743-7315", bibdate = "Tue Mar 17 17:08:12 MST 1998", acknowledgement = ack-nhfb, } @Book{Tuf83, author = "Edward R. Tufte", title = "The Visual Display of Quantitative Information", publisher = "Graphics Press", address = "Cheshire, Connecticut, U.S.A.", year = "1983", ISBN = "0-9613921-0-X", } @InProceedings{AISS95, author = "Albert Alexandrov and Mihai Ionescu and Klaus E. Schauser and Chris Scheiman", title = "{LogGP} : Incorporating Long Messages into the Log{P} model : One step closer towards a realistic model for parallel computation", pages = "95--105", booktitle = "7th Annual Symposium on Parallel Algorithms and Architectures ({SPAA} '95)", ISBN = "0-89791-717-0", month = jul, publisher = "ACM", address = "New York, USA", year = "1995", } @InProceedings{CulEtAl93s, author = "D. Culler and others", title = "{LogP}: Towards a Realistic Model of Parallel Computation", booktitle = "Fourth {ACM} {SIGPLAN} Symposium on Principles and Practice of Parallel Programming", year = 1993, pages = "1--12", address = "San Diego", annote = "Lokale Kommunikation wird nicht belohnt. Lange Nachrichten passen irgendwie nicht ins Bild." } @Article{CulEtAl96, author = "D. Culler and R. Karp and D. Patterson and A. Sahay and K. E. Schauser and E. Santos and R. Subromonian and T. v. Eicken", title = "{LogP} a Practical Model of Parallel Computation", journal = cacm, year = 1996, volume = 39, number = 11, pages = "78--85" } @Article{DinSud94, author = "A. Dingle and I. H. Sudborough", title = "Efficient Mappings of Pyramid Networks", journal = tpds, year = 1994, volume = 5, number = 10, pages = "1009--1017", annote = "Benutzen Hilbertkurven -> Miller/Stout" } @Article{GilMat94, author = "J. Gil and Y. Matias", title = "Designing Algorithms by Expectations", journal = ipl, year = 1994, volume = 51, pages = "31--34", annote = "Anwendung von Chernoff Schranken auf abhangige Folgen. Schluss von der Erfolgswahrscheinlichkeit einer Iteration auf dern Erwartungswert der Ausfuhrungszeit." } @Article{Mot94, title = "Average-Case Analysis of Algorithms for Matchings and Related Problems", author = "Rajeev Motwani", area = "Operations Research", pages = "1329--1356", journal = "Journal of the ACM", month = nov, year = "1994", volume = "41", number = "6", references = "\cite{STOC::BollobasFF1985} \cite{STOC::Broder1986} \cite{FOCS::EvenK1975} \cite{STOC::FederM1991} \cite{STOC::GabowT1988} \cite{STOC::JerrumS1988} \cite{FOCS::KarpS1981} \cite{FOCS::MicaliV1980}", } @Article{Han95, author = "Y. Han", title = "An Improvement on Parallel Computation of a Maximal Matching", journal = "Information Processing Letters", year = 1995, volume = 56, number = 6, pages = "343--348" } @Article{HopKar73, author = "J. E. Hopcroft and R. M. Karp", title = "An {O}(n**5/2) algorithm for maximum matchings in bipartite graphs", journal = "SIAM Journal on Computing", volume = "2", pages = "225--231", year = "1973", } @Book{HopUll79, author = "J. E. Hopcroft and J. D. Ullman", title = "Introduction to Automata Theory, Languages, and Computation", publisher = "Addison-Wesley", year = 1979, annote = "Blums speedup theorem" } @InProceedings{GNL01, author = "D. J. Gonzalez and J. J. Navarro and J. Larriba-Pey", title = "Fast Parallel In-Memory 64-bit Sorting", booktitle = "ACM Supercomputing", pages = "114--122", year = 2001, annote = "nett aber nichts algorithmisch neues" } @InProceedings{MatVis90, title = "On Parallel Hashing and Integer Sorting (Extended Summary)", author = "Y. Matias and U. Vishkin", booktitle = "17th ICALP", year = "1990", series = "LNCS", number = "443", pages = "729--743", } @InProceedings{MatVis91, author = "Y. Matias and U. Vishkin", title = "Converting High Probability into Nearly-Constant Time -- with Applications to Parallel Hashing", pages = "307--316", booktitle = stoc, year = 1991 } @InProceedings{GodMatVis94, author = "M. T. Goodrich and Y. Matias and U. Vishkin", booktitle = "5th ACM-SIAM Symp. on Discrete Algorithms (SODA),", title = "Optimal Parallel Approximation Algorithms for Prefix Sums and Integer Sorting", year = "1994", url = "http://www.cs.jhu.edu/{\%7e}goodrich/pubs/prefix.ps", pages = "241--250", scope = "scan", } @Article{Rab89, author = "M. O. Rabin", title = "Efficient Dispersal of Information for Security, Load Balancing and Fault Tolerance", journal = "Journal of the ACM", year = 1989, volume = 36, number = 2, pages = "335--348", annote = "One of the oldest references for r out of R schemes? No concurrent disk access however. (Routing and fault tolerance. Detailed discussion of the coding schemes" } @Article{CPRV98, author = "I. D. D. Curcio and A. Puliafito and S. Riccobene and L. Vita", title = "Design and evaluation of a multimedia storage server for mixed traffic", journal = "Multimedia Systems", year = 1998, volume = 6, pages = "367--381", annote = "Nothing really new as far as I can see. But perhaps its interestin to compare the messages with what Phillips of Uni-SB does." } @Unpublished{ABL01, author = "D. Arnon and E. Bachmat and T. K. Kam", title = "On the Macroscopic Approach to Storage System Optimization", note = "??", year = "2001?" } @Unpublished{AlonBachmat04, author = "Noga Alon and Eitan Bachmat", title = "Regular Graphs Whose Subgraphs Tend to be Acyclic", note = "nimm regulaeren Zufallsgraph und schmeisse kleine Kreise aktiv raus", year = 2004 } @TechReport{KorCou98, author = "J. Korst and P. Coumans", title = "Asynchronous Control of Disks in Video Servers", institution = "Philips Research Laboratories", year = 1998, number = "NL-MS-19.649", address = "Eindhoven, the Netherlands" } @InProceedings{Korst97, author = "J. Korst", title = "Random Duplicate Assignment: An Alternative to Striping in Video Servers", pages = "219--226", booktitle = "ACM Multimedia", year = 1997, address = "Seattle" } @Book{Tri82, author = "K. S. Trivedi", title = "Probability and Statistics with Reliability, Queueing and Computer Science Applications", publisher = "Prentice Hall", address = "Englewood Cliffs", year = 1982, ISBN = "0-13-711564-4", descriptor = "Markovkette, Statistik, Stochastischer Prozess, Wahrscheinlichkeitstheorie, Wartenetz, Warteschlangennetz, Warteschlangentheorie, Zuverlaessigkeitstheorie, Queue, Queueing", annote = "Jop hat es. War Grundlage fuer Ausrechnung der erwarteten queue length bei zufaelligem Schreiben. Besprechungen des Buches sind erschienen in: 1. Angewandte Informatik 3/83, S. 131 2. ACM Sigmetrics, Vol. 11, Nr. 3, S. 14, 1982", } @Book{Nelxx, author = "R. Nelson", title = "Probability, Stochastic Processe and Queueing Theory", publisher = "Springer", year = "19??", annote = "Abschnitt ueber qeuing theorie kopiert" } @InProceedings{NRMPTW97, author = "G. Nerjes and Y. Romboyannakis and P. Muth and M. Paterakis and P. Triantafillou and G. Weikum", title = "On Mixed-Workload Multimedia Storage Servers with Guaranteed Performance and Service Quality", booktitle = "3rd Workshop on Multimedia Information Systems", year = 1997, pages = "63--72", address = "Como, Italy" } @Article{NMPRTW99, author = "Nerjes, G. and Muth, P. and Paterakis, M. and Romboyannakis, Y. and Triantafillou, P. and Weikum, G.", title = "Incremental Scheduling of Mixed Workloads in Multimedia Information Servers", journal = "Journal of Multimedia Tools and Applications", year = 2000, volume = 11, number = 1, pages = "249--273", } Nerjes, G., Muth, P., Paterakis, M., Romboyannakis, Y., Triantafillou, P., Weikum, G.: Incremental Scheduling of Mixed Workloads in Multimedia Information Servers to appear in: Special Issue of the Journal of Multimedia Tools and Applications, Kluewer 1999 @InProceedings{NerMutWei97, author = "G. Nerjes and P. Muth and G. Weikum", title = "Stochastic Service Guarantees for Continuous Data on Multi-Zone Disks ", booktitle = "16th Symposium on Principles of Database Systems", year = 1997 } @Article{SalTso99, author = "B. Salzberg and V. J. Tsotras", title = "Comparison of Access Methods for Time-Evolving Data", journal = "ACM Computing Surveys", year = 1999, volume = 31, number = 2, pages = "158--221" } @InProceedings{JCJ03, author = "S. Jaggi and P. S. Chou and K. Jain", title = "Low Complexity Algebraic Multicast Network Codes", booktitle = "International Symposium on Information Theory", year = 2003, month = "July", organization = "IEEE", note = "1 page abstract, to appear" } @InProceedings{JMS03, author = "K. Jain and M. Mahdian and M. R. Salavatipour", title = "Packing {S}teiner Trees", booktitle = "14th ACM-SIAM Symposium on Discrete Algorithms", year = 2003, } @Unpublished{BalSri03, title = "Approximate Implementation of Minimum Multicast Congestion --- Implementation versus Theory", author = "A. Baltz and A. Srivastav", note = "Manuscript" } @InProceedings{JanZha02, author = "K. Jansen and H. Zhang", title = "An approximation algorithm for the multicast congestion problem via minimum {S}teiner trees", booktitle = "3rd International Workshop on Approximation and Randomized Algorithms in Communication Networks (ARANCE)", year = 2002, address = "Rome, Italy" } @InProceedings{CarVem00, author = "B. Carr and S. Vempala", title = "Randomized meta-rounding", booktitle = "32nd ACM Symposium on the Theory of Computing", pages = "58--62", year = 2000, note = "also in Random Structures and Algorithms, 20(3):343--352, 2002" } 13.Randomized meta-rounding. (Bob Carr) Proc. of the 32nd ACM Symposium on the Theory of Computing (STOC '00), Portland, 2000. @InProceedings{VemVoe99, author = "S. Vempala and B. V{\"o}cking", title = "Approximating Multicast Congestion", booktitle = "10th Int. Symp. on Algorithms and Computation", pages = "367--372", year = 1999, number = 1741, series = "LNCS", address = "Chennai", publisher = "Springer" } S. Vempala and B. V�king. Approximating Multicast Congestion. In Proc. 10th ISAAC (Chennai, India, 1999). Abstract or compressed postscript . @InProceedings{Voe99, author = "B. V{\"o}cking", title = "How Asymmetry Helps Load Balancing", booktitle = "40th Symposium on Foundations of Computer Science", organization = "IEEE", pages = "131--140", year = 1999 } @InProceedings{RaaSte98, author = "M. Raab and A. Steger", title = "``Balls into Bins'' -- {A} Simple and Tight Analysis", booktitle = "RANDOM: International Workshop on Randomization and Approximation Techniques in Computer Science", volume = "1518", pages = "159--170", publisher = "LNCS", year = "1998", } @Article{BHH96, author = "B. Bhattacharya and P. Hell and J. Huang", title = "A Linear Algorithm for Maximum Weight Cliques in Proper Circular Arc Graphs", journal = "SIAM Journal on Discrete Mathematics", volume = "9", number = "2", pages = "274--289", month = may, year = "1996", ISSN = "0895-4801 (print), 1095-7146 (electronic)", keywords = "adjacency lists; algorithm complexity; computational complexity; graph theory; inclusion-free family; linear-time algorithm; maximum weight cliques; optimisation; proper circular arc graphs; $q$-coloring; sorted simple family; weighted graph", } @InProceedings{BCSV00, author = "P. Berenbrink and A. Czumaj and A. Steger and B. V{\"o}cking", title = "Balanced Allocations: The Heavily Loaded Case", pages = "745--754", booktitle = "32th Annual {ACM} Symposium on Theory of Computing", year = 2000, } @Article{CzuSte01, author = "A. Czumaj and V. Stemann", title = "Randomized Allocation Processes", journal = "Random Structures {\&} Algorithms", year = 2001, volume = 18, number = 4, pages = "297--331" } @InProceedings{CzuSte97, author = "A. Czumaj and V. Stemann", title = "Randomized Allocation Processes", pages = "194--203", booktitle = "38th Symposium on Foundations of Computer Science (FOCS)", year = 1997, organization = "IEEE" } @Article{PitSpeWor96, author = "B. Pittel and J. Spencer and N. Wormald", title = "Sudden Emergence of a giant $k$-core in random graph", journal = "J. Combinatorial Theory, Series B", year = 1996, volume = 67, pages = "111-151" } @Unpublished{CSW03, author = "J. Cain and P. Sanders and N. Wormald", title = "A Random Multigraph Process for Linear Time {RDA} Disk Scheduling", note = "manuscript in preparation", year = 2003 } @InProceedings{JurKut01, author = "T. Jurdzinski and M. Kutylowski", title = "Communication Gap for Finite Memory Devices", booktitle = "ICALP", year = 2001 } @InProceedings{DGP02, author = "J. Dumas and T. Gautier and C. Pernet", title = "Finite Field Linear Algebra Subroutines", booktitle = "ISSAC", pages = "63--74", year = 2002, address = "Lille", organization = "ACM" } @Article{Ima80, author = "K. Imamura", title = "A method for computing addition tables in {$GF(p^n)$}", journal = "IEEE Transactions on Information Theory", year = 1980, volume = 26, pages = "367--369" } @InProceedings{CzuEtAl96, author = "A. Czumaj and P. Knarek and M. Kutylowski and K. Lorys", title = "Fast Generation of Random Permutations via Network Simulation", pages = "246--260", series = "LNCS", number = "1136", booktitle = "4th European Symposium on Algorithms", year = 1996 } @InProceedings{ColGru02, author = "D. Colarelli and D. Grunwald", title = "Massive Arrays of Idle Disks For Storage Archives", booktitle = "SC'2002 Conference CD", publisher = "IEEE/ACM SIGARCH", address = "Baltimore, MD", month = nov, year = "2002", keywords = "system components,", abstract = "The declining costs of commodity disk drives is rapidly changing the economics of deploying large amounts of online or near-line storage. Conventional mass storage systems use either high performance RAID clusters, automated tape libraries or a combination of tape and disk. In this paper, we analyze and alternative design using massive arrays of idle disks, or MAID. We argue that this storage organization provides storage densities matching or exceeding those of tape libraries with performance similar to disk arrays. Moreover, we show that with effective power management of individual drives, this performance can be achieved using a very small power budget. In particular, we show that our power management strategy can result in performance comparable to an always-on RAID system while using 1/15th the power of such a RAID system.\par http://www.sc-conference.org/sc2002/", } @InProceedings{MadGibFal99, author = "R. M. Madhyastha and G. A. Gibson and C. Faloutsos", title = "Informed Prefetching of Collective Input/Output Requests", booktitle = "ACM Supercomputing", year = 1999, annote = "two phase I/O, batched I/O, brauchen lookahead D^2" } @InProceedings{BleEtAl95, author = "G. E. Blellock and P. B. Gibbons and Y. Matias", title = "Provably Efficient Scheduling for Languages with Fine-Grained Parallelism", booktitle = spaa, year = 1995, pages = "1--12", annote = "Nur deterministische Abhaengigkeiten, PRAM. Tpar in O(Tseq/n + Tcritical log n" } @InProceedings{GibEtAl94, author = {P. B. Gibbons and Y. Matias and V. Ramachandran}, title = {Efficient Low Contention Parallel Algorithms}, booktitle = spaa, year = 1994, address = {Cape May, NJ}, pages = {236--247} } InProceedings{Vis92, author = "U. Vishkin", title = "A Case for the {PRAM} as a Standard Programmer's Model", series = "LNCS", number = "678", booktitle = "Heinz Nixdorf Symposium on Parallel Architectures and Their Efficient Use", year = "1992", } @InProceedings{GilEtAl91, author = "J. Gil and Y. Matias and U. Vishkin", title = "Towards a Theory of Nearly Constant Time Parallel Algorithms", pages = "698--710", booktitle = focs, year = 1991, publisher = "IEEE", annote = "Total abgedrehter Kram. Extrem kompakt. Martingale Tail inequality oder Azumas Theorem wird erwahnt???" } @Article{Gil58, author = "B. N. Gilbert", title = "Gray Codes and Paths on the $n$-Cube", journal = "Bell System Technical Journal", year = 1958, month = "May", pages = "815--826", annote = "Wie erhalte ich alle moeglichen Hamiltonpfade durch einen Hyperwuerfel?" } @Article{Gil84, author = "W. J. Gilbert", title = "A Cube filling Hilbert Curve", journal = "The Mathematical Intelligencer", year = 1984, volume = 6, number = 3, pages = 78, annote = "Beziehung Gray-Codes <-> Hilbertkurven" } @Article{KruBab96, author = "P. Krueger and D. Babbar", title = "The Effects of Precedence and Priority Constraints on the Performance of Scan Scheduling for Hypercube Multiprocessors", journal = jpdc, year = 1996, volume = 39, pages = "95--104" } @Manual{Intel97, title = "Intel Archtecture Software Developer's Manual. Volume I: Basic Architecture", organization = "Intel Corporation", address = "P.O. Box 5937, Denver, CO, 80217-9808, \url{http://www.intel.com}", note = "Ordering Number 243190", year = 1997 } @article{Den80, author = {P.J. Denning}, title = {What is experimental computer science?}, journal = {Comm.~ACM}, volume = {23}, number = {10}, year = {1980}, pages = {543--544} } @inproceedings{FiMe97, author = {U. Finkler and K. Mehlhorn}, title = {Runtime prediction of real programs on real machines}, booktitle = {SODA'97}, year = {1997}, pages = {380--389} } @InProceedings{Sch99, author = "Uwe Sch{\"{o}}ning", title = "A Probabilistic Algorithm for $k$-SAT and Constraint Satisfaction Problems", booktitle = "40th IEEE Symposium on Foundations of Computer Science", pages = "410--414", year = 1999 } @InProceedings{MehSch00, author = "K. Mehlhorn and G. Sch{\"a}fer", title = "Implementation of $O(nm \log n)$ weighted matchings: The power of data structures", booktitle = "Workshop on Algorithm Engineering", year = 2000, series = "LNCS", publisher = "Springer", note = "to appear" } @book{FeLeSa77, author = {R.P. Feynman and R.B. Leighton and M. Sands}, title = {The Feynman Lectures on Physics}, publisher = {Addison-Wesley}, edition = {6}, year = {1977} } @article{Den81, author = {P.J. Denning}, title = {Performance analysis : {E}xperimental computer science at its best}, journal = {Comm.~ACM}, volume = {24}, number = {11}, year = {1981}, pages = {725--727} } @Book{Aus01, author = "M. H. Austern", title = "Generic programming and the STL : using and extending the C++ standard template library", publisher = "Addison-Wesley", year = 2001, edition = 7 } Austern, Matthew H.: Generic programming and the STL : using and extending the C++ standard template library. Addison-Wesley professional computing series. 7. print. edition. Addison-Wesley (2001). @Manual{SGI97, title = "Multiprocessing C/C++ Compiler Directives", organization = "SGI", year = 1997, } @Manual{SGI97, title = "Origin2000 Architecture", organization = "SGI", year = 1997, } @Manual{SGI97a, title = "Running Programs under MPI", organization = "SGI", year = 1997, note = "Chapter 11, some Handbook for Origin2000" } @Manual{MIPS96, title = "R10000 Microprocessor User's Manual", organization = "MIPS Technologies, Inc.", edition = "2.0", year = 1998, note = "\url{http://www.mips.com}" } @InProceedings{Kel96, author = "J. Keller", title = "The 21264: A Superscalar Alpha Processor with Out-of-Order Execution", booktitle = "Microprocessor Forum", year = 1996, month = "October" } @Article{BowEtAl95, author = "William J. Bowhill and Shane L. Bell and Bradley J. Benschneider and Andrew J. Black and Sharon M. Britton and Ruben W. Castelino and Dale R. Donchin and John H. Edmondson and Harry R. {Fair, III} and Paul E. Gronowski and Anil K. Jain and Patricia L. Kroesen and Marc E. Lamere and Bruce J. Loughlin and Shekhar Mehta and Robert O. Mueller and Ronald P. Preston and Sribalan Santhanam and Timothy A. Shedd and Michael J. Smith and Stephen C. Thierauf", title = "Circuit Implementation of a {300-MHz} 64-bit Second-generation {CMOS Alpha CPU}", journal = "Digital Technical Journal of Digital Equipment Corporation", volume = "7", number = "1", pages = "100--118", month = "Winter", year = "1995", coden = "DTJOEL", ISSN = "0898-901X", bibdate = "Thu Mar 20 18:15:43 MST 1997", url = "ftp://ftp.digital.com/pub/Digital/info/DTJ/v7n1/Circuit_Implementation_of_a_30_01jul1995DTJH08P8.ps; http://www.digital.com:80/info/DTJH08/DTJH08SC.TXT", abstract = "A 300-MHz, custom 64-bit VLSI, second generation Alpha CPU chip has been developed. The chip was designed in a 0.5-$\mu$m CMOS technology using four levels of metal. The die size is 16.5 mm by 18.1 mm, contains 9.3 million transistors, operates at 3.3 V, and supports 3.3-V\slash 5.0-V interfaces. Power dissipation is 50W. It contains an 8-KB instruction cache; an 8-KB data cache; and a 96-KB unified second-level cache. The chip can issue four instructions per cycle and delivers 1,200 mips/600 MFLOPS (peak). Several noteworthy circuit and implementation techniques were used to attain the target operating frequency. This paper focuses on the circuit implementation of the Alpha 21164 CPU. Some of the significant circuit design challenges encountered during the project are discussed. The paper begins with an introductory overview of the chip microarchitecture. It continues with a description of the floorplan and the physical layout of the chip. The next section discusses the clock distribution and latch design. This is followed by an overview of the circuit design strategy and some specific circuit design examples. The paper concludes with information about design (physical and electrical) verification and CAD tools.", acknowledgement = ack-nhfb, classcodes = "B1265F (Microprocessors and microcomputers); B1130 (General circuit analysis and synthesis methods); C5130 (Microprocessor chips); C7410D (Electronic engineering computing)", classification = "B1130 (General circuit analysis and synthesis methods); B1265F (Microprocessors and microcomputers); C5130 (Microprocessor chips); C7410D (Electronic engineering computing)", keywords = "1200 MIPS; 300 MHz; 600; 600 MFLOPS; 64 Bit; 64 bit; Alpha 21164 CPU; Chip microarchitecture; chip microarchitecture; circuit design; Circuit design; Clock distribution; clock distribution; CMOS Alpha CPU; Floorplan; floorplan; integrated circuit layout; Latch design; latch design; layout; MFLOPS; microprocessor chips; physical; Physical layout; second-generation; Second-generation; VLSI", numericalindex = "Frequency 3.0E+08 Hz; Computer speed 6.0E+08 FLOPS; Computer execution rate 1.2E+09 IPS; Word length 6.4E+01 bit", thesaurus = "Integrated circuit layout; Microprocessor chips", treatment = "P Practical; R Product Review", } @Article{MitDur86, author = "G. Mitchison and R. Durbin", title = "Optimal Numberings of an $N\times N$ Array", journal = "SIAM J. Alg. Disc. Meth.", year = 1986, volume = 7, number = 4, pages = "571--582", annote = "computational geometry Standpunkt. unklar " } @Article{Gol82, author = "L. M. Goldschlager", title = "A universal interconnection pattern for parallel computers", journal = jacm, year = 1982, volume = 29, number = 4, pages = "1073--1086", annote = "Def. von feasible architecture als constant degree network" } @Article{Hil91, author = "D. Hilbert", title = "{\"U}ber die stetige {A}bbildung einer {L}inie auf ein {F}l{\"a}chenst{\"u}ck", journal = "Mathematische Annalen", year = 1891, volume = 38, pages = "459--460" } @Article{Pea90, author = {G. Peano}, title = {Sur une courbe qui remplit toute une aire plane}, journal = {Mathematische Annalen}, volume = {36}, pages = {157--160}, year = {1890} } @Article{Gon98, author = "T. F. Gonzales", title = "Complexity and Approximations for Multimessage Multicasting", journal = jpdc, year = 1998, volume = 55, pages = "215--235", annote = "irregular gossiping, nur interessant wenn die Hardware vervielfaeltigen kann" } @Article{GonEtAl95, author = "A. Gonz{\'a}les", title = "Executing Algorithms with Hypercube Topology on Torus Multicomputers", journal = tpds, year = 1995, volume = 6, number = 8, pages = "803--814", annote = "Referenz auf nichttiviale Einbettung mit kleiner max. Dilation" } @Book{Hwa93, author = "K. Hwang", title = "Advanced Computer Architecture -- Parallelism Scalability Programmability", publisher = "McGraw Hill", year = 1993, annote = "Ausfuer" } @InProceedings{Lei85, author = "C. E. Leiserson", title = "Fat trees: Universal networks for hardware efficient supercomputing", pages = "393--402", booktitle = icpp, year = 1985 } @InProceedings{AAFL96, author = "Baruch Awerbuch and Yossi Azar and Amos Fiat and Tom Leighton", title = "Making Commitments in the Face of Uncertainty: How to Pick a Winner Almost Every Time", pages = "519--530", booktitle = "Proceedings of The Twenty-Eighth Annual {ACM} Symposium On The Theory Of Computing ({STOC} '96)", ISBN = "0-89791-785-5", month = may, publisher = "ACM Press", address = "New York, USA", year = "1996", annote = "application: scheduling background jobs on a NOW. When little is known about future speed or availability. video on demand scheduling, on-line set covering. random assignment weighted using past behavior is better than oblivious assigment" } @InProceedings{ChoEtAl94, author = "F. T. Chong and E. A. Brewer and F. T. Leighton and Knight Jr., T. F.", title = "Building a better butterfly: The multiplexed metabutterfly", booktitle = "International Symposium on Parallel Architectures Algorithms and Networks", year = 1994, address = "Kanazawa, Japan, 14--16 December", annote = "ueberblick expander graphen" } @Book{Lei92, author = "T. Leighton", title = "Introduction to Parallel Algorithms and Architectures", publisher = "Morgan Kaufmann", year = 1992 } @Book{Lei92vorl, author = "T. Leighton", title = "Introduction to Parallel Algorithms and Architectures", publisher = "Morgan Kaufmann", year = 1992, note = "Algorithmen f{\"u}r Verbindungsnetzwerke" } @Book{Mat87, author = "F. Mattern", title = "Verteilte Basisalgorithmen", publisher = "Springer", year = 1987, number = 226, series = "Informatik-Fachberichte" } @Article{Mat87a, author = "F. Mattern", title = "Algorithms for Distributed Termination Detection", journal = "Distributed Computing", year = 1987, volume = 2, pages = "161--175" } @Article{MatMel89, author = "F. Mattern and H. Mehl", title = "{D}iskrete {S}imulation - {P}rinzipien und {P}robleme der {E}ffizienzsteigerung durch {P}arallelisierung", journal = "Informatik Spektrum", year = 1989, volume = 12, pages = "198--210" } @Article{Fuj91, author = "R. Fujimoto", title = "Parallel Discrete Event Simulation", journal = cacm, year = 1990, volume = 33, number = 10, pages = "30--53" } @Unpublished{RADF97, author = "R. R{\"o}nngren and R. Ayani and S. R. Das and R. M. Fujimoto", title = "Efficient Data Structures for Time Warp Event Sets on Shared Memory Systems", annote = "submitted to JPDC Special Issue on Data Structures, priority queue" } @TechReport{MilSto86, author = "R. Miller and Q. F. Stout", title = "Mesh Computer Algorithms for Computational Geometry", institution = "University of Buffalo", year = 1986, number = "86-18", note = "revised", annote = "Computational Geometry. Erste mir bekannte Nutzung von Hilber Kurven (hier als proximity ordering wiedererfunden). Sie wueschen sich einen Sortieralgorithmus auf dem Mesh. Scan ist wichtig. Von Schmeck bekommen. Erwaehnen ein Buch als to appear, das nicht auffindbar ist." } @Book{PreSha85, author = "F. P. Preparata and M. I. Shamos", title = "Computational Geometry", publisher = "Springer", year = 1985 } @TechReport{PruEtAl, author = "P. Prusinkiewicz and A. Lindenmayer and F. D. Fracchia", title = "Synthesis of space-filling curves on the sqare grid", institution = "University of Regina, Saskatchewan", year = 1989, annote = "Einige systematische Konstruktionsregeln" } @Book{PruLin91, author = "P. Prusinkiewicz and A. Lindenmayer", title = "The Algorithmic Beauty of Plants", publisher = "Springer", year = 1991, annote = "3D Hilbertkurve ueber Lindenmeyersystem" } @PhdThesis{Sin93, author = "J. P. Singh", title = "Parallel Hierarchical N-Body Methods and their Implications for Multiprocessors", type = "Ph.D. thesis", school = "Stanford University", year = 1993, annote = ">>Wiedererfindung<< von Hilbertkurven, getrennt gelagert." } @Article{MueRoo94, author = "D. M{\"u}ller-Wichards and W. R{\"o}nsch", title = "Scalability of algorithms: An analystic approch", journal = paco, year = 1995, volume = 21, pages = "937--952", annote = "ziemlich wirr" } @InProceedings{BCFV00, author = "P. Berenbrink and A. Czumaj and T. Friedetzky and N. D. Vvedenskaya", pages = "99--108", title = "On the Analysis of Infinite Parallel Job Allocation Processes via Differential Equations", booktitle = "11th ACM Symposium on Parallel Algorithms and Architectures", year = 2000 } @Article{VDK96, author = "N. D. Vvedenskaya and R. L. Dobrushin and F. I. Karpelevich", title = "Queueing System with Selection of the Shortest of Two Queues: An Asymptotic Approach", journal = "Problems of Information Transmission", year = 1996, volume = 32, number = 1, pages = "15--29" } @PhdThesis{Mit96phd, author = "M. Mitzenmacher", title = "The Power of Two Choices in Randomized Load Balancing", school = "UC Berkeley", year = 1996 } @InCollection{MitRicSit00, author = "M. Mitzenmacher and A. Richa and R. Sitaraman", title = "The power of two random choices: A survey of the techniques and results", booktitle = "Handbook of Randomized Computing", publisher = "Kluwer", year = 2000, editor = "P. Pardalos and S. Rajasekaran and J. Rolim" } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Randomisierte Parallele Algorithmen allgemein @InProceedings{Mit98, author = "M. Mitzenmacher", title = "Analyses of Load Stealing Models Based on Differential Equations", pages = "212--221", booktitle = "10th ACM Symposium on Parallel Algorithms and Architectures", year = 1998 } @InProceedings{ABS98, author = "M. Adler and P. Berenbrink and K. Schr{\"o}der", title = "Analyzing an Infinite Parallel Job Allocation Process", booktitle = "6th European Symposium on Algorithms", pages = "417--428", year = 1998, number = 1461, series = "LNCS", publisher = "Springer" } @InProceedings{MFCS::AdlerBK1995, title = "Scheduling Parallel Communication: The {$h$}-relation Problem", author = "Micah Adler and John W. Byers and Richard M. Karp", editor = "Jir{\'\i} Wiedermann and Petr H{\'a}jek", booktitle = "Mathematical Foundations of Computer Science 1995, 20th International Symposium", address = "Prague, Czech Republic", month = "1~" # sep # "-- 28~" # aug, year = 1995, series = "lncs", volume = 969, publisher = "Springer", pages = "1--20", annote = "abstraktion fuer all-to-all" } @InProceedings{BarFra97, author = "Dominique Barth and Pierre Fraigniaud", title = "Approximation Algorithms for Structured Communication Problems", booktitle = "Proceedings of the 9th Annual {ACM} Symposium on Parallel Algorithms and Architectures", address = "Newport, Rhode Island", organization = "SIGACT/SIGARCH and EATCS", month = jun # " 22--25,", year = "1997", pages = "180--188", annote = "recht allgemeiner Ansatz fuer beliebige Netzwerke. telephone model, d.h. duplex mit einem Partner. Ergebnisse via simulation anderer Algorithmen. Eine runde kostet O(edge congestion + dilation)" } @InProceedings{AdlEtAl95, author = "M. Adler and S. Chakrabarti and M. Mitzenmacher and L. Rasmussen", title = "Parallel Randomized Load Balancing", booktitle = "ACM Symposium on the Theory of Computing", year = 1995, annote = "Randomisiertes Lastverteilen mit geringen Abweichungen durch wiederholtes zufaelliges Plazieren. Bringts nur fuer lange Nachrichten. Ergebins aus zitiertem paper koennte R. Luelings Problem des zufaelligen plazierens loesen. RDA, random allocation" } @InProceedings{Mit96, author = "Michael Mitzenmacher", title = "{Load balancing and density dependent jump Markov processes}", booktitle = "Proceedings of 37th Conference on Foundations of Computer Science", year = "1996", month = oct, pages = "213--222", keyword = "scheduling, load balance, random", abstract = "We provide a new approach for analyzing both static and dynamic randomized load balancing strategies. We demonstrate the approach by providing the first analysis of the following model: customers arrive as a Poisson stream of rate lambda /sub n/, lambda <1, at a collection of n servers. Each customer chooses some constant d servers independently and uniformly at random from the n servers, and waits for service at the one with the fewest customers. Customers are served according to the first-in first-out (FIFO) protocol, and the service time for a customer is exponentially distributed with mean 1. We call this problem the supermarket model. We wish to know how the system behaves, and in particular we are interested in the expected time a customer spends in the system in equilibrium. The model provides a good abstraction of a simple, efficient load balancing scheme in the setting where jobs arrive at a large system of parallel processors. This model appears more realistic than similar models studied previously, in that it is both dynamic and open: that is, customers arrive over time, and the number of customers is not fixed.", } @InProceedings{CFMMRSU98, author = "R. Cole and A. Frieze and B. M. Maggs and M. Mitzenmacher and A. W. Richa and R. K. Sitaraman and E. Upfal", title = "On balls and bins with deletions", booktitle = "2nd RANDOM", pages = "145--158", year = 1998, volume = 1518, series = "LNCS", publisher = "Springer" } @InProceedings{Scott91a, author = "David S. Scott", title = "Efficient All-to-All Communication Patterns in Hypercube and Mesh Topologies", booktitle = "Sixth Distributed Memory Computing Conference Proceedings", pages = "398--403", publisher = "IEEE", address = "Portland, OR", month = apr, year = "1991", keywords = "DMCC6, computation and algorithms, communication, Direct Exchange algorithms for Complete Exchange,", } @Article{Bruck:1997:EAA, author = "J. Bruck and Ching-Tien Ho and S. Kipnis and E. Upfal and D. Weathersby", title = "Efficient Algorithms for All-to-All Communications in Multiport Message-Passing Systems", journal = "IEEE Transactions on Parallel and Distributed Systems", volume = "8", number = "11", pages = "1143--1156", month = nov, year = "1997", coden = "ITDSEO", ISSN = "1045-9219", bibdate = "Fri Nov 6 12:31:15 MST 1998", url = "http://www.computer.org/tpds/td1997/l1143abs.htm; http://dlib.computer.org/td/books/td1997/pdf/l1143.pdf", acknowledgement = ack-nhfb, classification = "C4230 (Switching theory); C4240C (Computational complexity); C4240P (Parallel programming and algorithm theory); C5220P (Parallel architecture)", corpsource = "California Inst. of Technol., Pasadena, CA, USA", keywords = "all-to-all communications; communication bandwidth; communication complexity; communication start-up; complexity measures; concatenation; index; message passing; message-passing systems; multiport; parallel algorithms; point-to-point communication; sender-receiver pair", treatment = "T Theoretical or Mathematical", } @Article{WBPM97, author = "X. Wang and E. K. Blum and D. S. Parker and D. Massey", title = "The dance party problem and its application to collective communication in computer networks", journal = "Parallel Computing", year = 1997, volume = 23, number = 8, pages = "1141--1156" } @Article{HamHamKho95, author = "S. E. Hambrusch and F. Hameed and A. A. Khokar", title = "Communication Operations on coarse-grained mesh architectures", journal = "Parallel Computing", year = 1995, volume = 21, pages = "731--751", annote = "balanciertes all-to-all. benutzen one-factors" } @Article{AieEtAl91, author = "Aiello and Leighton and Maggs and Newman", title = "Fast Algorithms for Bit-Serial Routing on a Hypercube", journal = "Mathematical Systems Theory", volume = "24", pages = "253--271", year = "1991", abstract = "In this paper we describe an $O(\log N)$ bit-step randomized algorithm for bit-serial message routing on a hypercube. The result is asymptotically optimal, and improves upon the best previously known algorithms by a logarithmic factor. The result also solves the problem of on-line circuit switching in an $O(1)$-dilated hypercube (i.e., the problem of establishing edge-disjoint paths between the nodes of the dilated hypercube for any one-to-one mapping). Our algorithm is adaptive and we show that this is necessary to achieve the logarithmic speedup. We generalize the Borodin-Hopcroft lower bound on oblivious routing by proving that any randomized oblivious algorithm on a polylogarithmic degree network requires at least $\Omega(\log^2 N / \log\log N)$ bit steps with high probability for almost all permutations.", note = "Appeared also in 2nd Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA 90)", annote = "Laut Alf laesst sich dieser Alg verwursten um T_req = O(max(log n, s(w))) fuer random polling zu erreichen." } @InProceedings{AuEtAl95, author = "V. Auletta and A. Negro and V. Scarano", title = "Fast Execution of Irregularly Structured Programs with Low Communication Frequency on the Hypercube", series = "LNCS", number = 980, booktitle = "Workshop on Algorithms for Irregularly Structured Problems", year = 1995, publisher = "Springer", address = "Lyon", annote = "Auch in ausfuehrlicher Variante. Ebenfalls fuer Special Issue TCS eingereicht" } @InProceedings{BlaRan93, author = "C. T. Blackston and A. Ranade", title = "{SnakeSort}: A Family of Simple Optimal Randomized Sorting Algorithms", number = "III", pages = "201--204", booktitle = "International Conference on Parallel Processing", year = 1993, address = "Boca Raton", annote = "Naive Algorithmen funktionieren mhw gut wenn nur genug Daten pro PE vorhanden, randomisiertes 01 Sortierlemma. " } @TechReport{BlaRan94, author = "D. T. Blackston and A. Ranade", title = "{SnakeSort}: A Family of Simple Optimal Randomized Sorting Algorithms", institution = "University of California Berkeley", year = 1994, annote = "Vollversion des Konferenzpapiers" } @Article{BluLei99, author = "R. D. Blumofe and C. E. Leiserson", title = "Scheduling multithreaded computations by work stealing", journal = "Journal of the ACM", volume = "46", number = "5", pages = "720--748", year = "1999", } @InProceedings{AroBluPla98, author = "N. S. Arora and R. D. Blumofe and C. G. Plaxton", title = "Thread Scheduling for Multiprogrammed Multiprocessors", pages = "119--129", address = "Puerto Vallarta, Mexico, June 28--July 2", publisher = "ACM, New York", booktitle = "10th ACM Symposium on Parallel Algorithms and Architectures", year = 1998 } @InProceedings{BluEtAl95, author = "R. D. Blumofe and C. Joerg and B. C. Kuszmaul and C. E. Leiserson and K. H. Randall and Y. Zhou", title = "Cilk: An Efficient Multithreaded Runtime System", pages = "207--216", booktitle = "Principles and Practice of Parallel Programming (PPoPP)", year = 1995, annote = "Anwendungen im wesentlichen Baumsuche.", address = "Santa Barbara, CA, 19--21 July", publisher = "ACM New York", } @InProceedings{BluEtAl96, author = "R. D. Blumofe and M. Frigo and C. F. Joerg and C. E. Leiserson and K. H. Randall", title = "An Analysis of Dag-Consistent Distributed Shared-Memory Algorithms", booktitle = "8th ACM Symposium on Parallel Algorithms and Architectures", year = 1996, pages = "297--308", address = "Padua, Italy, 24--26 June", publisher = "ACM, New York", } @InProceedings{Preis99, author = "Preis", title = "Linear Time $1/2$-Approximation Algorithm for Maximum Weighted Matching in General Graphs", booktitle = "Proc. 16th Ann. Symp. on Theoretical Aspects of Computer Science (STACS), LNCS 1563", year = "1999", pages = "259--269", } @Article{DH03a, author = "D. Drake and S. Hougardy", title = "A Simple Approximation Algorithm for the Weighted Matching Problem", journal = IPL, volume = "85", pages = "211--213", year = "2003", } @InProceedings{DH03b, author = "D. Drake and S. Hougardy", title = "Linear Time Local Improvements for Weighted Matchings in Graphs", booktitle = "International Workshop on Experimental and Efficient Algorithms (WEA), LNCS 2647", pages = "107--119", year = "2003", } @InProceedings{DH03c, author = "D. Drake and S. Hougardy", title = "Improved Linear Time Approximation Algorithms for Weighted Matchings", booktitle = "7th International Workshop on Randomization and Approximation Techniques in Computer Science (APPROX), LNCS 2764", pages = "14--23", year = "2003", } @techreport{PS04-tr, year = "2004", type = "Technical Report", number = "MPI-2-2004-1-002", institution = "Max Planck Institute for Computer Science", title = "A Simpler Linear Time {$2/3 - \epsilon$} Approximation for Maximum Weight Matching", bibdate = feb, author = "S. Pettie and P. Sanders", } @InProceedings{FLPR99, author = "M. Frigo and C. E. Leiserson and H. Prokop and S. Ramachandran", title = "Cache-Oblivious Algorithms", booktitle = "40th Symposium on Foundations of Computer Science", year = 1999, pages = "285--298" } @InProceedings{SenCha00, author = "S. Sen and S. Chatterjee", title = "Towards a Theory of Cache-Efficient Algorithms", booktitle = "11th ACM Symposium of Discrete Algorithms", pages = "829--838", year = 2000 } @Article{ZhiHer01, author = "V. V. Zhirnov and D. J. C. Herr", title = "New Frontiers: Self-Assembly and Nanoelectronics", journal = "IEEE Computer", year = 2001, volume = 34, number = 1, pages = "34--43" } @Unpublished{Tec00, author = "Lucent Technologies", title = "High Density Holographic Data Storage", note = "{\url{http://www.bell-labs.com/org/physicalsciences/projects/hdhds/1.html}}", year = 2000 } @InProceedings{BL94, author = "R. D. Blumofe and C. E. Leiserson", title = "Scheduling Multithreaded Computations by Work Stealing", booktitle = focs, pages = "356--368", address = "Santa Fe, NM, 20--22 November", publisher = "IEEE, Los Alamitos, CA", year = 1994 } @PhdThesis{Blu95, author = "R. D. Blumofe", title = "Executing Multithreaded Programs Efficiently", type = "Ph.D. thesis", school = "MIT", year = 1995 } @TechReport{BluEtAl94, author = "R. D. Blumofe and M. Halbherr and C. F. Joerg and B. C. Kuszmaul and C. E. Leiserson and P. Lisiecki and K. H. Randall and A. Shaw and Y. Zhou", title = "Cilk 1.1 Reference Manual", institution = "MIT", year = 1994, month = "September", annote = "vom WWW server. Interessanterweise deckt sich die Funktionalitaet nicht ganz mit dem Paper. Aber es gibt Beispiele, (Accus), bei denen der Fehler in der Analyse durchschlagen sollte." } @InCollection{ArgBro99, Year = 1999, Title = {On Showing Lower Bounds for External-Memory Computational Geometry Problems}, Annote = {In this paper, we consider lower bounds for external-memory computational geometry problems. We find that it is not quite clear which model of computation to use when considering such problems.}, Address = {Providence, RI}, Checked = {20020228jv}, Series = {{DIMACS} Series in Discrete Mathematics and Theoretical Computer Science}, Pages = {139--159}, Booktitle = {External Memory Algorithmss}, Publisher = {American Mathematical Society}, Author = {L. Arge and Bro Miltersen, P.}, Volume = 50} @InProceedings{Arg93, title = "A General Lower Bound on the {I/O}-Complexity of Comparison-based Algorithms", author = "Lars Arge and Mikael Knudsen and Kirsten Larsen", booktitle = "Algorithms and Data Structures, Third Workshop", editor = "Frank K. H. A. Dehne and J{\"o}rg-R{\"u}diger Sack and Nicola Santoro and Sue Whitesides", address = "Montr{\'e}al, Canada", month = "11--13~" # aug, year = "1993", series = "Lecture Notes in Computer Science", volume = "709", publisher = "Springer", ISBN = "ISBN 3-540-57155-8", pages = "83--94", } @PhdThesis{Arg96, author = "L. Arge", title = "Efficient External-Memory Data Structures and Applications", school = "University of Aarhus", year = 1996 } @InProceedings{ArgSamVit99, author = "L. Arge and V. Damoladas and J. S. Vitter", title = "On Two-Dimensional Indexability and Optimal Range Search Indexing", pages = "346--357", booktitle = "PODS", year = 1999, annote = "Lars hat hier drueber vorgetragen" } @Manual{Ven95, title = "{TPIE} User Manual and Reference", author = "D. E. Vengroff", organization = "Duke University", year = 1995, note = "\url{http://www.cs.duke.edu/~dev/tpie_home_page.html}" } @InProceedings{Arg95, author = "L. Arge", title = "{The Buffer Tree: A New Technique for Optimal I/O-Algorithms}", number = 955, series = "LNCS", pages = "334--345", booktitle = "4th Workshop on Algorithms and Data Structures", year = 1995, publisher = "Springer" } @InProceedings{Arg95www, author = "L. Arge", title = "The Buffer Tree: {A} New Technique for Optimal {I/O}-Algorithms", number = 955, series = "LNCS", pages = "334--345", booktitle = "4th WADS", year = 1995, note = "\htmladdnormallink{long version}{Arg95b.ps.gz}", publisher = "Springer" } @PhdThesis{NorbertThesis, author = "N. Zeh", title = "{I/O}-Efficient Algorithms for Shortest Path Related Problems", school = "Carleton University", year = 2002, address = "Ottawa, Canada" } @TechReport{WW03, author = "M. Wattenhofer and R. Wattenhofer", title = "Distributed Weighted Matching", institution = "ETH Z{\"{u}}rich", year = 2003, number = 420, note = "{\url{http://www.inf.ethz.ch/research/publications/data/tech-reports/4xx/420.ps}}" } @InProceedings{UehChe00, author = "Uehara and Chen", title = "Parallel Approximation Algorithms for Maximum Weighted Matching in General Graphs", booktitle = "IFIPTCS: IFIP International Conference on Theoretical Computer Science, LNCS", year = "2000", } @TechReport{KanMor02, author = "K. Kanemura and E. Moriya", title = "Parallel Approximation Algorithms and Average-Time Analysis for Maximum Weighted Matching in General Graphs", institution = "Advanced Research Institute for Science and Engineering", year = 2002, number = 3, comment = "average case, logDelta average time on EREW, linear work", address = "Waseda Univertiy, Japan", note = "{\url{http://www.rise.waseda.ac.jp/tech_repo/2002/03_e.html}}" } @InProceedings{GZ03, author = "B. Goethals and M. J. Zaki", title = "FIMI 03: Workshop on Frequent Itemset Mining Implementations", booktitle = " ", year = 2003, annote = "contains measurements on implementations" } @InProceedings{Goe04, author = "B. Goethals", title = "Memory Issues in Frequent Itemset Mining", booktitle = "SAC", year = 2004 } @TechReport{BFMZ04, author = "G. S. Brodal and R. Fagerberg and N. Zeh", title = "Cache-Oblivious Data Structures and Algorithms for Undirected Breadth-First Search and Shortest Paths", institution = "brics", year = 2004, number = "RS-04-2" } @InProceedings{ABT00, author = "L. Arge and G. Brodal and L. Toma", title = "On External Memory {MST}, {SSSP} and Multi-way Planar Graph Separation", booktitle = "7th Scandinavian Workshop on Algorithm Theory", pages = "433--447", year = 2000, volume = 1851, series = "LNCS", publisher = "Springer" } @InProceedings{BroKat98, author = "Gerth St{\o}lting Brodal and Jyrki Katajainen", booktitle = "6th Scandinavian Workshop on Algorithm Theory", publisher = "Springer {V}erlag, Berlin", number = 1432, pages = "107--118", series = "LNCS", title = "Worst-Case Efficient External-Memory Priority Queues", year = 1998 } @Article{WegTeu89, author = "L. M. Wegner and J. I. Teuhola", title = "The External Heapsort", journal = "IEEE Transactions on Software Engineering", year = 1989, volume = 15, number = 7, pages = "9--925", month = "July" } @Unpublished{Crau99, author = "A. Crauser", title = "Introduction to Magnetic Disc Drives", note = "SIG talk", year = 1999 } @Unpublished{CraFerMey97, author = "A. Crauser and P. Ferragina and U. Meyer", title = "Efficient Priority Queues in External Memory", note = "working paper", year = 1997, month = "October" } @InProceedings{KWCLC99, author = "S. Kuo and M. Winslett and Y. Cho and J. Lee and Y. Chen", title = "Efficient Input and Output for Scientific Simulations", pages = "33--44", booktitle = "IOPADS", year = 1999, annote = "Hilbertkurven fuer rectangular range queries bleibt hiner AsaEtAl95 zurueck?" } @InProceedings{AtaPra00, author = "Mikhail J. Atallah and Sunil Prabhakar", title = "(Almost) Optimal Parallel Block Access for Range Queries.", pages = "205--215", booktitle = "Proceedings of the Nineteenth {ACM} {SIGMOD}-{SIGACT}-{SIGART} Symposium on Principles of Database Systems ({PODS}-00)", month = may # "~15--17", publisher = "ACM Press", address = "N. Y.", year = "2000", annote = "Spezialfall von SanEgnKor00? Schlechtere bounds" } @Article{YanWan00, author = "Y. Yang and J. Wang", title = "Optimal All-to-All Personalized Exchange in Self-Routable Multistage Networks", journal = "IEEE Transactions on Parallel and Distributed Systems", volume = 11, number = 3, pages = "261--274", month = mar, year = 2000, coden = "ITDSEO", ISSN = "1045-9219", bibdate = "Thu Oct 12 18:48:32 MDT 2000", url = "http://www.computer.org/tpds/td2000/l0261abs.htm; http://dlib.computer.org/td/books/td2000/pdf/l0261.pdf", acknowledgement = ack-nhfb, } @InProceedings{ZWCL99, author = "Y. Zhou and L. Wang and D. W. Clark and K. Li", title = "Thread Scheduling for Our-of-Core Applications with Memory Server on Multicomputers", pages = "57--67", booktitle = "IOPADS", year = 1999, annote = "Speicher der anderen PEs als paging memory benutzen" } @InProceedings{AAK99, author = "S. Albers and S. Arora and S. Khanna", title = "Page replacement for general caching problems", booktitle = "10th ACM-SIAM Symposium Discrete Algorithms", pages = "31-40", year = 1999, annote = "variable page sizes" } @InProceedings{AlbBut03, author = "S. Albers and M. B{\"u}ttner", title = "Integrated Prefetching and Caching in Single and Parallel Disk Systems", booktitle = "15th ACM Symposium on Parallel Algorithms and Architectures", pages = "109--117", year = 2003 } @InProceedings{AlbGarLeo98, author = "S. Albers and N. Garg and S. Leonardi", title = "Minimizing Stall Time in Single and Parallel Disk Systems", pages = "454--462", ISBN = "0-89791-962-9", booktitle = "Proceedings of the 30th Annual {ACM} Symposium on Theory of Computing ({STOC}-98)", month = may # "~23--26", publisher = "ACM Press", address = "New York", year = "1998", } @Article{BlaKit91, author = "I. F. Blake and K. Kith", title = "On the Complet Weight Enumerator of Reed-Solomon Codes", journal = "SIAM Journal on Discrete Mathemtics", year = "1991", OPTkey = "", OPTvolume = "4", OPTnumber = "2", OPTpages = "164--181", OPTmonth = "", OPTnote = "", OPTannote = "" } @InProceedings{PSV92, author = "V. S. Pai and A. S. Schaeffer and P. J. Varman", title = "Markov Analysis of Multipe-Disk Prefetching Strategies for External Merging", booktitle = "ICPP", year = 1992, annote = "applied to external merge sort" } @InProceedings{PaiVar92, author = "V. S. Pai and P. J. Varman", title = "Prefetching with Multiple Disks for External Mergesort: Simulation and Analysis", booktitle = "ICDE", pages = "273--282", year = 1992 } @InProceedings{ErtKalVar00, author = "{\"O}. Ertug and M. Kallahalla and P. J. Varman", title = "Real Time Parallel Disk Scheduling for VBR Video Servers", booktitle = "CSI", year = 2000, address = "Chennai, India", note = "{\url{http://www.ece.rice.edu/~kalla/}}" } @inproceedings{KalVar01, author = {M. Kallahalla and P. J. Varman}, title = {Optimal prefetching and caching for parallel {I/O} systems}, booktitle = "13th Symposium on Parallel Algorithms and Architectures", pages = "219--228", year = 2001, } @Article{KalVar02, author = "M. Kallahalla and P. J. Varman", title = "{PC-OPT}: Optimal Offline Prefetching and Caching for Parallel {I/O} Systems", journal = "IEEE Transactions on Computers", year = 2002, number = 11, volume = 51, pages = "1333--1344" } @InProceedings{KalVar99, author = "M. Kallahalla and P. J. Varman", title = "Optimal Read-Once Parallel Disk Scheduling", pages = "68--77", booktitle = "6th Workshop on Input/Output in Parallel and Distributed Systems", year = 1999, annote = "no caches offline" } @Article{KWGH02, author = "S. Kirkpatrick and W. Wilcke and R. Garner and H. Huels", title = "Percolation in Storage Arrays", journal = "Physica A", year = 2002, note = "to appear", annote = "wann faellt das Ice Cube system aus?" } @InProceedings{MalSoi, author = "L. Malmi and E. Soisalon-Soininen", title = "Group Updates for Relaxed Height-Balanced Trees", pages = "358--367", booktitle = "PODS", year = 1999 } @Unpublished{LeuTsaTan99, author = "F. C. Leu and Y. T. Tsai and C. Y. Tang", title = "An Efficient External Sorting Algorithm", note = "two pass", year = 1999 } @InProceedings{BGHMSV99, author = "R. Barve and P. B. Gibbons and B. K. Hillyer and Y. Matias and E. Shriver and J. S. Vitter", title = "Round-like behavior in multiple disks on a bus", pages = "1--10", booktitle = "IOPADS", year = 1999, annote = "SCSI bus cannot be saturated with independent random accesses. No explanation!" } @InProceedings{SVV04, author = "R. Shah and P. J. Varman and J. S. Vitter", title = "Online algorithms for prefetching and caching on parallel disks", booktitle = "16th ACM Symposium on Parallel Algorithms and Architectures", pages = "255--264", year = 2004 } @InProceedings{BarVit99, author = "R. D. Barve and J. S. Vitter", title = "A Simple and Efficient Parallel Disk Merge Sort", booktitle = "11th ACM Symposium on Parallel Algorithms and Architectures", pages = "232--241", year = 1999 } @Article{BarGroVit97, author = "R. D. Barve and E. F. Grove and J. S. Vitter", title = "Simple Randomized Mergesort on Parallel Disks", journal = "Parallel Computing", year = 1997, volume = 23, number = 4, pages = "601--631", annote = "auch TR CS-1996-15, Duke" } @InProceedings{FJKT97, author = "R. Fadel and K. V. Jakobsen and J. Katajainen and J. Teuhola", title = "External heaps combined with effective buffering", volume = "19-2", series = "Australian Computer Science Communications", pages = "72--78", booktitle = "4th Australasian Theory Symposium", year = 1997, publisher = "Springer" } @InProceedings{AACHP97, author = "A. C. Arpaci-Dusseau et al.", title = "High-Performance Sorting on Networks of Workstations", pages = "243--254", booktitle = "{ACM} {SIGMOD}", series = "SIGMOD Record", volume = "26,2", year = "1997", } @InProceedings{HZ04, author = "N. J. A. Harvey and K. Zatloukal", title = "The Post-Order Heap", booktitle = "FUN with Algorithms", year = 2004, annote = "priority queue with O(1) amortized insert" } @InProceedings{GZ03, author = "J. Gao and L. Zhang", title = "Well-Separated Pair Decomposition for the Unit-Disk Graph Metric and its Applications", booktitle = "STOC", pages = "483--492", year = 2003 } @InProceedings{SVV04, author = "R. Shah and P. J. Varman and J. S. Vitter", title = "Online Algorithms for Prefetching and Caching on Parallel Disks", booktitle = "SPAA", year = 2004 } @Article{VarEtAl91, author = "Peter J. Varman and Scott D. Scheufler and Balakrishna R. Iyer and Gary R. Ricard", title = "Merging Multiple Lists on Hierarchical-Memory Multiprocessors", journal = "J. Par. {\&} Dist. Comp.", volume = "12", number = "2", pages = "171--177", year = "1991", coden = "JPDCER", ISSN = "0743-7315", bibdate = "Sat Apr 12 17:13:17 MDT 1997", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory)", corpsource = "Dept. of Electr. and Comput. Eng., Rice Univ., Houston, TX, USA", keywords = "computational complexity; data access costs; hierarchical-memory multiprocessors; merging lists; multiprocessor algorithm; multiway merging; parallel algorithms; partitioning algorithm; Sequent symmetry multiprocessor; sorted lists; time complexity", treatment = "T Theoretical or Mathematical", } @InProceedings{BFV04, author = "G. S. Brodal and R. Fagerberg and K. Vinther", title = "Engineering a Cache-Oblivious Sorting Algorithm", booktitle = "6th Workshop on Algorithm Engineering and Experiments", year = 2004 } @InProceedings{Tho03, author = "M. Thorup", title = "Integer priority queues with decrease key in constant time and the single source shortest paths problem", booktitle = "35th {ACM} Symposium on Theory of Computing", pages = "149--158", year = 2004 } @InProceedings{MTTZ04, author = "R. Mendelson and R. E. Tarjan, M. Thorup, U. Zwick", title = "Melding Priority Queues", booktitle = "9th Scandinavian Workshop on Algorithm Theory", pages = "223--235", year = 2004 } @InProceedings{HanTho02, author = "Y. Han, M. Thorup", title = "Integer Sorting in {$\Oh{n \sqrt{\log\log n}}$} Expected Time and Linear Space", booktitle = "42nd Symposium on Foundations of Computer Science", pages = "135--144", year = 2002 } @InProceedings{Bro96, author = "G. S. Brodal", title = "Priority Queues on Parallel Machines", booktitle = "5th Scandinavian Workshop on Algorithm Theory", number = 1097, series = "LNCS", year = 1996, publisher = "Springer", pages = "416--427" } @INCOLLECTION{Bro97, title = "Predecessor Queries in Dynamic Integer Sets", author = "G. S. Brodal", booktitle = "Proc. 14th Symposium on Theoretical Aspects of Computer Science", series = "Lecture Notes in Computer Science", number = "1200", publisher = "Springer {V}erlag, Berlin", pages = "21-32", year = "1997" } @InProceedings{BroEtAl97, author = "G. S. Brodal and J. L. Tr{\"a}ff and C. D. Zaroliagis", title = "A Parallel Priority Data Structure with Applications", booktitle = "11th International Parallel Processing Symposium", year = 1997, note = "to appear" } @Article{BroTraZar98, author = "G. S. Brodal and C. D. Zaroliagis and J. L. Tr{\"a}ff", title = "A Parallel Priority Data Structure with Applications", journal = "Journal Parallel and Distributed Processing, Special Issue on Parallel and Distributed Data Structures", year = 1998, volume = 49, number = 1, pages = "4--21", } @Article{BroTraZar98this, author = "G. S. Brodal and J. L. Tr{\"a}ff and C. D. Zaroliagis", title = "A Parallel Priority Data Structure with Applications", journal = jpdc, year = 1998, note = "This issue" } @Unpublished{BroEtAl97b, author = "G. S. Brodal and J. L. Tr{\"a}ff and C. D. Zaroliagis", title = "A Parallel Priority Queue with Constant Time Operations", note = "MPII", annote = "taucht in seiner Veroeffentlichungsliste nicht auf??" } @InProceedings{Che94, author = "J. Chen", title = "Parallel Heap Construction Using Multiple Selection", pages = "371--380", booktitle = "{CONPAR} {VAPP}", year = 1994, publisher = "Springer", annote = "CRCW; Wozu brauche ich heap construction?" } @InProceedings{ChiEtAl94, author = "D. D. Chinn and T. Leighton and M. Tompa", title = "Minimal Adaptive Routing on the Mesh with Bounded Queue Size", pages = "354--363", booktitle = spaa, year = 1994, address = "Cape May, New Jersey", annote = "Untere Schranken fur einfache Algorithmen" } @InProceedings{DeoPra90, author = "N. Deo and S. Prasad", title = "Parallel Heap", volume = "III", pages = "169--172", booktitle = "International Conference on Parallel Processing", year = 1990, annote = "EREW PRAM Frage: geht es nicht trivial auf Verbindungsnetzwerken?" } @Article{DeoPra92, author = "N. Deo and S. Prasad", title = "Parallel Heap: An Optimal Parallel Priority Queue", journal = "The Journal of Supercomputing", volume = "6", number = "1", pages = "87--98", month = mar, year = "1992", keywords = "parallel data structure, heaps, priority queue, optimal parallel algorithm, parallel random access machine, PRAM,", } @Article{OlaWen91, author = "S. Olariu and Z. Wen", title = "Optimal Parallel Initialization Algorithms for a Class of Priority Queues", journal = "IEEE Transactions on Parallel and Distributed Systems", year = 1991, volume = 2, number = 4, pages = "423--429", month = "October" } @TechReport{PinPuc91, author = "M. C. Pinotti and G Pucci", title = "Parallel Priority Queues", institution = "ICSI", year = 1991, number = "91-016", address = "Berkeley", annote = "Kennen Prasad Deo nicht. CREW, loeschen schneller, einfuegen gleich schnell. Benutzt Merge des neuen Knotens mit dem ganzen Pfad bis zur Wurzel. Deutlich einfacher als Prasad Deo.Es sieht so aus, als koennte man das ganze auch auf EREW wenn man loeschen so langsam macht wie einfuegen? Ein zusaetlicher loglog n Faktor ermoeglicht dann das ganze auf dem HC? (Leighton S. 642). Problem, wie kann man eine n log n und eine n sortierte Folge moeglichst schnell mergen?" } @TechReport{DasEtAl94, author = "S. K. Das and M. C. Pinotti and F. Sarkar", title = "Optimal Parallel Priority Queues in Distributed Memory Hypercubes", institution = "University of North Texas", year = 1994, number = "CRPDC-94-23", address = "Denton", month = "December" } @Article{DasPinSar96, author = "S. K. Das and M. C. Pinotti and F. Sarkar", title = "Optimal and Load Balanced Mapping of Parallel Priority Queues in Hypercubes", journal = tpds, year = 1996, volume = 7, number = 6, pages = "555--564", annote = "der Tr von Dez. 94, revised Nov. 95" } @InProceedings{DasPra94, author = "S. K. Das and F. Sarkar and S. K. Prasad", title = "Dynamic Load Balancing Algorithms for Optimistic Parallel Discrete Event Simulation", booktitle = "??", year = 1994, pages = "91--97", annote = "Keine PPQs" } @Article{PinPuc95, author = "M. C. Pinotti and G. Pucci", title = "Parallel algorithms for priority queue operation", journal = "Theoretical Computer Science", year = 1995, volume = 148, pages = "171--180", annote = "ein einzelnes Element so schnell wie moeglich rausholen" } @InProceedings{DasEtAl95, author = "S. K. Das and M. C. Pinotti and F. Sarkar", title = "Conflict-Free Path Access of Trees in Parallel Memory Systems With Applications to Distributed Heap Implementation", booktitle = icpp, year = 1995 } @InProceedings{RanEtAl94, author = "A. Ranade and S. Cheng and E. Deprit and J. Jones and S. Shih", title = "Parallelism and Locality in Priority Queues", pages = "97--103", booktitle = "Sixth IEEE Symposium on Parallel and Distributed Processing", year = 1994, month = "October", annote = "meshes" } @Article{DiaGraMor90, author = "P. Diaconis and R. L. Graham and J. A. Morrison", title = "Asymptotic Analysis of a Random Walk on a Hypercube with Many Dimensions", journal = "Random Structures and Algorithms", year = 1990, volume = 1, number = 1, pages = "51--72", annote = "Tbal in O(log n loglog n)" } @Article{DiaGra92, author = "P. Diaconis and R. L. Graham", title = "An affine walk on the hypercube", journal = "Computational and Applied Mathematics", year = 1992, volume = 41, pages = "215--235" } @InProceedings{GuPho94, author = "A. K. Gupta and A. G. Phoutiou", title = "Load Balanced Priority Queue Implementations on Distributed Memory Parallel Machines", number = 817, series = "LNCS", pages = "689--700", booktitle = "Sixth International Conference on Parallel Architectures and Languages Europe", year = 1994, publisher = "Springer", address = "Athens", month = "July" } @InProceedings{DonEtAl96, author = "E. de Doncker and P. Ealy and A. Gupta", title = "Two Methods for Load Balanced Distributed Adaptive Integration", pages = "562--570", booktitle = "HPCN Europe", year = 1996, OPTaddress = "Br{\"u}ssel", annote = "Interessante Anwendung fuer parallele priority queue" } @InProceedings{Man95, author = "B. Mans", title = "Portable Distributed Priority Queues with MPI", booktitle = "International Conference on High Performance Computing", year = 1995, annote = "Bettet PE Baum ein => hot spot T3D impl. Branch and bound als Testanwendung. Event set Anwendungsmodell: Queue anfangs voll. Jedes PE entnimmt elemnt und fuegt zufaelliges neues ein. Leider wird nicht ganz verraten was gemessen wird. Gesamtdurchsatz sinkt mit Anzahl PEs !" } @InProceedings{DioEtAl94, author = "M. Dion and M. Gengler and S. Ubeda", title = "Comparing two Probabilistic Models of the Computational Complexity of the Branch and Bound Algorithm", pages = "359--370", booktitle = "{CONPAR/VAPP}", year = 1994, publisher = "Springer", address = "Linz", annote = "modelliere Differenzen zwischen Knotenschranken als identisch verteilte unabh ZVA. Dann wird magisch diskretiesiert und es stellt sich heraus, das die Anzahl Knoten mit gleicher Bewertung exponentiell mit der Suchbaumtiefe waechst. B&B nutzt das aus indem nur Knoten mit gleicher Bewertung parallel expandiert werden. Die Leute scheinen noch nie von IDA* gehoert zu haben. (waere wohl oft effizienter). Die herleitungen scheinen Fehler zu enthalten." } @InProceedings{DG96, author = "C. G. Diderich and M. Gengler", title = "Solving Traveling Salesman Problems Using a Parallel Synchronized Branch and Bound Algorithm", pages = "633--638", booktitle = "HPCN Europe", year = 1996, address = "Br{\"u}ssel", annote = "bis zu 256 PEs, schlecht, aehnlicher seq. Ansatz wie Paderborner, LV wie gehabt" } @InProceedings{WooYan00, author = "Sung-Ho Woo and Sung-Bong Yang", title = "An Improved Nework Clustering Method for I/O Efficient Query Processing", booktitle = "ACM GIS", pages = "62--68", year = 2000, annote = "simple heuristics. needs BFS" } @Unpublished{Ten97, author = "S.-H. Teng", title = " Coarsening, Sampling, and Smoothing: Elements of the Multilevel Method ", note = "{\url{http://www-sal.cs.uiuc.edu/~steng/multilevel.ps}}" } @InProceedings{SpiTen96, author = "D. A. Spielman and S.-H. Teng", title = "Spectral Partitioning Works: Planar graphs and finite element meshes", booktitle = "37th Conference on Foundations of Computer Science", pages = "96--105", year = 1996 } @InProceedings{FelSgaEtAl91, author = "A. Feldmann and J. Sgall and S. Teng", title = "Dynamic Scheduling on Parallel Machines", pages = "111--120", booktitle = focs, year = 1991, publisher = "IEEE", annote = "nongreedy Heuristing fuer Prozessorzuteilung auf 2D Gitter." } @Article{GuGu94, author = "Q. P. Gu and J. G. Gu", title = "Algorithms and Average Time Bounds of Sorting on a Mesh-Connected Computer", journal = tpds, year = 1994, volume = 5, number = 3, pages = "308--315", annote = "Sehr effiziente Sorieralgorithmen fuer Gitter fuer versch. Knoennumerierungen." } @Article{GupEtAl94, author = "R. Gupta and S. A. Smolka and S. Bhaskar", title = "On Randomization in Sequential and Distributed Algorithms", journal = acmcs, year = 1994, volume = 26, number = 1, pages = "7--86", annote = "average time ungleich expected time, whp als 1-1/n definiert, almost shurely als 1-1/2^n^c definiert, random NC ungleich NC? universelles hashing, perfect hashing, Diskussion der Quellen von Zufallsbits. verloren?" } @InProceedings{PagRod01, author = "Pagh and Rodler", series = "LNCS", publisher = "Springer", volume = "2161", title = "Cuckoo Hashing", booktitle = "ESA: Annual European Symposium on Algorithms", year = "2001", } @InProceedings{Pag99, author = "R. Pagh", title = "Gash and Displace: Efficient Evaluation of Minmal Perfect Hash Functions", booktitle = "WADS", pages = "49--54", year = 1999, volume = 1663, series = "LNCS", publisher = "Springer" } @Article{AHNR98, author = "A. Andersson and T. Hagerup and S. Nilsson and R. Raman", title = "Sorting in linear time?", journal = "Journal of Computer and System Sciences", year = 1998, pages = "74--93" } @Article{HagRue89, author = "T. Hagerup and C. R{\"u}b", title = "Optimal merging and sorting on the {EREW-PRAM}", journal = "Information Processing Letters", year = 1989, volume = 33, pages = "181--185" } @Article{HagRue, author = "T. Hagerup and C. R{\"u}b", title = "A Guided Tour of Chernoff Bounds", journal = ipl, year = 1990, volume = 33, pages = "305--308" } @InProceedings{Hag91, author = "T. Hagerup", title = "Fast Parallel Generation of Random Permutations", booktitle = "International Colloquium on Automata, Languages and Programming", year = 1991 } @InProceedings{Hag92, author = "T. Hagerup", title = "The Log-Star Revolution", pages = "259--280", ISBN = "3-540-55210-3", editor = "Alain Finkel and Matthias Jantzen", booktitle = "Proceedings of Symposion on Theoretical Aspects of Computer Science ({STACS} '92)", month = feb, series = "LNCS", number = "577", publisher = "Springer", year = "1992", } @Article{Rag88, author = "P. Raghavan", title = "Probabilistic Construction of Deterministic Algorithms: Approximating Packing Integer Programs", journal = "Journal of Computer and System Sciences", year = 1988, volume = 37, pages = "130--143", annote = "weighted Chernoff bound" } @Book{BorYan98, author = "A. Borodin and R. El-Yaniv", title = "Online Computation and Competitive Analysis", publisher = "Cambridge University Press", year = "1998", address = "Cambridge", language = "english", } @InProceedings{BKRSW96, author = "A. Borodin and J. Kleinberg and P. Raghavan and M. Sudan and D. P. Williamson", title = "Adversarial Queing Theory", booktitle = "28th Annual {ACM} Symposium on Theory of Computing", pages = "376--385", year = 1996 } @InProceedings{AKOR98, author = "W. Aiello and E. Kushilevitz and R. Ostrovsky and A. Ros{\'e}n", title = "Adaptiv Packet Routing for Bursty Adversarial Traffic", booktitle = "30th Annual {ACM} Symposium on Theory of Computing", pages = "359--368", year = 1998 } @InBook{Pet95, author = "V. V. Petrov", title = "Limit Theorems of Probability Theory", publisher = "Clarendon Press", year = 1995, pages = "167ff", address = "Oxford", annote = "genaue Aussagen ueber Konvergenzgeschwindigkeit der Normalapproximation. von Hannah Bast" } @ARTICLE{BasHag95, AUTHOR = {H. Bast and T. Hagerup}, TITLE = {Fast Parallel Space Allocation, Estimation and Integer Sorting}, YEAR = {1995}, JOURNAL = {Information and Computation}, VOLUME = {123}, PAGES = {72 - 110}, } @InProceedings{Bas98, author = "H. Bast", title = "Dynamic Scheduling with Incomplete Information", booktitle = "10th ACM Symposium on Parallel Algorithms and Architectures" } @InProceedings{BasHag91, author = "H. Bast and T. Hagerup", title = "Fast and Reliable Parallel Hashing", pages = "50--61", booktitle = "3rd Symposium on Parallel Algorithms and Architectures", year = 1991 } @InProceedings{Nar99, author = "Girija J. Narlikar", title = "Scheduling Threads for Low Space Requirement and Good Locality", booktitle = "Proceedings of the 11th Annual {ACM} Symposium on Parallel Algorithms and Architectures", address = "Saint-Malo, France", month = jun # " 27--30,", year = "1999", pages = "83--95", publisher = "ACM, New York", } @InProceedings{HuCho83, author = "J. S. Huang and Y. C. Chow", title = "Parallel sorting and data partitioning", booktitle = "7th IEEE International Computer Software and Applications Conference", pages = "627--631", year = 1983 } @InProceedings{Aga96, author = "R. Agarwal", title = "A super scalar sort algorithm for {RISC} processors", booktitle = "{ACM SIGMOD} Int. Conf. on Management of Data", pages = "240--246", year = 1996, annote = "msd radix sort mentions TLB and branches" } @InProceedings{BleEtAl91, author = "G. E. Blelloch and C. E. Leiserson and B. M. Maggs and C. G. Plaxton and S. J. Smith and M. Zagha", title = "A comparison of sorting algorithms for the Connection Machine {CM-2}.", booktitle = spaa, year = 1991, pages = "3--16" } @InProceedings{BMW03, author = "G. E. Blelloch and B. M. Maggs and S. L. M. Woo", title = "Space-efficient finger search on degree-balanced search trees", booktitle = "14th Symposium on Discrete algorithms", pages = "374--383 ", year = 2003, annote = "Einsparung von Backpointern and level links durch komplexere Iteratoren" } @InCollection{MonLue, author = "B. Monien and R. L{\"u}ling", title = "Mapping und Lastverteilung in parallelen Systemen", booktitle = "??" } @InProceedings{DieEtAl94, author = "R. Diekmann and J. Gehring and R. L{\"u}ling and B. Monien and M. N{\"u}bel and R. Wanka", title = "Sorting Large Data Sets on a Massively Parallel System", booktitle = "6th IEEE Symposium on Parallel and Distributed Processing", year = 1994, pages = "2--9" } @InProceedings{HigEtAl92, author = "W. L. Hightower and J. F. Prins and J. H. Reif", title = "Implementations of Randomized Sorting on Large Parallel Machines", pages = "158--167", booktitle = spaa, year = 1992, annote = "Grosse Datenmengen werden auf MasPar sortiert. Samples muessen recht gross gewaehlt werden damit der Speicher nicht zu ungleichmaessig ausgelastet wird. Analyse wird einschliesslich der zu betrachtenden Konstanten betrieben. Beispiel wo Fehlschlagsw beliebig klein aber mit festem Exponenten ist. Splitter directed routing auf Meshes." } @InProceedings{Ier94, author = "D. Ierardi", title = "2d-Bubblesorting in Average Time {$O(\sqrt{N\lg N}$)}", booktitle = spaa, pages = "36--47", year = 1994, annote = "whp und average case, Mir die liebste Def. von whp, wichtig ist, das der worst case oft bei ungleicher verteilung von 0 und 1 auftritt. Andere Form des randomisierten 0-1 Sortierlemmas. Anders Beispiel fuer max Problem" } @Article{LanEtAl85, author = "H. Lang and M. Schimmler and H. Schmeck and H. Schr{\"o}der", title = "Systolic Sorting on a Mesh-Connected Network", journal = ietc, year = 1985, volume = 34, number = 7, pages = "652--658" } @InProceedings{LeiEtAl89, author = "T. Leighton and M. Newman and A. G. Ranade and E. Schwabe", title = "Dynamic Tree Embeddings in Butterflies and Hypercubes", booktitle = spaa, pages = "224--234", year = 1989, annote = "Loose end: Lower bound fuer det DLB?", address = "Santa Fe, NM, 18--21 June", publisher = "ACM, New York", } @InProceedings{LiSev94, author = "H. Li and K. C. Sevcik", title = "Parallel Sorting by Overpartitioning", pages = "46--56", booktitle = spaa, year = 1994, address = "Cape May, New Jersey", annote = "sample sort mit kP pivots. Sample wird seriell sortiert, dann wird globale nach Langen sortierte Liste der Segmente angelegt. angelegt und round robin abgeholt. Interessanter Verweis det. sample-sort Variante: sortiere lokal, bestimmt P lokale pivots sortiere die P^2 lokalen Pivots global und waehle dann P pivots aequidistant. Max Faktor 2 Overhead. Frage: was passiert wenn man aus denen wieder nur PlogP Elemente auswaehlt?" } @TechReport{AluEtAl96, author = "S. Aluru and S. Goil and S. Ranka", title = "Concatenated Parallelism: A Technique for Efficient Parallel Divide and Conquer", institution = "NPAC Syracuse University", year = 1996, number = "SCCS-759", annote = "deterministische LV fuer divide and conquer wenn man Teilproblemgroessen kennt. Overpartitioning. Quicksort, ..." } @Article{RanWanKum, author = "S. Ranka and J. Wang and M. Kumar", title = "Irregular Personalized Communication on Distributed Memory Machines", journal = jpdc, year = 1995, volume = 25, pages = "58--71", annote = "betonen den Fall weniger Nachriten CM5 orientiert. RS_NH ist interssanter Alg: bestimme Chunk size und berechne Folge von Permuationenen dieser Chunk size mit random und greedy Elementen. Analyse nur experimentell wird als schwierig bezeichnet." } @inproceedings{AluEtAl96a, title = "Concatenated Parallelism: A Technique for Efficient Parallel Divide and Conquer", author = "Sanjay Goil and Srinivas Aluru and Sanjay Ranka", booktitle = "Proceedings of the 8th IEEE Symposium on Parallel and Distributed Processing", pages = "488--495", year = 1996} @InProceedings{BurKar03, author = "Stefan Burkhardt and Juha K�kk�nen", title = "Fast lightweight suffix array construction and checking", booktitle = "14th Symposium on Combinatorial Pattern Matching", year = 2003, series = "LNCS", publisher = "Springer", note = "to appear" } @InProceedings{Har96, author = "J. Hardwick", title = "An Efficient Implementation of Nested Data Parallelism for Irregurlar Divide-and-Conquer Algorithms", booktitle = "Workshop on High-Level Programming Models and Supportive Environments", year = 1996, address = "Honolulu, Hawaii", annote = "Qucksort mit generischem Lastverteilungsverfahren" } @InCollection{Apostolico85, author = "Apostolico", title = "The Myriad Virtues of Subword Trees", booktitle = "Alberto Apostolico and Zvi Galil, Combinatorial Algorithms on Words, NATO ISI Series, Springer-Verlag", year = 1985, annote = "suffix tree" } @Article{McCreight:1976:SES, author = "Edward M. McCreight", title = "A Space-Economical Suffix Tree Construction Algorithm", journal = "Journal of the ACM", volume = "23", number = "2", pages = "262--272", month = apr, year = "1976", coden = "JACOAH", ISSN = "0004-5411", bibdate = "Wed Jan 15 18:12:53 MST 1997", abstract = "A new algorithm is presented for constructing auxiliary digital search trees to aid in exact-match substring searching. This algorithm has the same asymptotic running time bound as previously published algorithms, but is more economical in space. Some implementation considerations are discussed, and new work on the modification of these search trees in response to incremental changes in the strings they index (the update problem) is presented.", acknowledgement = ack-nhfb, classification = "723; 901", comment = "Algorithms to build, use, and modify suffix tree are presented. The advantage of this algorithm over other linear time algorithms to perform similar tasks is that this algorithm uses less space. This seems to the primary reference for suffix trees.", journalabr = "J Assoc Comput Mach", keywords = "computer programming; information science --- Information Retrieval", } @InProceedings{MutRaj98, author = "S. Muthukrishnan and R. Rajaraman", title = "An Adversarial Model for Distributed Dynamic Load Balancing", pages = "47--54", booktitle = "10th ACM Symposium on Parallel Algorithms and Architectures", annote = "Adversay model for token distribution on a network" } @InProceedings{GMR92, author = "L. Guibas and J. Mitchell and T. Roos", title = "Voronoi diagrams of moving points in the plane", pages = "113--125", ISBN = "3-540-55121-2", editor = "Gunther Schmidt and Rudolf Berghammer", booktitle = "Proceedings on Graph--Theoretic Concepts in Computer Science ({WG} '91)", month = jun, series = "LNCS", volume = "570", publisher = "Springer", address = "Berlin, Germany", year = "1992", } @Article{CarWeg79, author = "J. Lawrence Carter and Mark N. Wegman", title = "Universal Classes of Hash Functions", journal = "Journal of Computer and System Sciences", volume = "18", number = "2", pages = "143--154", month = apr, year = "1979", coden = "JCSSBM", ISSN = "0022-0000", bibdate = "Sat Jan 25 17:38:12 MST 1997", abstract = "An input independent average linear time algorithm for storage and retrieval on keys is given. The algorithm makes a random choice of hash function from a suitable class of hash functions. Given any sequence of inputs the expected time (averaging over all functions in the class) to store and retrieve elements is linear in the length of the sequence. The number of references to the data base required by the algorithm for any input is extremely close to the theoretical minimum for any possible hash function with randomly distributed inputs. Three suitable classes of hash functions are presented which also can be evaluated rapidly. The ability to analyze the cost of storage and retrieval without worrying about the distribution of the input allows as corollaries improvements on the bounds of several algorithms.", acknowledgement = ack-nhfb, classification = "723", journalabr = "J Comput Syst Sci", keywords = "computer programming; skew", } @InProceedings{DieMey93, author = "M. Dietzfelbinger and Meyer auf der Heide, F.", title = "Simple, Efficient Shared Memory Simulations", booktitle = "5th {ACM} Symposium on Parallel Algorithms and Architectures", address = "Velen, Germany", organization = "SIGACT and SIGARCH", month = jun # " 30--" # jul # " 2,", year = "1993", pages = "110--119", } @Article{DKMMRT94, author = "Martin Dietzfelbinger and Anna Karlin and Kurt Mehlhorn and Friedhelm Meyer auf der Heide and Hans Rohnert and Robert E. Tarjan", title = "Dynamic Perfect Hashing: Upper and Lower Bounds", journal = "SIAM Journal on Computing", volume = "23", number = "4", pages = "738--761", month = aug, year = "1994", coden = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", mrclass = "68P10 (68Q20)", mrnumber = "95c:68055", bibdate = "Sat Dec 5 17:26:53 MST 1998", url = "http://epubs.siam.org/sam-bin/dbq/article/19409", acknowledgement = ack-nhfb, } @Article{SchSieSri95, author = "J. P. Schmidt and A. Siegel and A. Srinivasan", title = "Chernoff-Hoeffding Bounds for Applications with Limited Independence", journal = "SIAM Journal of Discrete Mathematics", year = 1995, volume = 8, number = 2, pages = "223--250", annote = "laut M. Dietzfelbinger wichtiges Ergebnis zur Verwendung von universal hashing methoden" } @Article{JACM::MackenziePR1998, title = "On Contention Resolution Protocols and Associated Probabilistic Phenomena", author = "P. D. Mackenzie and C. G. Plaxton and R. Rajaraman", area = "Parallel Computation", journal = "Journal of the ACM", pages = "324--378", month = mar, year = 1998, volume = 45, number = 2, keywords = "Parallel computation, hash functions, emulation protocols", general-terms = "Algorithms, Theory", cr-categories = "F.1.2[parallelism and concurrency]; F.2.2", preliminary = "stoc::MackenziePR1994", references = "\cite{JCSS::AlonBLP1991} \cite{JCSS::CarterW1979} \cite{SPAA::DietzfelbingerH1993} \cite{SPAA::Gereb-GrausT1992} \cite{SPAA::GoldbergJLR1993} \cite{SPAA::GoldbergMR1994} \cite{JACM::GreenbergFL1987} \cite{JACM::GreenbergW1985} \cite{FOCS::GreenbergL1985} \cite{STOC::KarpLH1992} \cite{IEEETIT::KomlosG1985} \cite{CACM::MetcalfeB1976} \cite{STACS::HeideSS1995} \cite{FOCS::Siegel1989} \cite{JACM::UpfalW1987} \cite{FOCS::Yao1983}", annote= "fast das gleiche wie ein STACS95 paper von FMadH (loglog n) . allgemeines r aus R Problem wird betrachtet. RDA, " } @InProceedings{BDLMMNV02, author = "L. Becchetti and S. Diggavi and S. Leonardi and A. Marchetti-Spaccamela and S. Muthukrishnan and T. Nandagopal and A. Vitaletti", title = "Parallel Scheduling Problems in Next Generation Wireless Networks", booktitle = "SPAA", pages = "238--247", year = 2002, annote = "ressource augmented competitive analysis, minimizing maximal responce time, assigne both codes and data rates, QOS" } @InProceedings{MSVG02, author = "Meyer auf der Heide, F. and C. Schindelhauer and K. Volbert and M. Gr{\"u}newald", title = "Energy, Congestion and Dilation in Radio Networks", booktitle = "SPAA", pages = "230--237", year = 2002, annote = "behaupten MST seien energieoptimal" } @InProceedings{GhoEtAl95, author = "B. Ghosh and F. T. Leighton and B. M. Maggs and S. Muthukrishnan and C. G. Plaxton and R. Rajaraman and A. W. Richa and T. E. Tarjan and D. Zuckerman", title = "Tight Analyses of Two Local Load Balancing Algorithms", booktitle = stoc, year = 1995, annote = "preprint, benutzen Random matching. Funktioniert besonders gut fuer expandergraphen. " } @InProceedings{GGP95, author = "S Ghosh and A Gupta and SV Pemmaraju", title = "A self-stabilizing algorithm for the maximum flow problem", booktitle = "Proceedings of the IEEE 14th Annual International Phoenix Conference on Computers and Communication", year = "1995", pages = "8--14", annote = "habe version aus Distributed Computing (1997)10" } @InProceedings{GehPlaRaj97, author = "Gehrke and Plaxton and Rajaraman", title = "Rapid Convergence of a Local Load Balancing Algorithm for Asynchronous Rings", booktitle = "WDAG: International Workshop on Distributed Algorithms", series = "LNCS", number = 1320, publisher = "LNCS, Springer-Verlag", year = 1997, annote = "unser nearest neighbor algorithmus" } @Article{SleTar83, author = "D. D. Sleator and R. E. Tarjan", title = "A Data Structure for Dynamic Trees", journal = "Journal of Computer and System Sciences", year = "1983", volume = "26", number = "3", mon = jun, pages = "362--391", } @Article{DriEtAl88, author = "J. R. Driscoll and H. N. Gabow and R. Shrairman and R. E. Tarjan", title = "Relaxed Heaps: An Alternative to {F}ibonacci Heaps with Applications to Parallel Computation", journal = cacm, year = 1988, volume = 31, number = 11, pages = "1343--1354" } @InProceedings{MunRan99, AUTHOR = {K. Munagala and A. Ranade}, TITLE = {{I/O}-complexity of graph algorithms}, YEAR = {1999}, booktitle = "Proc. 10th Symp. on Discrete Algorithms", pages = {687--694}, publisher = {ACM-SIAM} } @InProceedings{KS96, author = "V. Kumar and E. J. Schwabe", title = "Improved Algorithms and Data Structures for Solving Graph Problems in External Memory", pages = "169--177", booktitle = "Proc. 8th Symp. on Parallel and Distrib. Processing", publisher = "IEEE", year = "1996", } @Article{YDL91, author = "S. B. Yang, Sudarshan K. Dhall, S. Lakshmivarahan", title = "An Improved Maximal Matching Algorithm", journal = "Parallel Processing Letters", year = 1991, volume = 1 } @Article{AbeBuc02, author = "J. Abello and A. L. Buchsbaum and J. R. Westbrook", title = "A Functional Approach to External Graph Algorithms", journal = "Algorithmica", year = 2002, volume = 32, pages = "437-458", annote = "semi external MST" } @InProceedings{BGVW00, AUTHOR = {A. Buchsbaum and M. Goldwasser and S. Venkatasubramanian and J. Westbrook}, TITLE = {On external memory graph traversal}, YEAR = {2000}, booktitle = "Proc. 11th Symp. on Discrete Algorithms", pages = {859--860}, publisher = {ACM-SIAM} } @InProceedings{ArToVi00, AUTHOR = {L. Arge and L. Toma and J. S. Vitter}, TITLE = {{I/O}-efficient algorithms for problems on grid-based terrains}, YEAR = {2000}, booktitle = "Proc. Workshop on Algorithm Engineering and Experiments (ALENEX)", } @InProceedings{RKU00, author = "A. Ranade and S. Kothari and R. Udupa", title = "Register Efficient Mergesorting", booktitle = "High Performance Computing --- HiPC", pages = "96--103", year = 2000, volume = 1970, series = "LNCS", publisher = "Springer" } @Article{WACV02, author = "R. Wickremesinghe and L. Arge and J. S. Chase and J. S. Vitter", title = "Efficient Sorting Using Registers and Caches", journal = "ACM Journal of Experimental Algorithmics", year = 2002, volume = 7, number = 9 } @InProceedings{ArBrTo00, author = "L. Arge and G. Brodal and L. Toma", title = "On External-Memory {MST}, {SSSP} and multi-way Planar Graph Separation", booktitle = "Proc. 8th Scand.Workshop on Alg. Theory", publisher = "Springer", series = "LNCS", year = 2000 } @InProceedings{MahZeh99, author = "A. Maheshwari and N. Zeh.", title = "External Memory Algorithms for Outerplanar Graphs", pages = "307--316", booktitle = "Proc. 10th Intern. Symp. on Algorithms and Computations", series = "LNCS", volume = "1741", publisher = "Springer", year = "1999", } @ARTICLE{ZhaNoo98, AUTHOR = {Zhan, F. B. and Noon, C. E.}, TITLE = {Shortest path algorithms: {An} evaluation using real road networks}, YEAR = {1998}, JOURNAL = {Transportation Science}, VOLUME = {32}, PAGES = {65--73}, BIBTYPE = {ARTICLE}, } @ARTICLE{CheGolRad96, AUTHOR = {Cherkassky, B. V. and Goldberg, A. V. and Radzik, T.}, TITLE = {Shortest path algorithms: {Theory} and experimental evaluation }, YEAR = {1996}, JOURNAL = {Math.\ Programming}, VOLUME = {73}, PAGES = {129--174}, LOCATION = {priebe's library}, BIBTYPE = {ARTICLE}, } @Article{Dij59, author = "E. W. Dijkstra", title = "A note on two problems in connexion with graphs.", journal = "Numerische Mathematik", volume = "1", pages = "269--271", year = "1959", keywords = "weighted, graph, graphs, all pairs shortest paths, path, minimal, minimum, weight, closure, spanning tree, connection, SSSP", } @Article{Tho99, author = "Mikkel Thorup", title = "Undirected Single Source Shortest Paths in Linear Time", journal = "Journal of the ACM", year = 1999, volume = 46, pages = "362--394" } @InProceedings{Tho97, author = "Mikkel Thorup", title = "Undirected Single Source Shortest Paths in Linear Time", booktitle = focs, year = 1997 } @InProceedings{Tho96, author = "Mikkel Thorup", title = "On {RAM} Priority Queues", pages = "59--67", ISBN = "0-89871-366-8", booktitle = "Proceedings of the Seventh Annual {ACM}-{SIAM} Symposium on Discrete Algorithms", month = "28--30*" # jan, publisher = "ACM/SIAM", address = "New York/Philadelphia", year = "1996", } @Article{Kle94, author = "P. N. Klein", title = "A data structure for bicategories, with application to speeding up an approximation algorithm", journal = "Information Processing Letters", year = 1994, volume = 52, pages = "303--307", annote = "network design, non-fixed point-to-point problem, netral forest problem" } @InProceedings{KLA+01, author = "T. Kasai and G. Lee and H. Arimura and S. Arikawa and K. Park", title = "Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications", booktitle = proc # "12th " # cpm, series = lncs, volume = "2089", publisher = springer, pages = "181--192", year = "2001", } @Article{BDTW, author = "J. L. Balcazar and Y. Dai and J. Tanaka and O. Watanabe", title = "Provably Fast Training for Support Vector Machines", journal = "dam", year = "???" } @Article{HMKKESL04, author = "T. Ho and M. Medard and R. Koetter and D. R. Karger and M. Effros and J. Shi and B. Leong", title = "Towards a Random Operation of Networks", journal = "submitted", year = 2004, annote = "journal version of two isit papers?" } @Article{CLC82, author = "F. Y. Chin and J. Lam and I-N. Chen", title = "Efficient Parallel Algorithms for Some Graph Problems", journal = "cacm", year = 1982, annote = "conncted components and mst dense graphs only?" } @InProceedings{KR04, author = "D. R. Karger and M. Ruhl", title = "Simple Efficient Load Balancing Algorithms for Peer-to-Peer Systems", booktitle = "SPAA", year = 2004 } @InProceedings{STOC98*69, author = "David R. Karger and Matthew S. Levine", title = "Finding Maximum Flows in Simple Undirected Graphs is Easier Than Bipartite Matching", pages = "69--78", ISBN = "0-89791-962-9", booktitle = "Proceedings of the 30th Annual {ACM} Symposium on Theory of Computing ({STOC}-98)", month = may # "23--26~", publisher = "ACM Press", address = "New York", year = "1998", } @InProceedings{GhoMutSch96, author = "B. Ghosh and S. Muthukrishnan and M. H. Schultz", title = "First and second order diffusive methods for rapid, coarse, distributed load balancing", booktitle = spaa, year = 1996, pages = "72--81" } @Article{LeiEtAl94, author = "F. T. Leighton and B. M. Maggs and A. G. Ranade and S. B. Rao", title = "Randomized Routing and Sorting on Fixed-Connection Networks", journal = "Journal of Algorithms", year = 1994, volume = 17, pages = "157--205" } @Unpublished{Mag01, author = "B. Maggs", title = "Challenges in Building a Reliable System of Tens of Thousandes of Servers", note = "Akamai Technologies, mini course at ADFOCS", year = 2001 } @InProceedings{LeiEtAl95, author = "T. Leighton and Y. Ma and T. Suel", title = "On Probabilistic Networks for Selection, Merging and Sorting", booktitle = spaa, year = 1995, address = "Santa Barbara", pages = "106--118" } @InProceedings{NegEtAl, author = "A. Negro and N. Santoro and J. Urrutia", title = "On the Packet Complexity of Distributed Selection", pages = "108--115", booktitle = "{CONPAR} ???", year = 1987, publisher = "Springer", annote = "sieht ziemlich straight forward aus." } @InProceedings{Pla89, author = "C. G. Plaxton", title = "On the Network Complexity of Selection", pages = "396--401", booktitle = focs, year = 1989, publisher = "IEEE", annote = "Lower bound fuer selection unter der ich bleibe. Gute einfuehrung des Modells. z.B. verschiedene Schluessel. Knackpunkt ist die unfaehigkeit konzentrierte Datenelemente schnell zu verteilen." } @InProceedings{MilRei85, author = "G. L. Miller and J. H. Reif", title = "Parallel Tree Contraction and its Application", pages = "478--489", booktitle = focs, year = 1985, annote = "Zufallspermutationen" } @InProceedings{Rei85, author = "J. Reif", title = "An optimal parallel algorithm for integer sorting", booktitle = "26th Symposium on Foundations of Computer Science", pages = "490--503", year = 1985 } @InProceedings{Raj98, author = "S. Rajasekaran", title = "A Framework for Simple Sorting Algorithms on Parallel Disk Systems", booktitle = "10th {ACM} Symposium on Parallel Algorithms and Architectures", pages = "88--98", year = 1998 } @Article{RajRei89, author = "S. Rajasekaran and J. H. Reif", title = "Optimal and Sublogarithmic Time Randomized Parallel Sorting Algorithms", journal = "{SIAM} Journal on Computing", year = 1989, volume = 18, number = 3, pages = "594--607", annote = "zufallspermutationen" } @InCollection{Raj92, author = "S. Rajasekaran", booktitle = "Advances in Parallel Algorithms", title = "Randomized Algorithms for Packet Routing on the Mesh", publisher = "Blackwell", year = 1992, editor = "L. Kronsj{\"o} and D. Shumsheruddin", pages = "277--301", annote = "Referenz Chernoff. Interessante Def. von mhw." } @InProceedings{Raj90, author = "S. Rajasekaran", title = "Randomized Parallel Selection", number = 472, series = "LNCS", pages = "215--224", booktitle = "Tenth Conference on Foundations of Software Technology and Theoretical Computer Science", year = 1990, publisher = "Springer", address = "Bangalore", annote = "ziemlich genau mein problem und Algortihmus :-(. Zitiert lower bound _unter_ dem ich bleibe weil Elemente wirklich zufaellig verteilt Er muss den Hypercube extrem ausnutzen um auf die gleiche Zeit zu kommen aber bei mir sind die Routing Probleme einfacher. Er macht nur eine Iteration." } @InCollection{RajSen93, author = "S. Rajasekaran and S. Sen", title = "Random Sampling Techniques and Parallel Algorithm Design", booktitle = "Synthesis of Parallel Algorithms", publisher = "Morgan Kaufmann", year = 1993, editor = "H. Reif", chapter = 9, pages = "411--451", annote = "Schwerpunkt auf sortieren, Einfache Begruendung warum Annahme versch. Werte obda ist." } @Article{Ran94, author = "A. Ranade", title = "Optimal Speedup for Backtrack Search on a Butterfly Network", volume = 27, number = 1, journal = "Mathematical Systems Theory", year = 1994, pages = "85--101", annote = "Optimal skalierbar aber keinerlei Granularitaetskontrolle." } @InProceedings{Reif85, author = "J. H. Reif", title = "An Optimal Parallel Algorithm for Integer Sorting", booktitle = focs, year = 1985, pages = "496--504", annote = "Zufallspermutationen sehr aehnlich wie meine" } @Article{ReiVal87, author = "J. H. Reif and L. G. Valiant", title = "A Logarithmic Time Sort for Linear Size Networks", journal = jacm, year = 1987, volume = 34, number = 1, pages = "60--76", annote = "Referenzpaper fuer Flashsort. Gewohnt unlesbar" } @InCollection{Val90a, author = "L. G. Valiant", title = "General Purpose Parallel Architectures", booktitle = "Handbook of Theoretical Computer Science", publisher = "Elsevier", year = 1990, editor = "J. van Leeuwen", volume = "A: Algorithms and Complexity", pages = "943--971", annote = "Annahme ueber Hash function section 4.3" } @Article{Val94, author = "L. Valiant", title = "A Bridging Model for Parallel Computation", journal = cacm, year = 1994, volume = 33, number = 8, annote = "BSP Referenz in DitEtAl96" } @Book{Neu66, author = "Neumann, J. von", annote = "edited by A. W. Burks", key = "refs-general, CA, automata-theory, complex, automata-selfrepro", title = "Theory of Self-Reproducing Automata", publisher = "University of Illinois Press", address = "Urbana, IL, USA", year = "1966", LCCN = "QA267 .V55", bibdate = "Wed Dec 16 07:25:27 1998", annote = "Von Neumann's work on self-reproducing automata, completed and edited after his death by Arthur Burks. Also includes transcripts of von Neumann's 1949 University of Illinois lectures on the ``Theory and Organization of Complicated Automata''.", acknowledgement = ack-nhfb, } @Article{Hoa61, author = "C. A. R. Hoare", journal = "Communication of the ACM", number = "7", pages = "321", title = "Quicksort", volume = "4", year = "1961", crindex = "Classeur", } @Book{Hoa84, author = "C. A. R. Hoare", title = "Communicating Sequential Processes", publisher = "Prentice-Hall", year = "1984", } @Article{Hoa78, author = "C. A. R. Hoare", title = "Communicating Sequential Processes", journal = "Communications of the ACM", volume = "21", number = "8", pages = "666--677", month = aug, year = "1978", coden = "CACMA2", ISSN = "0001-0782", bibdate = "Tue Mar 25 13:26:09 MST 1997", anote = "See corrigendum \cite{Hoare:1978:CCS}.", abstract = "This paper suggests that input and output are basic primitives of programming and that parallel composition of communicating sequential processes is a fundamental program structuring method. When combined with a development of Dijkstra's guarded command, these concepts are surprisingly versatile. \par Their use is illustrated by sample solutions of a variety of familiar programming exercises.", acknowledgement = ack-nhfb, annote = "This paper is now expanded into an excellent book detailed by Hoare and published by Prentice-Hall. This paper is reproduced in Kuhn and Padua's (1981, IEEE) survey ``Tutorial on Parallel Processing.'' Reproduced in ``Distributed Computing: Concepts and Implementations'' edited by McEntire, O'Reilly and Larson, IEEE, 1984. Somewhat dated.", classcodes = "C6110 (Systems analysis and programming)", classification = "723", corpsource = "Queen's Univ., Belfast, UK", journalabr = "Commun ACM", keywords = "4.22; 4.32 maeder biblio: synchronisation and concurrency in processes; ak; bhibbard grecommended91; classes; computer programming; concurrency; conditional critical regions; coroutines; CR categories: 4.20; CSP; data representations; Dijkstra's guarded command; guarded commands; hcc; input; iterative arrays; k-concurrency; k-csp; k-guarded-commands; monitors; multiple entries; multiple exits; nondeterminacy; output; parallel composition; parallel programming; primitives; procedures; program; program structures; programming; Programming; programming languages; programming primitives; recursion; sequential processes; structured programming; structuring method", treatment = "T Theoretical or Mathematical", } @Article{ReiSen94, author = "J. H. Reif and S. Sen", title = "Randomized Algorithm for Binary Search and Load Balancing on Fixed Connection Networks with Geometric Applications", journal = "{SIAM} Journal on Computing", year = 1994, volume = 23, number = 3, pages = "633--651", annote = "Kurze Einfuehrung von Flash sort. Im grossen und ganzen unlesbar, Lemma fuer whp Ergebnisse bei rekursiven Algorithmen. Benutzt Rajasekarans Def. von Oschlange whp aber nennt es very high likelyhood." } @InProceedings{ReiTat94, author = "J. H. Reif and S. R. Tate", title = "Dynamic Parallel Tree Contraction", pages = "114--121", address = "Cape May, New Jersey", annote = "CRCW, Terminator II Analogie !" } @Article{Rei85, author = "R. Reischuk", title = "Probabilistic Parallel Algorithms for Sorting and Selection", journal = "{SIAM} Journal on Computing", year = 1985, volume = 14, number = 2, pages = "396--409", annote = "abgedrehte Modelle. comparison tree, selection in konst. Zeit mhw!" } @InProceedings{Sav93, author = "S. A. Savari", title = "Average Case Analysis of Five Two-dimensional Bubble Sorting Algorithms", pages = "336--345", booktitle = spaa, year = 1993, address = "Velen" } @Article{Sen90, author = "S. Sen", title = "Finding an approximate median with high probability in constant parallel time", journal = "Information Processing Letters", year = 1990, volume = 34, pages = "77--80" } @Unpublished{Sin98, author = "Alistair Sinclair", title = "Balls and Bins: Load-Balancing", note = "Lecture 15: March 30", annote = "von Volker P. lower bounds for random allocation, kurze Herleitung von balanced random allocation" } @InProceedings{Ste96, author = "V. Stemann", title = "Parallel Balanced Allocation", booktitle = spaa, year = 1996, pages = "261--269", annote = "deja vu (wahrscheinlich AzarEtAl, Adler die er zitiert. Random graph Methoden Durch allocation in mehreren Runden kann in O(log log n) Runden Balance erreicht werden. etc." } @Article{PelUpf89, author = "D. Peleg and E. Upfal", title = "The token distribution problem", journal = "{SIAM} Journal of Computing", year = 1989, volume = 18, pages = "229--243", annote = "Basisreferenz token distribution" } @Article{ABKU00, author = "Y. Azar and A. Z. Broder and A. R. Karlin and Eli Upfal", title = "Balanced Allocations", journal = "SIAM Journal on Computing", volume = "29", number = "1", pages = "180--200", month = feb, year = "2000", coden = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", bibdate = "Sat Jan 22 13:21:34 MST 2000", url = "http://epubs.siam.org/sam-bin/dbq/article/28849", acknowledgement = ack-nhfb, } @InProceedings{ABKU94, author = "Y. Azar and A. Z. Broder and A. R. Karlin and E. Upfal", title = "Balanced Allocations", pages = "593--602", booktitle = "26th ACM Symposium on the Theory of Computing", year="1994" } @Unpublished{Sai01, author = "J. Saia", title = "Data Migration with Edge Capacities and Machine Speeds", note = "U. Washington", year = 2001 } @InProceedings{HHKSW01, author = "J. Hall and J. Hartline and A. R. Karlin and J. Saia and J. Wilkes", title = "On Algorithms for Efficient Data Migration", booktitle = "12th ACM-SIAM Symposium on Discrete Algorithms", pages = "620--629", year = 2001 } @Article{MorSha94, author = {B.M.E. Moret and H.D. Shapiro}, title = {An Empirical Assessment of Algorithms for Constructing a Minimum Spanning Tree}, journal = {DIMACS Series in Discrete Mathematics and Theoretical Computer Science}, year = {1994}, volume = {15}, pages = {99--117} } @InProceedings{MorSha91, author = "B. M. E. Moret and H. D. Shapiro", title = "An Empirical Analysis of Algorithms for Constructing a Minimum Spanning Tree", pages = "400--411", ISBN = "3-540-54343-0", booktitle = "Workshop Algorithms and Data Structures ({WADS})", month = aug, series = "LNCS", number = "519", publisher = "Springer", year = "1991", } @article{ABW02, AUTHOR = "J. Abello and A. Buchsbaum and J. Westbrook", TITLE = "A Functional Approach to External Graph Algorithms", journal = {Algorithmica}, VOLUME = {32}, number = {3}, PAGES = {437--458}, YEAR = {2002}, } @inproceedings{CGG+95 , author = "Yi-Jen Chiang and Michael T. Goodrich and Edward F. Grove and Roberto Tamassia and Darren E. Vengroff and Jeffey S. Vitter" , title = "External-Memory Graph Algorithms" , pages = "139--149" , booktitle = "Proceedings of the Sixth Annual {ACM}-{SIAM} Symposium on Discrete Algorithms" , year = 1995 , checked = "20020228jv" } @Article{Kin97, author = "V. King", title = "A Simpler Minimum Spanning Tree Verification Algorithm", journal = "Algorithmica", year = 1997, volume = 18, pages = "263--270" } @misc{Mor98, author = {B.M.E. Moret}, title = {Towards a discipline of experimental algorithmics}, year = 1998, note = "Manuscript" } @InProceedings{FatSpi99, author = "P. Fatourou and P. Spirakis", title = "A New Scheduling Algorithm for General Strict Multithreaded Computations", booktitle = "13rd International Symposium on DIStributed Computing (DISC'99)", address = "Bratislava, Slovakia", number = 1693, pages = "297--311", series = "LNCS", year = 1999 } @Article{FatSpi00, volume = 33, number = 3, pages = "173--232", journal = "Theory of Computing Systems Journal", author = "P. Fatourou and P. Spirakis", title = "Efficient Scheduling of Strict Multithreaded Computations", year = 2000 } @InProceedings{FatSpi96, author = "P. Fatourou and P. Spirakis", title = "Scheduling Algorithms for Strict Multithreaded Computations", booktitle = "ISAAC: 7th International Symposium on Algorithms and Computation", number = 1178, pages = "407--416", series = "LNCS", year = 1996 } @InProceedings{Spi86, author = "P. Spirakis", title = "The Diameter of Connected Components of Random Graphs", number = 246, series = "LNCS", pages = "264--275", booktitle = "Workshop on Graph-Theoretic Concepts in Computer Science", year = 1986 } @InProceedings{Upf94, author = "E. Upfal", title = "On the Theory of Interconnection Networks for Parallel Computers", pages = "473--486", booktitle = "Scalable High Performance Computing Conference", year = 1994, address = "Knoxville", annote = "Wormhole routing ist offenes Problem. Zuordnung zu Konferenz nicht ganz sicher. ", address = "Knoxville, TN", publisher = "IEEE, Los Alamitos, CA", } @Article{Sie78, author = "A. F. Siegel", title = "Random Arcs on the Circle", journal = "J. Appl. Probab.", year = 1978, volume = 15, pages = "774--789", note = "studies proportion covered" } @Article{SieHol82, author = "A. F. Siegel and L. Holst", year = "1982", title = "Covering the circle with random arcs of random sizes", journal = "J. Appl. Probab.", volume = "19", pages = "373--381", annote = "geompr; coverage", } @Unpublished{Tre98, author = "R. Treumann", title = "Experiences in The Implementation of a Thread Safe, Threads Based {MPI} for the {IBM RS/6000 SP}", note = "presented at EuroPVM/MPI", year = 1998 } @Article{UpfEtAl96, author = "E. Upfal and S. Felperin and M. Snir", title = "Randomized Routing with Shorter Paths", journal = tpds, year = 1996, volume = 7, number = 4, pages = "356--362", annote = "Will man viele Pakete routen braucht man relativ wenig randomness (O (loglog n) pro zus. Paket)" } @Article{AhaAtt95, author = "E. Aharonson and H. Attiya", title = "Counting networks with arbitrary fan-out", journal = "Distributed Computing", year = 1995, volume = 8, pages = "163--169" } @InProceedings{ShaZem94, author = "N. Shavit and A. Zemach", title = "Diffracting Trees", pages = "167--176", booktitle = spaa, year = 1994, address = "Cape May, New Jersey", annote = "Globales Zaehlen effizienter als Reduktionsbaum" } @Unpublished{ABHMST98, author = "W. Aiello and C. Busch and M. Herlihy and M. Mavranicolas and N. Shavit and D. Touitou", title = "Supporting Increment and Decrement Operations in Balancing Networks", note = "submitted for STACS", year = 1998 } @Article{ShaZem96, author = "N. Shavit and A. Zemach", title = "Diffracting Trees", journal = "IEEE Transactions on Computer Systems", year = 1996, volume = 14, number = 4, pages = "385--428" } @Article{WatWid98, author = "R. Wattenhofer and P. Widmayer", title = "An Inherent Bottleneck in Distributed Counting", journal = "Journal Parallel and Distributed Processing, Special Issue on Parallel and Distributed Data Structures", volume = 49, year = 1998, pages = "135--145" } @InProceedings{ShaTou95, author = "N. Shavit and D. Touitou", title = "Elimination Trees and the Construction of Pools and Stacks", booktitle = spaa, year = 1995, address = "Santa Barbara", pages = "54--63", annote = "Erweiterung des Vorjahres papers ueber diffracting trees. Anwendung fuer pools (i/o Reihenfolge nicht ganrantiert) und stacks. Im Mittel konstante Zugriffszeit!? Sowohl inkrement als auch dekrement moeglich. tokens und anti-tokens koennen sich annihilieren. 'Almost stack'" } @PhdThesis{Sib92, author = "J. Sibeyn", title = "Algorithms for Routing on Meshes", school = "University of Utrecht", year = 1992 } @TechReport{Sib95, author = "J. F. Sibeyn", title = "Sample Sort on Meshes", institution = "{MPI} Informatik", year = 1995, OPTaddress = "Saarbr{\"u}cken", annote = "zweistufig, determinstische Variante, grosse Zahlenmengen. recht gut." } @InProceedings{SibKau97, author = "J. Sibeyn and M. Kaufmann", title = "{BSP}-Like External-Memory Computation", pages = "229-240", booktitle = "3rd Italian Conference on Algorithms and Complexity", year = 1997 } @TechReport{Sib97, author = "J. Sibeyn", title = "From Parallel to External List Ranking", institution = "Max-Planck Institut f{\"u}r Informatik", year = 1997, number = "MPI-I-97-1-021" } @Book{SuaBir89, author = "R. Suaya and G. Birtwistle (eds.)", title = "{VLSI} and Parallel Compuation", publisher = "Morgan Kaufmann", year = 1989, annote = "Mit Artikeln von E.W. Mayr, W. Dally, Dally sagt warum meshes u.U. besser als HC, Johnsson zeigt embedding HC mesh" } @Article{Dal93, author = "W. J. Dally", title = "A Universal Parallel Comptuer Architecture", journal = "New Generation Computing", year = 1993, number = 11, pages = "227--249", annote = "Motivation fuer J-Machine?" } @InProceedings{FelEtAl92, author = "S. Felpering and P. Raghavan and E. Upfal", title = "A Theory of Wormhole Routing in Parallel Computers", pages = "563--572", booktitle = focs, year = 1992, publisher = "IEEE", annote = "Beispiel fuer meine schwaechere Def. von whp. Auf Butterfly geht routing in O(L min(L, N)log N) sei L Nachrichtenlaenge, N PE-Zahl. Auf mesh: O(sqrt(N)L\log N + N/log N. Also alles ziemilich schlecht. Unterschied zu einfachen Algorithmen: Zufaelliges Warten am Anfang. Simulationen zeigen, dass kurzes Warten gut sein kann. Aber der theoretesche Algorithmus wartet l a n g e damit die W klein wird, dass Nachrichten sich blockieren. Besondere Schwierigkeit: Ketten von Nachrichten blockieren sich indirekt." } @Proceedings{ParResRam94, title = "Parallel Processing of Discrete Opitmization Problems", year = 1994, editor = "P. M. Pardalos and G. C. Resende and K. G. Ramakrishnan", number = 22, publisher = "{DIMACS}" } @Article{FelEtAl96, author = "S. Felpering and P. Raghavan and E. Upfal", title = "A Theory of Wormhole Routing in Parallel Computers", journal = "IEEE Transactions on Computers", year = 1996, volume = 48, number = 6, pages = "704--713", annote = "siehe auch obiges FOCS paper" } @Article{Wes94, author = "J. Westbrook", title = "Randomized Algorithms for Multiprocessor Page Migration", journal = "{SIAM} Journal on Computing", year = 1994, volume = 23, number = 5, pages = "951--965", annote = "eine Seite pro PE. Fuer jede Seite und jede PE einen Zaehler, der zufaellig initialisiert wird. Bei Zugriff dekremtierung. =0 ? => migrieren und ruecksetzen. optimiere die setz/ruechsetzverteilung. Problem: worst case (competitive) wird optimiert. Aber der ist wahrscheinlich ohnehin so schlecht dass es nicht hilft. Def. oblivious und adaptive adversary. Markov ketten." } @Article{ZhaKor94, author = "W. Zhang and R. E. Korf", title = "Parallel Heap Operations on an EREW PRAM", journal = jpdc, year = 1994, volume = 20, pages = "248--255", annote = "Algorithmus der auf schnelles Entfernen eines Elements getunt ist. Zeit O((log n)/p + log p) bringt also nur bei exponentiellen queue Groessen einen Vorteil." } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % sequentielle Suche @Article{CarPin89, author = "J. Carlier and E. Pinson", title = "An Algorithm for Solving the Job-Shop Problem", journal = "Management Science", year = 1989, volume = 35, number = 2, pages = "164--176", annote = "OR-Kram" } @Article{DilNel94, author = "J. F. Dillenburg and P. C. Nelson", title = "Perimeter Search", journal = aint, year = 1994, volume = 65, pages = "165--178", annote = "Biderektionale bei der durch Bewertung def. Umkreis um Ziel expandiert wird. Problem: Heuristik zu allen Knoten im Perimeter wird gebraucht. -> 15-Puzzle" } @Book{HorSah78, author = "E. Horowitz and S. Sahni", title = "Fundamentals of Computer Algorithms", publisher = "Computer Science Press", year = 1978 } @Article{Kor85, author = "R. E. Korf", title = "Depth-First Iterative-Deepening: An Optimal Admissible Tree Search", journal = aint, year = 1985, volume = 27, pages = "97--109", annote = "Daten fuer 15-Puzzle, IDA* Ursprungspaper" } @Article{Kor93, author = "R. E. Korf", title = "Linear-space best-first search", journal = aint, year = 1993, volume = 62, pages = "41--78", annote = "Haupteigenschaft: Neue Knoten werden in best first order expandiert. Vergleich mit verwandten Verfahren, 15 Puzzle. Rein rekursiver Tiefensuchalgorithmus der Bound so geschickt waehlt das nie voreilig entschieden wird. Wird nichtrivial dadurch das in bekanntem Gelaende (das gerade reexpandiert wird etwas anders vorgegangen wird. DFB\&B generiert nur 10\% mehr Knoten als best first fuer euklidische TSP mit Spannbaumheuristik! fuer 15 Puzzle ungefaehr gleiche Leistung v. IDA* und RBFS" } @Article{Par95, author = "I. Parberry", title = "A real-time algorithm for the $(n^2 - 1)$-puzzle", journal = "Information Processing Letters", year = 1995, volume = 56, pages = "23--28" } @Article{RatWar90, author = "D. Ratner and M. Warmuth", title = "Finding a Shortest Solution to the $N\times N$ Extension of the 15-Puzzle is Intractable", journal = "Journal of Symbolic Computation", year = 1990, volume = 10, pages = "111-137" } @Article{NiePla89, author = "X. Nie and D. A. Plaisted", title = "Refinements to Depth-First Iterative Deepening Search in Automatic Theorem Proving", journal = aint, year = 1989, volume = 41, pages = "223--235", annote = "abstrus" } @InCollection{Hel88, author = "P. Helman", title = "An Algebra for Search Problems and their Solutions", booktitle = "Search in Artificial Intelligence", publisher = "Springer", year = 1988, editor = "V. Kumar and L. N. Kanal", pages = "28--90", annote = "Hammerhart, Betonung auf Dominanzrelationen. Behaupten ein gutes Modell fuer Komplixeitaetsuntersuchungen gefunden zu haben." } @InProceedings{Hog94, author = "T. Hogg", title = "Statistical Mechanics of Combinatorial Search", booktitle = "Physics and Computation", year = 1994, pages = "196--202", annote = "Modell fuer Graph coloring" } @InCollection{BagSen88, author = "A. Bagchi and A. K. Sen", title = "Average-Case Analysis of Heuristic Search in Tree-like Networks", booktitle = "Search in Artificial Intelligence", publisher = "Springer", year = 1988, editor = "V. Kumar and L. N. Kanal", pages = "28--90", annote = "Aehlich zu Pearls Betrachtungen. Unterschied: mehr als ein goal-node" } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Kumars Stuff @TechReport{ArvEtAl90a, author = "S. Arvindam and V. Kumar and V. N. Rao and V. Singh", title = "Automatic Test Pattern Generator on Parallel Processors", institution = "University of Minnesota", year = 1990, number = "TR 90-20", annote = "Short version in Proc. Intl. Conference on Knowledge-Based Computer Systems, December 1989. Hier wird das falsche Ergebnis fuer Random Polling ausfuehrlich benutzt. Speedup Anomalien" } @InProceedings{ArvEtAl90b, author = "S. Arvindam and V. Kumar and V. N. Rao", title = "Efficient Parallel Algorithms for Search Problems: Applications in {VLSI} {CAD}", booktitle = "3rd Symposium on Massively Parallel Computation", year = 1990, annote = "VLSI floorplan optimization, tautology verification, tiefensuche, random polling? kurzer ueberblick", address = "College Park, MD, 8--10 October", publisher = "NASA/IEEE, Los Alamitos, CA", } @InProceedings{EveEtAl90, author = "M. Evett and J. Hendler and A. Mahanti and D. Nau", title = "{PRA*}: A memory-limited heuristic search procedure for the {C}onnection {M}achine", pages = "145--149", booktitle = "3rd Symposium On the Frontiers Of Massively Parallel Computation", year = 1990, address = "College Park, Maryland", annote = "Bei Speichermangel werden die schlechtesten Knoten durch ihre Vorgaenger ersetzt. Ansonsten ist das Karp-Zhangs local best first Algorithmus!" } @Article{NauEtAl84, author = "D. S. Nau and V. Kumar and L. Kanal", title = "General Branch and Bound, and Its Relation to {A*} and {AO*}", journal = aint, year = 1984, volume = 23, pages = "29--58", annote = "Gaehn" } @Article{KumKan84, author = "V. Kumar and L. N. Kanal", title = "Parallel Branch-and-Bound Formulations for {AND}/{OR} Tree Search", journal = pami, year = 1984, volume = 6, number = 6, pages = "768--778", annote = "SSS* im Branch and Bound Gewand. Maessig erfolgreiche Parallelisierung" } @InCollection{KumKan88, author = "V. Kumar and L. N. Kanal", title = "The CDP: A Unifying Formulation for Heuristic Search, Dynamic Programming and Branch-and-Bound", booktitle = "Search in Artificial Intelligence", publisher = "Springer", year = 1988, editor = "V. Kumar and L. N. Kanal", pages = "1--27", annote = "Info Bib: F Sea, Vereinheitlichung verschiedener Suchformalismen durch was Grammatikmaessiges. z.B. dyn prog. und BuB" } @InCollection{SchKarKum00, author = "K. Schloegel and G. Karypis and V. Kumar", title = "Graph Partitioning for High Performance Scientific Simulations", booktitle = "CRPC Parallel Computing Handbook", publisher = "Morgan Kaufmann", year = 2000, editor = "J. Dongarra et al.", note = "to appear, {\protect\url{http://www-users.cs.umn.edu/~karypis/publications/partitioning.html}}" } @Book{KumEtAl94, author = "V. Kumar and A. Grama and A. Gupta and G. Karypis", title = "Introduction to Parallel Computing. Design and Analysis of Algorithms", publisher = "Benjamin/Cummings", year = 1994, annote = "S. 316: Er behauptet immer alpha splitting zu koennen." } @Book{KumEtAl94vorl, author = "V. Kumar and A. Grama and A. Gupta and G. Karypis", title = "Introduction to Parallel Computing. Design and Analysis of Algorithms", publisher = "Benjamin/Cummings", year = 1994, note = "einfaches, praxisnahes Buch" } @TechReport{KarKum92, author = "G. Karypis and V. Kumar", title = "Unstructured Tree Search on {SIMD} Parallel Computers", institution = "University of Minnesota", year = 1992, month = "April", annote = "Triggering schemes sind schon drin. Ausfuerhlicher als Zeitschriftenversion. Berechnung eines optimalen statischen Triggers. " } @Article{KarKum94, author = "G. Karypis and V. Kumar", title = "Unstructured Tree Search on {SIMD} Parallel Computers", journal = tpds, year = 1994, volume = 5, number = 10, pages = "1057--1072", annote = "Wie Powley und Co. aber genauere Untersuchung von Triggering Mechanismen. Analyse etwas krank: Sie nehmen an, routing auf CM-2 log^2 n braucht???" } @InProceedings{GupEtAl96, author = "A. Gupta and G. Karypis and V. Kumar", title = "Scalable Parallel Algorithms for Sparse Linear Systems", booktitle = "??", year = 1996, annote = "bis 1024 PEs einer T3D" } @TechReport{KumAna91, author = "V. Kumar and G. Y. Ananth", title = "Scalable Load Balancing Techniques for Parallel Computers", institution = "University of Minnesota", year = 1991, number = "TR 91-55", annote = "Isoeffizienzanalyse von: Round Robin (global/lokal) nearest neighbor, random polling, zentral, hierearchisch. Er benutzt allgemeines Framework das speziell auf global round robin zugeschnitten ist und z.B. fuer random polling nur eine Abschaetzung liefert, Randomized Allocation. Behandlung von variabler Nachrichtengroesse. Untere Schranke fuer Load Balancing Isoeffisienz von PD(P) ist zu optimistisch." } @InProceedings{KumNob91, author = "K. Kimura and N. Ichiyoshi", title = "Probabilistic Analysis of the efficiency of the dynamic load distribution", booktitle = "6th Distributed Memory Computing Conference", year = 1991, address = "Portland", annote = "Multi-Level Server based Scheduling. Benutzen probabilistisches Modell. Teilproblemgroessen sind (unabhaengige?) Zufallsvariablen. Fuer dieses Modell duerfte die Analyse OK sein." } % was Kum90 @InCollection{KumRao90, author = "V. Kumar and V. N. Rao", title = "Scalable parallel formulations of depth-first search", booktitle = "Parallel Algorithms for Machine Intelligence and Vision ", publisher = "Springer", year = 1990, editor = "V. Kumar", annote = "Weitere Sachen ueber Isoeffizienz. Aber ziemlich alte Sachen" } @TechReport{KumGup92, author = "V. Kumar and A. Gupta", title = "Analyzing Scalability of Parallel Algorithms and Architectures", institution = "University of Minnesota", year = 1992, number = "TR 91-18 revised", month = "January", annote = "Diskussiong verschiedener Skalierbarkeitsmasse" } @Article{RaoKum88, author = "V. N. Rao and V. Kumar", title = "Concurrent Access of Priority Queues", journal = ietc, year = 1988, volume = 37, number = 12, pages = "1657--1665", annote = "pipelining von log P updates. Funktioniert nur auf shared memory." } @Article{RaoKum87a, author = "V. N. Rao and V. Kumar", title = "Parallel Depth First Search. {Part} {I}", journal = ijpp, year = 1987, volume = 16, number = 6, pages = "470--499", annote = "Erstes Beispiel fuer grossen Speedup (128 PEs) 15 Puzzle" } @Article{RaoKum87b, author = "V. N. Rao and V. Kumar", title = "Parallel Depth First Search. {Part} {II}", journal = ijpp, year = 1987, volume = 16, number = 6, pages = "501--519", annote = "Analyse NN DLB fuer Ring und Hypercube" } @Article{RaoKum87ab, author = "V. N. Rao and V. Kumar", title = "Parallel Depth First Search.", journal = ijpp, year = 1987, volume = 16, number = 6, pages = "470--519", annote = "Analyse NN DLB fuer Ring und Hypercube" } @Article{RaoKum93, author = "V. N. Rao and V. Kumar", title = "On the Efficiency of Parallel Backtracking", journal = tpds, year = 1993, volume = 4, number = 4, pages = "427--437", month = "April", annote = "Verschiedene Beweise, die konsistente amortisierte Effizienz > 1 beweisen. Zweifelhaft: obskures Modell fuer ungleichmaessige Loesungsverteilung. Wer sagt, dass die nicht mit zunehmender Problemgroesse kleiner wird." } @Article{SinEtAl91a, author = "V. Singh and V. Kumar and G. Agha and C. Tomlinson", title = "Efficient Algorithms for Parallel Sorting on Mesh Multicomputers", journal = ijpp, year = 1991, volume = 20, number = 2, pages = "95--131", annote = "Langversion des ICPP papers" } @InProceedings{SinEtAl91, author = "V. Singh and V. Kumar and G. Agha and C. Tomlinson", title = "Efficient Algorithms for Parallel Sorting on Mesh Multicomputers", pages = "92--101", booktitle = "5th International Parallel Processing Symposium", year = 1991, publisher = "IEEE", annote = "erster Teil ziemlich trivial, ein bekannter Algorithmus wird naiv verallgemeinert und dann geilt er sich daran auf, das sein Algorithmus besser ist. Er benutzt parallels Quicksort mit zeilenweiser Knotennumerierung. QSP-2 ist asympt. optimal aber im strengen Sinne kein Sortieralg. weil die PE Numerierung dynamisch bestimmt wird. Erwaehnt Moeglichkeit Partition boundaries innerhalb eines PE zu erlauben. Macht aber falsche Abschaetzung des Kommunikationsaufwands. Sie haben massive Probleme mit Lastimbalance" } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Paderborn @TechReport{Bur94, author = "M. Buro", title = "The 1st International Paderborn Computer-Othello Tournament", institution = "Universit{\"a}t Paderborn", year = 1994, number = 141, annote = "Verweise auf einige interessante Othello papers" } @InCollection{MonEtAl90, author = "B. Monien and R. Feldmann and P. Mysliwietz and O. Vornberger", title = "Parrallel game tree search by dynamic tree decomposition", editor = "Vipin Kumar and P. S. Gopalakrishnan and Laveen Kanal", booktitle = "Parallel Algorithms for Machine Intelligence and Vision", publisher = "Springer-Verlag", address = "New York", year = "1990", } @InProceedings{FunEtAl92, author = "R. Funke and R. L{\"u}ling and B. Monien and F. L{\"u}cking and H. Blanke-Bohne", title = "An optimized reconfigurable architecture for Transputer networks", volume = 1, year = 1992, pages = "237--245", booktitle = "25th Hawaii Int. Conference on System Sciences", address = "Hawaii", annote = "Super Cluster" } @Article{BroSch00, author = "M. Brockington and J. Schaeffer", title = "{APHID}: Asynchronous Parallel Game-Tree Search", journal = "Journal of Parallel and Distributed Processing", year = 2000, pages = "247--273", annote = "asynchron im Sinne von wenigen Datenabhaengigkeiten. integriert mit starken Programmen, " } @Unpublished{Pla01, author = "A. Plagne", title = "On threshold properties of k-SAT. An additive viewpoint", note = " ", year = 2001, annote = "stacs01?" } @Unpublished{LorMon01, author = "U. Lorenz and B. Monien", title = "The Secret of Selective Game Tree Search, when Using Random-Error Evaluations", note = " ", year = 2001, annote = "stacs01?" } @InProceedings{FelEtAl91s, author = "R. Feldmann and P. Mysliwietz and B. Monien", title = "Distributed Game Tree Search on a Massively Parallel System", booktitle = "Data structures and efficient algorithms: Final report on the {DFG} special joint initiative", pages = "270--288", series = "LNCS", number = 594, year = 1991, annote = "noch besorgen" } @InProceedings{FelEtAl91, author = "R. Feldmann and P. Mysliwietz and B. Monien", title = "Distributed Game Tree Search on a Massively Parallel System", booktitle = "Data structures and efficient algorithms: Final report on the {DFG} special joint initiative", publisher = "Springer-Verlag", editor = "Th. Ottmann and B. Monien", pages = "270--288", series = "LNCS", number = 594, month = Sep, year = "1991", annote = "noch besorgen" } @Article{BenOtt79, author = "J. L. Bentley and T. A. Ottmann", title = "Algorithms for reporting and counting geometric intersections", pages = "643--647", journal = "IEEE Transactions on Computers", year = "1979", keywords = "algorithmic aspects, intersections, mathematical aspects, computational geometry, surface graphics, intersection", } @PhdThesis{Fel93, author = "R. Feldmann", title = "Game Tree Search on Massively Parallel Systems", school = "Universit{\"a}t Paderborn", type = "Dissertation", year = 1993, month = "August" } @InProceedings{FelEtAl94, author = "R. Feldmann and P. Mysliwietz and B. Monien", title = "Studying Overheads in Massively Parallel Min/Max-Tree Evaluation", pages = "94--103", booktitle = spaa, year = 1994, annote = "[12] ist Referenz fuer Othello, Kurze Skizze von Hsus Ansatz, Karp Zhang haben theor. Ergebnis verbessert.", address = "Cape May, NJ, 27--29 June", publisher = "ACM, New York", } @InProceedings{LueEtAl91, author = "R. L{\"u}ling and B. Monien and F. Ramme", booktitle = "3rd IEEE Symposium on Parallel and Distributed Processing", organization = "IEEE", title = "Load Balancing in Large Networks: {A} Comparative Case Study", year = "1991", annote = "Netter Rueckblich auf aeltere Arbeiten. Benutzung eines ausfuehrlichen Simulationsmodells zum Vergleich von Lastverteilungsalgorithmen. Best first Suche. Klassifikation von DLB nach lokal/global Entscheidungen, lokal/global Lastbewegung, sender/empfaenger- initiiert. Hinweis auf 2 mir unbekannte Algorithmen (bidding, drafting) aber die sind ziemlich schlecht. Deutlich verbesserte version des Gradienten modells: Es wird explizit gesagt, dass mit alten Werten gearbeitet wird; symmetrische Behandlung von High/Low belasteten PEs. Weitere Variante: Pakete werden von Medium PEs direkt entsprechend dem Gradienten weitergeleitet. Gutes Beispiel warum inflexible Routing Hardware ein Problem sein koennte. Interessanter Hinweis dass auch 324 PEs noch nicht reichen um ueber DeBruijn und Co vernuenftige Aussagen zu machen; Deshalb Torus und sogar Ring." } @InProceedings{LueMon92, author = "R. L{\"u}ling and B. Monien", booktitle = "Int. Parallel Processing Symposium (IPPS)", key = "new", title = "Load Balancing for Distributed Branch \& Bound Algorithms", year = "1992", annote = "best first mit neighborhood averaging. Flusskontrolle: erst balancieren wenn last sich um bestimmten Faktor geaendert hat. Zusaetzlich Flussbeschraenkung waere aber leichter durch Prozesspriotitaeten zu modellieren. Zwei Literaturhinweise. Z.B. am besten 2. besten Knoten abgeben. Interessante Diskussion wie die Last eines PE unter beruechsichtigung der Qualitaet gemessen werden kann. Benutzen sowas wie direkte Initialisierung (fuer Vertex Cover)" } @InCollection{MonEtAl96, author = "B. Monien and R. Dickmann and R. Feldmann and R. Klasing and R. L{\"u}ling and Knut Menzel and R. R{\"o}mke and U. Schroeder", title = "Efficient Use of Parallel \& Distributed Systems: From Theory to Practice ", booktitle = "Computer Science Today", publisher = "Springer", year = 1996, number = 1000, series = "LNCS" } @Book{Rei89, author = "Alexander Reinefeld", title = "Spielbaum-{Suchverfahren}", publisher = "Springer-Verlag", address = "New York, NY", series = "Informatik-Fachberichte ", number = "200", year = "1989", avcode = "available -- ETHICS", } @InCollection{LueEtAl96, author = "R. L{\"u}ling and B. Monien and A. Reinefeld and S. Tsch{\"o}ke", title = "Mapping Tree-Structured Conbinatorial Optimization Problems onto Parallel Computers", booktitle = "Solving Combinatorial Optimization Problems in Parallel", publisher = "Springer", year = 1996, editor = "A. Ferreira and P. M. Pardalos", pages = "127--144", annote = "Zusammenfassung von altem Kram. Zahlen zu Vertex Cover auf 1024 PEs" } @InCollection{Tsc94, author = "S. Tsch{\"o}ke", title = "A Portable Parallel Branch-and-Bound Library (PPBB-Lib)", booktitle = "{PC$^2$} User Report", publisher = "{PC$^2$}", year = 1994, editor = "B. Bauer", number = "TR-009-94", month = "Jun.", pages = "31--33" } @InCollection{CorFer96, author = "R. Corr{\^e}a and A. Ferreira", title = "Parallel Best-First Branch-and-Bound in Discrete Optimization: a Framework", booktitle = "Solving Combinatorial Optimization Problems in Parallel", publisher = "Springer", year = 1996, editor = "A. Ferreira and P. M. Pardalos", pages = "171--200", annote = "Uebersicht ueber implementierte Anwendungen, Lastverteilungsstrategien. Offenenes Problem: real world Anwendungen." } @InCollection{BenEtAl96, author = "M. Bena{\"\i}ouche and V. Cung and S. Dowaji and Le Cun, B. and T. Mautor and C. Roucairol", title = "Building a Parallel Branch and Bound Library", booktitle = "Solving Combinatorial Optimization Problems in Parallel", publisher = "Springer", year = 1996, editor = "A. Ferreira and P. M. Pardalos", pages = "201--231", annote = "Behaupted D-Heap sei ineffizient" } @InCollection{BruEtAl96, author = "de Bruin, A. and G. A. P. Kindervater and H. W. J. M. Trienekens", title = "Towards an Abstract Parallel Branch and Bound Machine", booktitle = "Solving Combinatorial Optimization Problems in Parallel", publisher = "Springer", year = 1996, editor = "A. Ferreira and P. M. Pardalos", pages = "145--170", annote = "Hauptsaechlich best first. Schichtenmodell kommt mir bekannt vor. Uebersicht ueber abstrakte Modelle, bisherige Bibliotheken. Erwaehnen explizit, das existierende Bibliotheken die Zielarchitektur festhalten." } @InCollection{CunRou95, author = "Le Cun, B. and C. Roucairol", title = "Concurrent Data Structures for Tree Structured Search Algorithms", booktitle = "Parallel Algorithms for Irregular Problems: State of the Art", publisher = "Kluwer", year = 1995, editor = "A. Ferreira and J. D. P. Rolim", chapter = 7, pages = "135--155", annote = "eigentlich proceedings Irregular 94, Ueberblick ueber PPQ Verfahren. Verwaltung von open und closed set gleichzeitig durch treap in A*" } @InCollection{CorFer95, author = "R. Corr{\^e}a and A. Ferreira", title = "A distributed implementation of asynchronous parallel branch and bound", booktitle = "Parallel Algorithms for Irregular Problems: State of the Art", publisher = "Kluwer", year = 1995, editor = "A. Ferreira and J. D. P. Rolim", chapter = 8, pages = "157--176", annote = "eigentlich Proceedings Irregular 94. Wenig spannden. Best first fuer Rucksack Problem" } @InCollection{Sod95, author = "A. Sodan", title = "Atredia: A mapping environment for dynamic tree-structured problems", booktitle = "Parallel Algorithms for Irregular Problems: State of the Art", publisher = "Kluwer", year = 1995, editor = "A. Ferreira and J. D. P. Rolim", chapter = 14, pages = "269--296", annote = "Lisp, GMD-FIRST Berlin, elaborates Verfahren fuer Teilproblemgroessenvorraussage. Einige Argumente gegen Tree splitting - kann man widerlegen" } @InProceedings{MonEtAl92, author = "B. Monien and R. L{\"u}ling and F. Langhammer", title = "A realizable efficient parallel architecture ", number = 678, series = "LNCS", pages = "93--109", booktitle = "First Heinz Nixdorf Symposium", year = 1992, annote = "clos" } @TechReport{LueMon94, author = "R. L{\"u}ling and B. Monien", title = "A Dynamic Load Balancing Algorithm with Provable Good Performance", institution = "Universit{\"a}t Paderborn", year = 1994, annote = "Mischung aus Random Polling und Random Distribution. Trigger: lokale Aenderung um bestimmten Faktor. Gute Literaturuebersicht. Zunaechst wird Ew_i/Ew_j wird bestimmt-> konstanter Faktor. Zusaetzlich wird die Variationsdichte bestimmt (stdAbw/E). Frage wie uebersetzt sich das in Maximum? Interessant: Anwendung des Banachschen Fixpunktsatzes. Problem damit: das ist nur eine Grensbetrachtung und es ist nicht ganz klar wie schnell sich dieses Gleichgewicht einstellt. Ist es mal hergestellt wird es aber wohl bestehen bleiben. " } @Book{AaKo89, author = "E. H. L. Aarts and J. H. M Korst", address = "Chichester, U.K.", publisher = "John Wiley \& Sons", title = "Simulated Annealing and Boltzmann Machines", year = "1989", annote = "Book providing an overview of simulated annealing techniques and issues.", } @TechReport{AKV00b, author = {Aerts,J. and Korst,J. and Verhaegh,W.}, title = {Complexity of retrieval problems}, institution = {Philips Research Laboratories}, year = {2000}, number = {NL-MS-20.899}, place = {Eindhoven, The Netherlands} } @InProceedings{AKV00, author = "J. Aerts and J. Korst and W. Verhaegh", title = "Load balancing in multimedia servers", booktitle = "Workshop on Project Management and Scheduling PMS", pages = "25--28", year = 2000 } @Article{Tov84, author = "C. A. Tovey", title = "A simplified {NP}-complete satisfiability problem", journal = "Discrete Applied Mathematics", year = 1984, volume = 8, pages = "85--89" } @Article{AKE00a, author = "J. Aerts and J. Korst and S. Egner", title = "Random duplicate storage for load balancing in multimedia servers", journal = "Information Processing Letters", volume = "76", number = "1--2", year = 2000, pages = "51--59", } @TechReport{DieEtAl93, author = "R. Diekmann and R. L{\"u}eling and J. Simon", title = "Problem Independent Distributed Simulated Annealing and its Applications", institution = "Universit{\"a}t Paderborn", year = 1993, note = "Auch auf SPDP 92", annote = "Ebenen der Parallelitaet: Bewertung eines Kandidaten -> Anwendungsspezifisch; Generierung u. Bewertung von Muatanten -> Geringe Parallelitaet zu Beginn; Betrachtung paralleler Entwicklungsfaeden: Konvergenzprobleme oder viel redundante Arbeit. Synthese: Zu Beginn viele Parallel Faeden gegen Schluss weniger werdend. Speedup 70 bei 120 PEs 320 hatte wohl keinen Sinn? Anwendung fuer TSP und SuperCluster Konfigurierung" } @Article{BerDas00, author = "P. Berman and B. DasGupta", title = "Multi-phase Algorithms for Throughput Maximization for Real-Time Scheduling", journal = "Journal of Combinatorial Optimization", year = 2000, volume = 4, number = 3, pages = "307--323", annote = "use van Emde Boas trees" } @InCollection{KroVor90, author = "B. Kr{\"o}ger and O. Vornberger", title = "Enumerative vs. Genetic Optimization. Two Parallel Algorithms for the Bin Packing Problem", booktitle = "Data Structures and Efficient Algorithms: Final Report on the DFG Special Joint Initiative", publisher = "Springer", year = 1990, editor = "B. Monien and T. Ottmann", number = 594, series = "LNCS", annote = "2D Bin Packing, 32 T800" } @InProceedings{MonEtAl94, author = "B. Monien and R. Diekmann and R. L{\"u}ling", title = "Communication Throughput of Interconnection Networks", series = "LNCS", booktitle = "MFCS", year = 1994, publisher = "Springer", annote = "Referenz auf Wormhole Analyse. Betrachten anderes Mass als Bisektionsbreite" } @InProceedings{Rei93, author = "A. Reinefeld", title = "Complete Solution of the Eight-Puzzle and the Benefit fo Node Ordering in {IDA*}", pages = "248--253", booktitle = "13th International Conference on Artificial Intelligence", year = 1993, address = "Chambery, France", annote = "Daten darueber was best first sowie Tabellen bringen" } @Unpublished{FraGarLuq99, author = "D. Franco and I. Garc{\'{e}}s and E. Luque", title = "An Analytical Model of the Interconnection Network Latency Behavior", note = " ", annote = "Europar'99 eingereicht" } @Unpublished{FraGarLuq99, author = "D. Franco and I. Garc{\'{e}}s and E. Luque", title = "A New Method to Avoid Hot Spots in Interconnection Networks for Parallel Computers", note = " ", annote = "Europar'99 eingereich" } @InProceedings{Rei94, author = "A. Reinefeld", title = "Scalability of Massively Parallel Depth-First Search", booktitle = "Parallel Processing of Discrete Optimization Problems", pages = "305--322", year = 1995, number = 22, series = "DIMACS Series in Discrete Mathem. and Theor. Comp. Sc.", publisher = "AMS-Press, New York" } @InProceedings{ReiSch94a, author = "A. Reinefeld and V. Schnecke", title = "Work-Load Balancing in Highly Parallel Depth-First Search", pages = "773--780", booktitle = "Scalable High Performance Computing Conference", year = 1994, address = "Knoxville", annote = "PDFS, Initialisierung durch replizierte Breitensuche, so erzeugt Pakete gelten als unteilbar. DLB Nachbarschafts Polling mit weiterreichen. Anwendungen 15-Puzzle und floorplan optimization." } @InProceedings{ReiSch94b, author = "A. Reinefeld and V. Schnecke", title = "{AIDA*} --- Asynchronous Parallel {IDA*}", booktitle = "10th Canadian Conference on Artificial Intelligence", year = 1994, address = "Banff", annote = "Praktisch, detaillierte Daten ueber einzelne Probleme" } @InProceedings{Rei94c, author = "A. Reinefeld", title = "Effective Parallel Backtracking Methods for Operations Research Applications.", booktitle = "International Conference Massively Parallel Processing Applications and Development", year = 1994, pages = "117--124", address = "Delft", annote = "das uebliche" } @TechReport{TscEtAl94, author = "S. Tsch{\"o}ke and M. R{\"a}cke and R. L{\"u}ling and B. Monien", title = "Solving the Traveling Salesman Problem with a Parallel Branch-and-Bound Algorithm on a 1024 Processor Network", institution = "Universit{\"a}t Paderborn", year = 1994, annote = "LB mit Nachbarschaftskomm. a la Mc Keown + Co. aber niemanden zitiert. Guter Speedup fuer Probleme mit 200-800 s Tpar und extrem aufwendiger Knotenauswertungsfunktion. Fuktioniert bis 318 Staedte." } @InProceedings{TscEtAl94b, author = "S. Tsch{\"o}ke and R. L{\"u}ling and B. Monien", title = "{E}ine {T}oolbox {z}ur {a}utomatischen {P}arallelisierung {b}eliebiger {B}ranch \& {B}ound {A}pplikationen", pages = "149--154", booktitle = "Transputer Anwender Treffen", year = 1994, publisher = "IOS Press" } @InProceedings{TscHol95, author = "S. Tsch{\"o}ke and N. Holth{\"o}fer", title = "A New Parallel Approach to the Constrained Two-Dimensional Cutting Stock Problem", pages = "285--299", booktitle = "Workshop on Algorithms for Irregularly Structured Problems", year = 1995, publisher = "Springer", address = "Lyon" } @InProceedings{Vor87, author = "O. Vornberger", title = "Implementing Branch-and-Bound in a Ring of Processors", pages = "157--164", booktitle = "{CONPAR}", year = 1987, publisher = "Springer", annote = "Hier hat Reinefeld sein Initialisierung durch Breitensuche her?" } @Article{Vor88, title = "Load Balancing in a Network of Transputers", journal = "2nd International Workshop on Distributed Algorithms", address = "Amsterdam", pages = "116--126", author = "O. Vornberger", year = 1988, month = jun, annote = "Beschreibt Vertex Cover" } @Book{BKOS97, author = "de Berg, M. van Kreveld, M. and Overmars, M. and O. Schwarzkopf", title = "Computational Geometry Algorithms and Applications", publisher = "Springer-Verlag", EDITION = {2., rev. ed.}, address = "Berlin Heidelberg", year = "2000", ISBN = "3-540-61270-x", descriptor = "Geometrische Algorithmen", } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Karlsruhe @TechReport{KucEtAl93b, author = "N. Kuck and M. Middendorf and H. Schmeck", title = "Generic Branch-and-Bound on a Network of Transputers", institution = "Universit{\"a}t Karlsruhe, AIFB", year = 1993, number = 283, annote = "Wie Konferenzpaper" } @InProceedings{Gut04, author = "R. Gutman", title = "Reach-based Routing: A New Approach to Shortest Path Algorithms Optimized for Road Networks", booktitle = "Alenex", year = 2004, annote = "patented" } @TechReport{GolHar03, author = "A. V. Goldberg and C. Harrelson", title = "Computing the Shortest Path: $A^*$ Meets Graph Theory", institution = "Microsoft Research", year = 2004, number = "MSR-TR-2004-24", annote = "date is March 19, 2003. concept of landmarks for computing lower bounds" } @InProceedings{GolMor99, author = "A. Goldberg and B. Moret", title = "Combinatorial Algorithms Test Sets (CATS)", booktitle = "10th {ACM}-{SIAM} Symposium on Discrete Algorithms", pages = "", year = 1999 } @Article{OOW99, author = "O'Neil and O'Neil and Weikum", title = "An Optimality Proof of the {LRU}-{K} Page Replacement Algorithm", journal = "JACM: Journal of the ACM", volume = "46", year = "1999", } @InCollection{Ira98, author = "S. Irani", title = "Competetive Analysis of Paging", booktitle = "Online Algorithms --- The State of the Art", pages = "52--73", publisher = "Springer", year = 1998, volume = 1442, series = "LNCS" } @article{NaoRei99, author = "M. Naor and O. Reingold", title = "On the Construction of Pseudorandom Permutations: {Luby-Rackoff} Revisited", journal = "Journal of Cryptology: the journal of the International Association for Cryptologic Research", volume = "12", number = "1", pages = "29--66", year = "1999", url = "citeseer.nj.nec.com/article/naor97construction.html" } @Article{Fei98, author = "U. Feige", title = "A threshold of $\ln n$ for approximating set cover", journal = "Journal of the ACM", volume = "45", number = "4", pages = "634--652", month = jul, year = "1998", coden = "JACOAH", ISSN = "0004-5411", bibdate = "Wed Dec 16 07:11:23 MST 1998", url = "http://www.acm.org:80/pubs/citations/journals/jacm/1998-45-4/p634-feige/", abstract = "Given a collection {\em F\/} of subsets of S = {1,...,n}, set cover is the problem of selecting as few as possible subsets from {\em F\/} such that their union covers S,, and max k-cover is the problem of selecting k subsets from {\em F\/} such that their union has maximum cardinality. Both these problems are NP-hard. We prove that (1 - o(1)) ln n is a threshold below which set cover cannot be approximated efficiently, unless NP has slightly superpolynomial time algorithms. This closes the gap (up to low-order terms) between the ratio of approximation achievable by the greedy alogorithm (which is (1 - o(1)) ln n), and provious results of Lund and Yanakakis, that showed hardness of approximation within a ratio of {\em log2 n/2\≃0.72 \/} ln n. For max k-cover, we show an approximation threshold of (1 - 1/e)(up to low-order terms), under assumption that {\em P\≠NP \/}.", acknowledgement = ack-nhfb, keywords = "algorithms; performance; theory", subject = "{\bf F.1.2} Theory of Computation, COMPUTATION BY ABSTRACT DEVICES, Modes of Computation, Probabilistic computation. {\bf F.2.2} Theory of Computation, ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY, Nonnumerical Algorithms and Problems, Computations on discrete structures. {\bf F.1.3} Theory of Computation, COMPUTATION BY ABSTRACT DEVICES, Complexity Measures and Classes.", } @InProceedings{KucEtAl93, author = "N. Kuck and M. Middendorf and H. Schmeck", title = "Generic Branch-and-Bound on a Network of Transputers", editor = "R. Grebe and others", pages = "521--535", booktitle = "Transputer Applications and Systems", year = 1993, publisher = "IOS Press", annote = "Guter Artikel, Lastverteilung lokal, adaptiv, Algorithmen geneisch, TSP , Set Cover, hybride Tiefen/besten-suche. Mein Senf zum Code: Kein konsequentes ANSI C; interfaces haben oft recht viele Parmeter also u.u. ineffizient. Selbst eine Referenz auf die globalen Daten wird immer mit uebergeben also old fashionel structured programming; incumbent ist ziemlich festgeklopft. immer eine minimale Loesung suchen." } @InProceedings{But94a, author = "R. Butenuth and S. Gilles", title = "{C\sc OSY} --- ein {Betriebssystem} f{\"u}r hochparallele {Computer}", booktitle = "Transputer Anwender Treffen", address = "Aachen", year = 1994 } @Article{ButHei96a, author = "R. Butenuth and H.-U. Hei{\"s}", title = "Skalierbare Gruppenkommunikation in Netzen mit beliebiger Topologie", journal = "SIGOPS", year = 1996 } @InProceedings{Hen93, author = "D. Henrich", title = "Initialization of parallel branch-and-bound algorithms", number = 2, booktitle = "International Workshop on Parallel Processing for Artificial Intelligence", year = 1993, publisher = "Elsevier", address = "Chambery" } @InProceedings{Hen94a, author = "D. Henrich", title = "Load Balancing for Data Parallel Branch-and-Bound", booktitle = "International Conference Massively Parallel Processing Applications and Development", pages = "227--234", year = 1994, publisher = "Elsevier", address = "Delft" } @InProceedings{Hen94as, author = "D. Henrich", title = "Load Balancing for Data Parallel Branch-and-Bound", booktitle = "Int. Conf. Massively Parallel Processing", year = 1994, publisher = "Elsevier" } @PhdThesis{Hen94b, author = "D. Henrich", title = "Lastverteilung f{\"u}r Branch-and-bound auf eng-gekoppelten Parallelrechnern", school = "Universit{\"a}t Karlsruhe", type = "Dissertation", year = "1994" } @PhdThesis{Hen94be, author = "D. Henrich", title = "Lastverteilung f{\"u}r Branch-and-bound auf eng-gekoppelten Parallelrechnern", school = "Universit{\"a}t Karlsruhe", year = "1994" } @InProceedings{Hen95a, author = "D. Henrich", title = "Local load balancing according to a simple liquid model", series = "PARS Mitteilungen", booktitle = "PARS Workshop", year = 1995, address = "Stuttgart", annote = "Echte Teilmenge von paper fuer Journal of Parallel Algorithms and Applications." } @Article{Hen95b, author = "D. Henrich", title = "The Liquid Model Load Balancing Method", journal = "Journal of Parallel Algorithms and Applications", year = 1995, note = "Special Issue on Algorithms for Enhanced Mesh Architectures", annote = "Obermenge von Hen95a" } @Article{HarHarTri00, author = "S. Harizououlos and C. Hariazakis and P. Triantafillou", title = "Hierarchical Caching and Prefetching for Continous Media Servers with Smart Disks", journal = "IEEE Concurrency", year = 2000, month = "July--September", annote = "Praktikerpapier. Sweep/Scan stategie grouped periodic multiround prefetching. Empirische Erkenntisse wann es nichts mehr bring batches groesser zu machen" } @InProceedings{Luk96, author = "P. Lukowicz", title = "A concept for an opto electronic smart pixel based concurrent read concurrent write shared memory", booktitle = "Third International Conference on Massively Parallel Processing Using Optical Interconnections", year = 1996, address = "Maui, Hawaii" } @Unpublished{Min94, author = "T. Minkwitz", title = "Personal communication", note = "Department of Informatics, University of Karlsruhe", year = 1994 } @Unpublished{Min95, author = "T. Minkwitz", title = "Personal communication", note = "Department of Informatics, University of Karlsruhe", year = 1995 } @PhdThesis{Non96, author = "A. Nonnenmacher", title = "Fl{\"u}ssigkristallsimulation mit automatischem Diffenzieren und Intervallarithmetik", school = "Universit{\"a}t Karlsruhe", year = 1996, type = "Dissertation", annote = "Anwengung von B-u-B und Tiefensuche zur Suche globaler und lokaler Optima nichtlinearer Funktionen." } @Article{Han80, author = "E. Hansen", title = "Global Optimization using Interval Analysis -- the Multidimensional Case", journal = "Numerische Mathematik", year = 1980, volume = 34, pages = "247--270" } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Parallele Suche sonstiges @InProceedings{SpeMonVor87, author = "E. Speckenmeyer and B. Monien and O. Vornberger", title = "Superlinear Speedup for Parallel Backtracking", pages = "985--993", ISBN = "3-540-18991-2", editor = "C. D. {Houstis, E. N.; Papatheodorou, T. S.; Polychronopoulos}", booktitle = "Proceedings of the 1st International Conference on Supercomputing", address = "Athens, Greece", month = jun, year = "1987", series = "LNCS", number = "297", publisher = "Springer", } @Article{BoeSpe96, author = "M. B{\"o}hm and E. Speckenmeyer", institution = "Informatik, Universit{\"a}t zu K{\"o}ln", journal = "Annals of Mathematics and Artificial Intelligence", title = "A Fast Parallel {SAT}-Solver -- Efficient Workload Balancing", volume = 17, pages = "381--400", year = 1996, crindex = "72k,15,zpr94-159.ps.gz", annote = "We present a fast parallel SAT-solver on a message based MIMD machine. The input formula is dynamically divided into disjoint subformulas. Small subformulas are solved by a fast sequential SAT-solver running on every processor, which is based on the Davis-Putnam procedure with a special heuristic for variable selection. The algorithm uses optimized data structures to modify boolean formulas.<br> Additionally efficient workload balancing algorithms are used, to achieve a uniform distribution of workload among the processors.We consider the communication network topologies $d$-dimensional processor grid and linear processor array. Tests with up to 256 processors have shown very good efficiency-values ($>0.95$).", } @TechReport{BoeSpe94, author = "M. B{\"o}hm and E. Speckenmeyer", title = "A Fast Parallel {SAT}-Solver -- Efficient Workload Balancing", institution = "Universit{\"a}t K{\"o}ln", year = 1994, number = "94.159", annote = "Auch in Annals of Math. and AI. Detaillierte Beschreibung der Implemenitierung. Die seq. Datenstrukturen sind ziemlich gut. -> SA. Lastverteilung etwas ad hoc, kann ich besser ? Fuer jede Dimension: Prefixsumme der Last. Durchschnitt berechnen Ring formig verschieben. Zur Lastabschaetzung wird heuristisch bestimmter Exponent hoch anzahl verbleibender Variablen verwendet. Effiziente Ausfuehrungszeiten auf 256 PEs ist ca. 150s" } @InProceedings{BoeSpe94b, author = "M. B{\"o}hm and E. Speckenmeyer", title = "Effiziente {L}astausgleichsverfahren", pages = "53--60", booktitle = "Transputer Anwender Treffen", year = 1994, publisher = "IOS Press", address = "Aachen", annote = "Aehnlicch TR aber konsentriert auf lastverteilung. Feedback Vertex Set Problem: wievile Kanten entfernen, damit Kreisfrei" } @InProceedings{CunCun94, author = "V. Cung and B. L. Cun", title = "An Efficient Implementation of Parallel {A*}", booktitle = "First Canada France Conference on Parallel and Distributed Computing", year = 1994, annote = "shared memory. Zentraler treap fuer open kann deleteMin und Search. Begrenzt paralleler Zugriff durch partial locking. Sie kriegen Speicherprobleme, Speedup kann man nicht ablesen aber mehr als 4 auf 8 PE Sequent und 2-5 auf KSR1 sind nicht drin." } @InProceedings{DutMah93, author = "S. Dutt and M. R. Mahapatra", title = "Parallel {A*} Algorithms and their Performance on Hypercube Multiprocessors", booktitle = ipps, year = 1993, address = "Newport Beach", annote = "Beispiel, das jemand Multiprocessor fuer Distributed Memory gebraucht (Hypercube)! Lokale Duplicate detection wird als parallel verkauft. neue bounds werden gebroadcasted! 2 Arten von Nachbarschaftskommunikation: wird die Last irgendwo Knapp (Schwelle), so wird lokal neighborhood averaging durchgefuehrt. Hat ein PE deutlich schlechtere Knoten als sein Nachbar (adhoc Kriterium) so werden einige gute Knoten abgegeben. Interessante Initialisierung ohne KOmm: Generiere kurze Liste von Knoten und spalte dann in zwei Teile wiederhole bis Symmetrie gebrochen." } @InProceedings{HerEtAl96, author = "K. T. Herley and A. Pietracaprina and G. Pucci", title = "Fast Deterministic Backtrack Search", booktitle = "ICALP", year = 1996, publisher = "Springer", address = "Paderborn", pages = "598--609", annote = "Abgedrehter CRCW Algorithmus mit Zeitbedarf O((n/p + h)logloglog p). Hinweis auf 'approximate prefix sum'" } @InProceedings{MahDut96, author = "N. R. Mahapatra and S. Dutt", title = "Random Seeking: A General, Efficient, and Informed Randomized Scheme for Dynamic Load Balancing", pages = "??", booktitle = "International Parallel Processing Symposium", year = 1996, annote = "Etwas abstruse Variante von Luelings Algorithmus fuer par. B&B. Nette Anwendungsbeispiele: Integer Linear Programming. Hinweis auf Beispielproblemressource." } @InProceedings{HuaDav89, author = "S. Huang and L. S. Davis", title = "Parallel Iterative A* Search: An Admissible Distributed Heuristic Search Algorithm", pages = "23--29", booktitle = "International Joint Conference on AI", year = 1989, annote = "Verteilte PQ aber sobald alle PEs nur noch spekulative Knoten auswerten, wird synchronisiert, ein neuer incumbent berechnet und zwischendurch generierten Knoten round-robin maessig verteilt." } @InProceedings{KakPer92, author = "C. Kaklamanis and G. Persiano", title = "Branch-and-Bound and Backtrack Search on Mesh-Connected Arrays of Processors", booktitle = spaa, year = 1992, annote = "Betrachtet nur Baeuume der groesse O(n). Nutzt Hilbert Kurven aber kennt Miller Stout nicht. Benutzt sowas wie lokales Rendevous. ", address = "San Diego, CA, 29 June -- 1 July", publisher = "ACM, New York", } @Article{KakPer94, author = "C. Kaklamanis and G. Persiano", title = "Branch-and-Bound and Backtrack Search on Mesh-Connected Arrays of Processors", journal = "Mathematical Systems Theory", year = 1994, volume = 27, pages = "471--489", annote = "Full Version des SPAA Papers, Hilbert wird nun zitiert (1 Fehler pro Wort :-)." } @InCollection{PowEtAl90, author = "Curt Powley and Chris Ferguson and Richard E. Korf", editor = "Vipin Kumar and P. S. Gopalkrishnan and Laveen N. Kanal", title = "Parallel Heuristic Search: Two Approaches", booktitle = "Parallel Algorithms for Machine Intelligence and Vision", pages = "42--65?", publisher = "Springer-Verlag", month = mar, year = "1990", } @InProceedings{WuKun91, author = "I. C. Wu and H. T. Kung", title = "Communication Complexity of Parallel Divide-and-Conquer", pages = "151--162", booktitle = "32nd Symposium on Foundations of Computer Science", address = "San Juan, Puerto Rico, 1--4 October", publisher = "IEEE, Los Alamitos, CA", year = 1991, annote = "Divide and conque laesst sich hier auch als Baumsuche auffassen. Vollstaendig verbunden. Lower bound fuer max PE Last und Kommunikationskosten. Beiweis geht ueber 6 engbedruckte Seiten. Scheint nur fuer deteministische LV zu gelten Zitiert Finkel Manber, Rao Kumar und Zhang. LV Algotithmus arbeitet mit globalem Pool. Mein SIMD Algorithmus laesst sich als effiziente Implementation dieses Schemas auffassen. Auch gewisse Verwandschaft zu Global Round Robin. Aber Kumar zitiert ihn nicht." } @Book{Pop34, author = "K. R. Popper", title = "Logik der Forschung", publisher = "Springer", year = 1934, note = "English Translation: {\emph{The Logic of Scientific Discovery}}, Hutchinson, 1959" } @InProceedings{BeiSib00, author = "Beier, R. and Sibeyn, J. F. ", title = "A Powerful Heuristic for Telephon Gossiping", booktitle = "7th Colloquium on Structural Information and Communication Complexity", pages = "17-35", year = 2000 } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Theorie parallele Suche @inproceedings{pamoz, author = {Konstantin Popov}, title = {A Parallel Abstract Machine for the Thread-Based Concurrent Constraint Language {Oz}}, booktitle = {Workshop On Parallism and Implementation Technology for (Constraint) Logic Programming Languages}, editor = {In\^es de Castro Dutra and V{\'\i}tor Santos Costa and Fernando Silva and Enrico Pontelli and Gopal Gupta}, year = {1997}, } @Article{LinYan95, author = "W-M. Lin and B. Yang", title = "Probabilistic Performance Analysis for Parallel Search Techniques", journal = "International Journal of Parallel Programming", volume = "23", number = "2", pages = "161--189", month = apr, year = "1995", coden = "IJPPE5", ISSN = "0885-7458", bibdate = "Sat Apr 26 11:36:49 MDT 1997", acknowledgement = ack-nhfb, affiliation = "Univ of Texas", affiliationaddress = "San Antonio, TX, USA", classification = "721.1; 722.4; 921.6; 922.1; C1180 (Optimisation techniques); C4240P (Parallel programming and algorithm theory); C5440 (Multiprocessing systems); C6170K (Knowledge engineering techniques)", corpsource = "Div. of Eng., Texas Univ., San Antonio, TX, USA", journalabr = "Int J Parallel Program", keywords = "computation steps; Computational methods; constraint handling; Constraint satisfaction problem; constraint satisfaction problem solving; Constraint theory; depth first search; Depth first search; Load balancing activity; load-balancing; parallel algorithms; Parallel processing systems; parallel search techniques; Parallel search techniques; Performance; performance evaluation; probabilistic analysis; Probabilistic performance analysis; probabilistic performance analysis; Probability; probability; Problem solving; problem solving; resource allocation; Shared memory multi processor systems; shared memory multi-processor systems; shared memory systems; tree searching", treatment = "T Theoretical or Mathematical", } @InProceedings{RTAS00*23, author = "P. Bosch and S. Mullender", title = "Real-Time Disk Scheduling in a Mixed-Media File System", pages = "23--33", booktitle = "Proceedings of the Sixth {IEEE} Real-Time Technology and Applications Symposium ({RTAS} '00)", ISBN = "0-7695-0713-X", month = jun, publisher = "IEEE", address = "Washington - Brussels - Tokyo", year = "2000", } @PhdThesis{Bos99, author = "H. G. P. Bosch", title = "Mixed-Media File Systems", school = "University of Twente, Netherlands", year = 1999 } @Article{BosEtAl92, title = "{PARTHENON}: {A} Parallel Theorem Prover for Non-{Horn} Clauses", author = "S. Bose and E. M. Clarke and D. E. Long and S. Michaylov", journal = "Journal of Automated Reasoning", pages = "153--181", month = apr, year = "1992", volume = "8", number = "2", } @PhdThesis{Ert92, author = "W. Ertel", title = "Parallele Suche mit randomisiertem Wettbewerb in Inferenzsystemen", school = "TU M{\"u}nchen", type = "Dissertation", year = 1992 } @PhdThesis{Ert92e, author = "W. Ertel", title = "Parallele Suche mit randomisiertem Wettbewerb in Inferenzsystemen", type = "Dissertation", school = "TU M{\"u}nchen", year = 1992 } @InProceedings{PraAgrAbb98, author = "S. Prabhakar and D. Agrawal and A. E. Abbadi", title = "Efficient Disk Allocation for Fast Similarity Searching", pages = "78--79", booktitle = "10th ACM Symposium on Parallel Algorithms and Architectures", annote = "nearest neighbor" } @InProceedings{JanEtAl87, author = "V. K. Janakiram and D. P. Agrawal and R. Mehotra", title = "Randomized Parallel Algorithms for {P}rolog Programs and Backtracking Applications", pages = "278--281", booktitle = icpp, year = 1987, annote = "Vollstaendig zufaelliges Traversieren des Baums durch unabhaengige Agenten. Modifikation: Toplevels des Baums durch zentraliesierten Scheduler verwalten. Modell fur Zufallssuchbaeume: Jeder Knoten hat eine Verzweigungswahrscheinlichkeit fur jeden moeglichen Grad. (0 verboten) i.allg. kann die Wahrscheinlichkeit von der Tiefe abhangen. Aber Knoten auf einer Ebene muessen unabhaengig sein. Mache das bis zu einer festen Tiefe. Baeume? Branching process? Eine weitere Verteilungsfunktion legt fest, welche Blaetter Loesungen sind (alle in gleicher Tiefe. Wenn man will kann man an der Mathe einiges zerpfluecken. Sie behaupten sie haetten cutoff Funktionen modelliert. Aber Informationsfluss durch den Baum findet nicht statt." } @Article{JanEtAl88, author = "V. K. Janakiram and E. F. Gehringer and D. P. Agrawal and R. Mehotra", title = "A Randomized Parallel Branch-and-Bound Algorithm", journal = ijpp, year = 1988, volume = 17, number = 3, pages = "277--301", annote = "best first. Beweise nicht verstanden. Shared memory. Wenig Prozessoren." } @InProceedings{Nat89, author = "K. S. Natarajan", title = "Expected Performance of Parallel Search", volume = "III", pages = "121--125", booktitle = icpp, year = 1989, annote = "Scheinbar das gleiche wie Janakiram, zitiert ihn aber nicht. Referenz auf Buch ueber order statistics." } @Book{Pea84, author = "Judea Pearl", title = "Heuristics", publisher = "Addison Wesley", year = 1984, annote = "Viele Theorie sachen. Z.B. Beispiele fuer polynomielle Baumsuche" } @TechReport{Jai94, author = "S. Jain", title = "Branch and Bound on the Network Model", institution = "University of Singapore", year = 1994, annote = "Bei sehr grosser Last reicht es, nur selten etwas zu Verschicken um aehnliche Leistung wie Karp/Zhang zu erreichen. sanjay@iss.nus.sg" } @TechReport{GarKoe98, author = "N. Garg and J. K{\"o}hnemann", title = "Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems", institution = "MPII", year = "1998??" } @InProceedings{BeiVoe03, author = "R. Beier and B. V{\"o}cking", title = "Random Knapsack in Expected Polynomial Time", booktitle = "35th ACM Symposium on Theory of Computing", year = 2003 } @PhdThesis{Zie01, author = "M. Ziegelmann", title = "Constrained Shortest Paths and Related Problems", school = "Saarland University", year = 2001 } @InProceedings{SpiTen01, author = "D. Spielman and S.-H. Teng", title = "Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time", booktitle = "33rd {ACM} Symposium on Theory of Computing", year = "2001", pages = "296--305", year = "2001", } @article{KaRi99, author = "A. Kapoor and R. Rizzi", title = "Edge-coloring bipartite graphs", journal = "Journal of Algorithms", volume = 34, number = 2, pages = "390--396", year = 2000, } @Article{ColHop82, author = "Richard Cole and John Hopcroft", title = "On edge coloring bipartite graphs", journal = "SIAM Journal on Computing", volume = "11", number = "3", pages = "540--546", year = "1982", coden = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", mrclass = "68E10 (05C15 68C25)", mrnumber = "83h:68101", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{ColOstSch00, author = "R. Cole and K. Ost and S. Schirra", title = "Edge-Coloring Bipartite Multigraphs in {$O(E\log D)$} Time", journal = "Combinatorica", pages = "5--12", volume = 21, number = 1, year = 2000 } @Article{LevPipVal81, author = "G. Lev and N. Pippenger and L. Valiant", title = "A Fast Parallel Algorithm for Routing in Permutation Networks", journal = "IEEE Trans. on Comp.", volume = "C-30, 2", year = "1981", pages = "93--100", references = "0", country = "USA", language = "English", enum = "3944", descriptors = "Interconnection network; parallel computing; routing; algorithm;", date = "09/03/90", by_date = "Uhl", revision = "21/04/91", by_rev = "Le", location = "UniDo-ESV", annote = "An algorithm is given for routing in permutation networks-that is, for computing the switch settings that implement a given permutation. The algorithm takes serial time or parallel time .The se time bounds may be reduced by a further logarithmic factor when all of the switch sizes are integral powers of two. edge coloring for bipartite graphs", } @inproceedings{ goodrich92planar, author = "Goodrich", title = "Planar Separators and Parallel Polygon Triangulation (Preliminary Version)", booktitle = "{STOC}: {ACM} Symposium on Theory of Computing ({STOC})", year = "1992", url = "citeseer.nj.nec.com/goodrich92planar.html" } @Article{Shr98, author = "A. Schrijver", title = "Bipartite Edge Coloring in $O(\Delta m)$ Time", journal = "SIAM J. Computing", year = 1998, volume = 28, number = 3, pages = "841--846", annote = "genauer O(m(log Delta + sum_i p_i/\prod_{j<i}p_j)) wobei p_i die i-t kleinste Primzahl in der Primfaktorzerlegung von Delta ist. Meine Beobachtung: daraus folgt ein O(m log Delta) Zeit Algorithms fuer eine 1+O(1/sqrt{Delta}) Approximations. Runde einfach so auf, dass es durch eine Zweirpotentz nahe sqrt{m} teilbar ist." } @InProceedings{DurJaiTse95, author = "D. Durand and R. Jain and D. Tseytlin", title = "Applying Randomized Edge Coloring Algorithms to Distributed Communication: An Experimental Study", pages = "264--274", booktitle = "7th ACM Symposium on Parallel Algorithms and Architectures", year = 1995, annote = "Ergebnisse sehen gut aus aber die Instanzen scheinen mir nicht sehr schwer zu sein. Ordentlicher Literaturueberblick" } @Article{Sha49, author = "C. E. Shannon", title = "A theorem on colouring lines of a network", journal = "J. Math. Phys.", year = 1949, volume = 28, number = "148--151" } @InProceedings{ValBre81, title = "Universal Schemes for Parallel Communication", author = "L. G. Valiant and G. J. Brebner", pages = "263--277", booktitle = "Conference Proceedings of the Thirteenth Annual {ACM} Symposium on Theory of Computation", month = "11--13 " # may, year = "1981", address = "Milwaukee, Wisconsin", } @Article{KarKleTar95, title = "{A randomized linear-time algorithm for finding minimum spanning trees}", author = "David Karger and Philip N. Klein and Robert E. Tarjan", keywords = "minimum spanning tree", journal = "J. Assoc. Comput. Mach.", publisher = "ACM", volume = "42", pages = "321--329", year = "1995", } @Article{GabKar82, author = "H. N. Gabow and O. Kariv", title = "Algorithms for edge coloring bipartite graphs and multigraphs", journal = "SIAM Journal on Computing", volume = "11", number = "1", pages = "117--129", year = "1982", coden = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", mrclass = "68E10 (05C15)", mrnumber = "83g:68098", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Hol81, author = "I. Holyer", title = "The {NP}-completeness of edge-coloring", journal = "SIAM Journal on Computing", volume = "10", number = "4", pages = "718--720", year = "1981", coden = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", mrclass = "68C25 (05C15 68E10)", mrnumber = "83b:68050", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Book{Moy98, author = "J. T. Moy", title = "{OSPF}: Anatomy of an {Internet} Routing Protocol", publisher = "Ad{\-d}i{\-s}on-Wes{\-l}ey", address = "Reading, MA, USA", pages = "xvii + 339", year = 1998, ISBN = "0-201-63472-4", LCCN = "TK5105.875.I57M69 1998", bibdate = "Wed May 27 07:22:11 1998", price = "US\$44.95", acknowledgement = ack-nhfb, } @InProceedings{WCLF01, author = "Peng-Jun Wan and G. Calinescu and Xiang-Yang Li and Ophir Frieder", title = "Minimum-Energy Broadcast Routing in Static Ad Hoc Wireless Networks", booktitle = "{IEEE Infocom}", year = "2001", } @InProceedings{WNE00, author = "J. E. Wieselthier and G. D. Nguyen and A. Ephremides", title = "On the Construction of Energy-Efficient Broadcast and Multicast Trees in Wireless Networks", booktitle = "{IEEE Infocom}", pages = "585--594", year = 2000, volume = 2, organization = "IEEE" } @Book{Rap96, author = "T. S. Rappaport", title = "Wireless Communication", publisher = "Prentice Hall", year = 1996 } @article{RamSte96, author = "S. Ramanathan and M. Steenstrup", title = "A Survey of Routing Techniques for Mobile Communications Networks", journal = "Mobile Networks and Applications", volume = "1", number = "2", pages = "89-104", year = "1996", url = "citeseer.nj.nec.com/ramanathan96survey.html" } @Unpublished{Pat04, author = "M. Patel", title = "A Probabilistic Self-Adjusting Binary Search Tree", note = " ", year = 2004 } @MastersThesis{Pat00, author = "D. Patel", title = "Energy in Ad-Hoc networking for the PicoRadio", school = "UC Berkeley", year = 2000 } @Article{Hof83, author = "R. D. Hofstadter", title = "Metamagical themas", journal = "Scientific American", year = 1983, number = 2, pages = "16--22" } @InProceedings{LAR02, author = "Q. Li and J. Aslam and D. Rus", title = "Online Power-aware Routing in Wireless Ad-hoc Networks", booktitle = "ACM SIGMOBILE", pages = "97--107", year = 2002, address = "Rome, Italy", annote = "maximize life time of network. mostly negative results" } @Article{RabEtAl00, author = "J. M. Rabaey et al.", title = "PicoRadio Supports Ad Hoc Ultra-Low Power Wireless Networking", journal = "IEEE Computer Magazine", year = 2000, pages = "42--48", month = "July" } @Article{NOZ01, author = "K. Nakano and S. Olariu and A. Y. Zomaya", title = "Energy-Efficient Permutation Routing in Radio Networks", journal = "IEEE Transactions on Parallel and Distributed Systems", year = 2001, volume = 12, number = 6, pages = "544--557", annote = "single hop looking at start up overhead only" } @Unpublished{Shm01, author = "D. Shmoys", title = "Approximation Algorithms and Performance Guarantees", note = "course notes mini course at ADFOCS", year = 2001 } @Article{HocNisShm86, author = "D. S. Hochbaum and T. Nishizeki and D. B. Shmoys", title = "A Better than ``Best Possible'' Algorithm to Edge Color Multigraphs", journal = "Journal of Algorithms", year = 1986, volume = 7, pages = "79--104", annote = "9/8 optimal. Ausfuehrliche Algorithmenbeschreibung" } @Unpublished{Pla04, author = "M. Plantholt", title = "A combined logarithmic bound on the chromatic index of multigraphs", note = "manuscript in preparation. The result was presented at the 34th Southeastern Int. Conf. on Combinatorics, Graph Theory, and Computing, Boca Raton", year = 2003 } @Article{PW84, author = "M. W. Padberg and L. A. Wolsey", title = "Fractional covers for forests and matchings", journal = "Math. Programming", year = 1984, volume = 29, number = 1, pages = "1--14" } M. Plantholt. A sublinear bound on the chromatic index of multigraphs. Discrete Mathematics, 202(1?3):201?213, 1999 @Article{Pla99, author = "M. Plantholt", title = "A sublinear bound on the chromatic index of multigraphs", journal = "Discrete Mathematics", year = 1999, volume = 202, number = "1--3", pages = "201--213" } @Article{, author = "M. W. Padberg and L. A. Laurence", title = "Fractional covers for forests and matchings", journal = "Math. Programming", year = 1984, volume = 29, pages = "1--14" } @InCollection{Sey79, author = "P. D. Seymour", title = "Some Unsolved Problems on One-Factorization of Graphs", booktitle = "Graph Theory and Related Topics", pages = "367--368", publisher = "Academic Press", year = 1979, editor = "J. A. Bondy and U. S. R. Murty" } @Article{Gol73, author = "M. K. Goldberg", title = "On Multigraphs of Almost Maximal Chromatic Class (in Russian)", journal = "Diskret Analiz", year = 1973, volume = 23, pages = "3--7" } @InProceedings{FOW02, author = "U. Feige and E. Ofek and U. Wieder", title = "Approximating Maximum Edge Coloring in Multigraphs", booktitle = "APPROX", pages = "108--121", year = 2002, volume = 2462, series = "LNCS", publisher = "Springer" } @Article{Gol84, author = "M. K. Goldberg", title = "Edge-Coloring of Multigraph: Recoloring Techniques", journal = "Journal of Graph Theory", year = 1984, volume = 8, pages = "122--136" } @Article{CapRiz98, author = "A. Caprara and R. Rizzi", title = "Improving a Family of Approximation Algorithms to Edge Color Multigraphs", journal = "Information Processing Letters", year = 1998, volume = 68, pages = "11--15" } @Article{Kah96, author = "J. Kahn", title = "Asymptotics of the Chromatic Index for Multigraphs", journal = "Journal of Combinatorial Theory B", year = 1996, volume = 68, pages = "233-254" } @Article{NisKas90, author = "T. Nishizeki and K. Kashiwagi", title = "On the $1.1$ Edge-Coloring of Multigraphs", journal = "SIAM Journal on Discrete Mathematics", volume = "3", number = "3", pages = "391--410", month = aug, year = "1990", coden = "SJDMEC", ISSN = "0895-4801 (print), 1095-7146 (electronic)", mrclass = "05C15 (05C85 68Q25 68R10 94C15)", mrnumber = "91f:05055", mrreviewer = "Marek Kubale", bibdate = "Thu Apr 9 15:20:35 MDT 1998", acknowledgement = ack-nhfb, } @Article{NisSat84, author = "T. Nishizeki and M. Sato", title = "An algorithm for edge-coloring multigraphs", journal = "Trans. Inst. Electronics and Communication Eng.", volume = "J67-D", number = 4, year = 1984, pages = "466-471", note = "(in Japanese)" } @Article{Viz64, author = "V. G. Vizing.", title = "On an estimate of the chromatic class of a p-graph (in Russian)", journal = "Diskret. Analiz", volume = "3", year = "1964", pages = "23--30", } @Article{Whi90, author = "J. Whitehead", title = "The Complexity of File Transfer Scheduling with Forwarding", journal = "SIAM Journal on Computing", volume = "19", number = "2", pages = "222--245", month = apr, year = "1990", coden = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", mrclass = "68M10 (68R10)", mrnumber = "92e:68007", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @InCollection{NakZhoNis96, author = "S. Nakano and X. Zhou and T. Nishizeki", title = "Edge-Coloring Algorithms", booktitle = "Computer Science Today", publisher = "Springer", year = 1996, number = 1000, series = "LNCS", pages = "172--183" } @InProceedings{soda90*291, author = "M. Chrobak and H. Karloff and T. Payne and S. Vishwanathan", title = "New Results on Server Problems", pages = "291--300", ISBN = "0-89871-251-3", editor = "David Johnson", booktitle = "Proceedings of the 1st Annual {ACM}-{SIAM} Symposium on Discrete Algorithms ({SODA} '90)", address = "San Francisco, CA, USA", month = jan, year = "1990", publisher = "SIAM", annote = "offline weighted caching" } @InProceedings{BeiChrLar99, author = "W. W. Bein and M. Chrobrak and L. L. Larmore", title = "The 3-Server Problem in the Plane", booktitle = "ESA'99", year = 1999 } @Article{KarPea83, author = "R. M. Karp", title = "Searching for an Optimal Path in a Tree with Random Costs", journal = aint, year = 1983, volume = 21, pages = "99--116", annote = "Eins der wichtigsten Theorie papers. Beispiel fuer Polynomiallen Aufwand." } @Article{Kar94, author = "R. M. Karp", title = "Probabilistic Recurrence Relations", journal = jacm, year = 1994, volume = 41, number = 6, pages = "1136--1150", annote = "behandelt Glchg. der Form T(x) = a(x) + T(h(x)). h ist ZVA und m(x) ist eine obere Schranke fuer den EW von h. z.T. muss die Annahme gemacht werden dass h(x)<=x. Allgemeneiner: T(x) = a(x) +\sum T(h_i(x)). Viele klassische Beispiele. Sogar Info Vorlesung (z.B. quick-sort)? " } @Article{KarZha93, author = "R. M. Karp and Y. Zhang", title = "Parallel Algorithms for Backtrack Search and Branch-and-Bound", journal = jacm, year = 1993, volume = 40, number = 3, pages = "765--789", annote = "randpomisierte Arbeitsverteilung. Ziel ist maximaler Speedup, Effizienz ? vollstaendige Vernetzung wird angenommen. Tiefensuche, Baum wird oben gespalten 123456->123, 456. Terminierungserkennung etwas obskur (wahrscheinlich nicht implementiert). Lastabschaetzung durch Mitzaehlen der Anzahl donations. Deterministischer Alg: woher nehmen die die Info ueber beschaeftigte PEs? es wird nur obskur von global control geregelt und diese dann in der Zeitbeeruchnung unter den Teppich gekehrt! Analyse von Random polling aber: Durchmesser 1, viele Operationen unter den Teppich gekehrt funktioniert nicht fuer bel. Effizienz. Ausserdem W(P) = O(P^2 log P) ist nicht neu und viiiiiiel zu grob. voll randomisiertes local best first. d.h. expandierte Knoten werden an zufaelligen anderen Knoten geschickt. Kein broadcast des incumbent. statt dessen schicken arbeitslose PEs ihren incumbent an zufaellig ausgewaehlte PEs. Interessant: Isoeffizienzfunktion in O(P^(1+\epsilon) mhw!!!!!!. Wichtige Beweistechnik: Was passiert mit den Knoten auf dem Pfad von der Wurzel zu einem bestimmten Knoten. Der Alg. laesst sich als Warteschlangenproblem verstehen allerdings wird in den Warteschlangen wird immer der wichtigste bedient Formulierung einer WT-Argumentation ueber einen Gegenspieler. Kontienuierliche Zeit mit Poisson-verteilten Ankunftszeiten. Chernoff-bound maessige Sachen fuer Poisson Prozesse. Ergodisches Theorem? Analyse des B&B Algorithmus mit aussschliesslicher Nachbarschaftskommunikation wird als offenes Problem angegeben." } @TechReport{KarZha93a, author = "R. M. Karp and Y. Zhang", title = "Finite Branching Processes and {AND/OR} Tree Evaluation", institution = "ICSI, Berkeley", year = 1993, number = "TR-93-043" } @Article{Ath93, author = "K. B. Athreya", title = "Large deviation rates for branching processes --- {I}, single type case", journal = "Annals of Applied Probability", year = 1993 } @InProceedings{ChaEtAl94, author = "S. Chakrabarti and A. Ranade and K. Yelick", title = "Randomized Load Balancing for Tree-structured Computation", pages = "666--673", booktitle = "Scalable High Performance Computing Conference", year = 1994, address = "Knoxville, TN, 23--25 May", publisher = "IEEE, Los Alamitos, CA", annote = "Verallgemeinerung von KarZha93. Interessante irregulaere numerische Anwendung: EW Berechnung tridiagonaler symmetrischer Matrizen. (hat allerdings Flaschenhals bei Initialisierung.)" } @InProceedings{YelEtAl95, author = "K. Yelick and C. Wen and S. Chakrabarti", title = "Portable Parallel Irregular Applications", pages = "157--173", booktitle = "Parallel Symbolic Languages and Systems", year = 1995, annote = "Mehrere Anwendungen. Wieder Eigenwerte, Phylogenie Problem. Potpourri paper" } @InProceedings{CasEtAl94, author = "C. Casari and C. Catelli and M. Guanziroli and M. Mazzeo and G. Meola and S. Punzi and A. Scheinine and P. Stofella", title = "Status Report on {ESPRIT} Project P9519 Palace: Parallelization of {GEANT}", booktitle = "International Conference Massively Parallel Processing Applications and Development", year = 1994, pages = "405--412", publisher = "Elsevier", address = "Delft" } @Article{Nak74, author = "K. Nakamura", title = "Asynchronous cellular automata and their computational ability", journal = "Systems, Computers, Controls", year = 1974, volume = 5, pages = "58--66" } @Book{Qui94, author = "M. J. Quinn", title = "Parallel Computing: {T}heory and Practice", publisher = "McGraw-Hill", year = 1994, annote = "einiges ueber Sortieren a la Quicksort" } @Article{Qui89, author = "M. J. Quinn", title = "Analysis and benchmarking oaf two parallel sorting algorithms: hyperquicksort and quickmerge", journal = "{BIT}", year = 1989, volume = 25, pages = "239--250" } @Article{QuiDeo86, author = "M. J. Quinn and N. Deo", title = "An Upper Bound for the Speedup of Parallel Best-Bound Branch-and-Bound Algorithms", journal = "BIT", year = 1986, volume = 26, pages = "35--43", annote = "cryptisch. OR. Signifikanz? Die Ergebnisse sind so lose das kaum etwas damit anzufangen ist!?" } @TechReport{Ran90, author = "A. Ranade", title = "A Simpler Analysis of the {K}arp-{Z}hang Parallel Branch-and-Bound Method", institution = "University of California Berkeley", year = 1990, annote = "Analyse von Karp/Zhangs Algorithumus verbessert (Isoeffizienzfunktion n log n) und Beweis braucht nur 3 Seiten. Deley Sequence Argument" } @Article{Smi84, author = "D. R. Smith", title = "Random Trees and the Analysis of Branch and Bound Procedures", journal = jacm, year = 1984, volume = 31, number = 1, pages = "163--188", annote = "Modell branching processes, unendl. Baum aber die Knoten minimaler Kosten bestimmen einen endlichen Teilbaum. Sehr mathemat. Def. von discrete optimization problem. Es wird argumentiert, dass eine Klasse von TSP-Problemen. Inkrementelle Berechnung fuer das Assignment Problem. im Mittel mit nlog n expandierten Knoten auskommt. Beispiel fuer gen. Pseudocode. Numerische Loesung von Rekurrenzen. Er sieht dass die Unabhaengigketis annahme nicht wirklich gilt." } @InProceedings{SutJob93, author = "C. B. Suttner and M. R. Jobmann", title = "Simulation of Static Partitioning with Slackness", booktitle = "Proceedings of PPAI-93", year = 1993, annote = "Theorembeweiserspezifisch" } @Unpublished{VolEtAl95, author = "R. Vollmar and H. Fernau and P. Sanders and T. Worsch", title = "Materialien zur Vorlesung Einf{\"u}hrung in die Informatik (f{\"u}r Elektrotechniker)", year = 1995, month = "Sommersemester" } @Book{UmlVol92, author = "T. Umland and R. Vollmar", title = "Transputerpraktikum", publisher = "Teubner", year = 1992 } @Article{Uml94, author = "T. Umland", title = "Parallel sorting revisited", journal = paco, year = 1994, volume = 20, number = 1, pages = "115--124", annote = "merge-splitting sort" } @Book{VolWor95, author = "R. Vollmar and T. Worsch", title = "Modelle der Parallelverarbeitung", publisher = "Teubner", year = 1995 } @Book{Vol79, author = "R. Vollmar", title = "Algorithmen in Zellularautomaten", publisher = "Teubner", year = 1979 } @Book{Chopard:1997:CAM, author = "B. Chopard and M. Droz", title = "Cellular Automata Modeling of Physical Systems", publisher = "Cambridge University Press", year = "1997", note = "Erscheint im Herbst 97", } @Book{BerConGuy82, author = "E. R. Berlekamp and J. H. Conway and R. K. Guy", title = "Winning ways for your mathematical plays", publisher = "Academic Press", year = 1982, volume = 2, address = "New York" } @MastersThesis{Gme94, author = "R. Gmehlich", title = "Einbettungen von Graphen mit logarithmischem Durchmesser in Gitter", school = "Universit{\"a}t Karlsruhe", year = 1994, type = "Diplomarbeit" } @TechReport{Wor94, author = "T. Worsch", title = "Lower and upper bounds for (sums of) binomial coefficients", institution = "Universit{\"a}t Karlsruhe", year = 1994, number = "IB 31/94" } @Article{YanDas94, author = "M. K. Yang and C. R. Das", ti