BibTeX Entries for Publications of Bruce Maggs

@inproceedings{AielloLMN90,
author = "W. Aiello and T. Leighton and B. Maggs and M. Newman",
title = "Fast Algorithms for Bit-Serial Routing on a Hypercube",
booktitle =  "Proceedings of the 2nd Annual {ACM} Symposium on
   Parallel Algorithms and Architectures",
month = jul,
year = 1990,
pages = "55--64"}

@article{AielloLMN91,
author = "W. A. Aiello and F. T. Leighton and B. M. Maggs and M. Newman",
title = "Fast Algorithms for Bit-Serial Routing on a Hypercube",
journal = "Mathematical Systems Theory",
volume = 24,
number = 4,
year = 1991,
pages = "253--271"}

@inproceedings{AielloAMR93,
author = "W. Aiello and B. Awerbuch and B. Maggs and S. Rao",
title = "Approximate Load Balancing on Dynamic and Asynchronous
   Networks",
booktitle = "Proceedings of the 25th Annual {ACM} Symposium on
   the Theory of Computing",
month = may,
year = 1993,
pages = "632--641"}

@inproceedings{AroraLM90,
author = "S. Arora and T. Leighton and B. Maggs",
title = "On-line Algorithms for Path Selection in a Non-blocking Network",
booktitle =  "Proceedings of the 22nd Annual {ACM} Symposium on
   Theory of Computing",
month = may,
year = 1990,
pages = "149--158"}

@article{AroraLM96,
author = "S. Arora and F. T. Leighton and B. M. Maggs",
title = "On-line Algorithms for Path Selection in a Non-blocking Network",
journal = "{SIAM} Journal on Computing",
volume = 25,
number = 3,
year = 1996,
month = jun,
pages = "600--625"}

@techreport{BerthomeFMPP92,
author = "P. Berthom\'e and A. Ferreira and B. M. Maggs and S.
Perennes and C. G. Plaxton",
title = "Sorting-Based Selection Algorithms for Hypercubic Networks",
type = "Rapport",
number = "{n$^{\circ}$} 92-36",
institution = "Laboratoire de l'Informatique du Parall\'{e}lisme,
		  Ecole Normale Sup\'{e}rieure de Lyon",
address = "Lyon, France",
month = jul,
year = 1992}

@inproceedings{BerthomeFMPP93,
author = "P. Berthom\'e and A. Ferreira and B. M. Maggs and S.
Perennes and C. G. Plaxton",
title = "Sorting-Based Selection Algorithms for Hypercubic Networks",
booktitle = "Proceedings of the 7th International Parallel Processing
   Symposium",
month = apr,
year =1993,
pages = "89--95"}

@article{BerthomeFMPP97,
 author = "P. Berthom\'e and A. Ferreira and B. M. Maggs and S.
 Perennes and C. G. Plaxton",
 title = "Sorting-Based Selection Algorithms for Hypercubic Networks",
 journal = "Algorithmica",
 note = "To appear"}

@inproceedings{BlellochLMPSZ91,
author = "G. E. Blelloch and C. E. Leiserson and B. M. Maggs and
C. G. Plaxton and S. Smith and M. Zagha",
title = "A Comparison of Sorting Algorithms for the Connection Machine
   {CM-2}",
booktitle = "Proceedings of the 3rd Annual {ACM} Symposium on
   Parallel Algorithms and Architectures",
year = 1991,
month = jul,
pages = "3--16"}

@article{BlellochLMPSZ97,
author = " G. E. Blelloch and C. E. Leiserson and B. M. Maggs and
   C. G. Plaxton and S. Smith and M. Zagha",
title = "An Experimental Analysis of Parallel Sorting Algorithms",
journal = "Theory of Computing Systems",
note = "To appear"}

@article{BlellochM96,
author = "G. E. Blelloch and B. M. Maggs",
title = "Parallel Algorithms",
journal = "{ACM} Computing Surveys",
volume = 28,
number = 1,
month = mar,
year = 1996,
pages = "51--54"}


@incollection{BlellochM97,
author = "G. E. Blelloch and B. M. Maggs",
title = "Parallel Algorithms",
booktitle = "The Handbook of Computer Science and Engineering",
editor = "A. B. {Tucker, Jr.}",
publisher =  "{CRC} Press",
address = "Boca Raton, FL",
year = 1997,
pages = "277--315"}

@incollection{BlellochMM94,
title = "The Hidden Cost of Low Bandwidth Communication",
author = "G. E. Blelloch and B. M. Maggs and G. L. Miller",
editor = "U. Vishkin",
booktitle = "Developing a Computer Science Agenda for High-Performance
  Computing",
publisher = "{ACM} Press",
year = 1994,
pages = "22--25"}

@techreport{BornsteinLMSY97,
 author = "C. F. Bornstein and A. Litman and B. M. Maggs and R. K. Sitaraman
and T. Yatzkar",
 title = "On the Bisection Width and Expansion of
Butterfly Networks",
 type = "Technical Report",
 number = "CMU--CS--97--132",
 institution = "School of Computer Science, Carnegie Mellon University",
 address = "Pittsburgh, PA",
 month = may,
 year = 1997,
}

@techreport{BornsteinMMR97,
 author = "C. Bornstein and B. Maggs and G. Miller and R. Ravi",
 title = "Parallel {Gaussian} Elimination with Linear
Work and Fill",
 type = "Technical Report",
 number = "CMU--CS--97--133",
 institution = "School of Computer Science, Carnegie Mellon University",
 address = "Pittsburgh, PA",
 month = may,
 year = 1997,
}

@inproceedings{ColeMS93,
author = "R. Cole and B. Maggs and R. Sitaraman",
title = "Multi-Scale Self-Simulation:  A Technique for Reconfiguring
   Arrays with Faults",
booktitle = "Proceedings of the 25th Annual {ACM} Symposium on
   the Theory of Computing",
month = may,
year = 1993,
pages = "561--572"}

@inproceedings{ColeMS95,
author = "R. Cole and B. Maggs and R. Sitaraman",
title = "Routing on Butterfly Networks with Random Faults",
booktitle =  "Proceedings of the 36th Annual Symposium on
   Foundations of Computer Science",
year = 1995,
month = oct,
pages = "558--570"}

@inproceedings{ColeMS96,
author = "R. J. Cole and B. M. Maggs and R. K. Sitaraman",
title = "On the Benefit of Supporting Virtual Channels in Wormhole  Routers",
booktitle = "Proceedings of the 8th {ACM} Symposium on
   Parallel Algorithms and Architectures",
mon = jun,
year = 1996,
pages = "131--141"}

@article{ColeMS97,
author = "R. J. Cole and B. M. Maggs and R. K. Sitaraman",
title = "Reconfiguring Arrays with Faults Part {I}: Worst-Case Faults",
journal = "{SIAM} Journal on Computing",
volume = 26,
number = 6,
month = dec,
year = 1997,
note = "To appear"}

@inproceedings{CoxHMR92,
author = "I. J. Cox and S. Hingorani and B. M. Maggs and S. B. Rao",
title = "Stereo Without Disparity Gradient Smoothing: A {Bayesian} Sensor
   Fusion Solution",
booktitle = "Proceedings of the 1992 British Machine Vision Conference",
month = sep,
year = 1992,
pages = "337-346"}

@article{CoxHMR96,
author = "I. J. Cox and S. L. Hingorani and B. M. Maggs and S. B. Rao",
title = "A Maximum Likelihood Stereo Algorithm",
journal = "Computer Vision and Image Understanding",
volume = 63,
number = 3,
month = may,
year = 1996,
pages = "542--567"}

@techreport{FeldmannMSST95,
author = "A. Feldmann and B. M. Maggs and J. Sgall and D. D. Sleator
   and A. Tomkins",
title = "Competitive analysis of call admission algorithms that allow
   delay",
type = "Technical Report",
number = "CMU--CS--95--102",
institution = "School of Computer Science, Carnegie Mellon University",
address = "Pittsburgh, PA",
month = jan,
year = 1995}

@inproceedings{GhoshLMMPRRTZ95,
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
   R. E. Tarjan and D. Zuckerman",
title = "Tight Analyses of Two Local Load Balancing Algorithms",
booktitle = "Proceedings of the 27th Annual {ACM} Symposium on
   the Theory of Computing",
month = may,
year = 1995,
pages = "548--558"}

@article{GhoshLMMPRRTZ97,
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
   R. E. Tarjan and D. Zuckerman",
title = "Tight Analyses of Two Local Load Balancing Algorithms",
journal = "{SIAM} Journal on Computing",
note = "To appear"}

@article{GoldbergMP94,
author = "A. V. Goldberg and B. M. Maggs and S. A. Plotkin",
title = "A Parallel Algorithm for Reconfiguring a Multibutterfly
   Network with Faulty Switches",
journal = "{IEEE} Transactions on Computers",
volume = 43,
number = 3,
month = mar,
year = 1994,
pages = "321--326"}

@inproceedings{KochLMRR89,
author = "R. Koch and T. Leighton and B. Maggs and
   S. Rao and A. Rosenberg",
title = "Work-Preserving Emulations of Fixed-Connection
   Networks",
booktitle = "Proceedings of the 21st Annual {ACM} Symposium on
   Theory of Computing",
month = may,
year = 1989,
pages = "227--240"}

@article{KochLMRRS97,
author = "R. R. Koch and F. T. Leighton and B. M. Maggs and
   S. B. Rao and A. L. Rosenberg and E. J. Schwabe",
title = "Work-Preserving Emulations of Fixed-Connection Networks",
journal = "Journal of the {ACM}",
volume = 44,
number = 1,
month = jan,
year = 1997,
pages = "104--147"}

@inproceedings{LeightonLM90,
author = "T. Leighton and D. Lisinski and B. Maggs",
title = "Empirical Evaluation of Randomly-Wired Multistage Networks",
booktitle =  "Proceedings of the 1990 {IEEE} International Conference on
   Computer Design: VLSI in Computers \& Processors",
month = sep,
year = 1990,
pages = "380--385"}

@inproceedings{LeightonM89,
author =  "T. Leighton and B. Maggs",
title = "Expanders Might be Practical:  Fast Algorithms
   for Routing Around Faults in Multibutterflies",
booktitle =  "Proceedings of the 30th Annual Symposium on
   Foundations of Computer Science",
month = oct,
year = 1989,
pages = "384--389"}

@article{LeightonM92,
author =  "F. T. Leighton and B. M. Maggs",
title = "Fast Algorithms for Routing Around Faults in Multibutterflies
   and Randomly-Wired Splitter Networks",
journal = "{IEEE} Transactions on Computers",
volume = 41,
number = 5,
month = may,
year = 1992,
pages = "578--587"}

@inproceedings{LeightonMR88,
author = "T. Leighton and B. Maggs and S. Rao",
title = "Universal Packet Routing Algorithms",
booktitle = "Proceedings of the 29th Annual Symposium on
   Foundations of Computer Science",
month = oct,
year = 1988,
pages = "256--271"}

@article{LeightonMR94,
author = "F. T. Leighton and B. M. Maggs and S. B. Rao",
title = "Packet Routing and Job-Shop Scheduling
   in {$O$}(Congestion + Dilation) Steps",
journal = "Combinatorica",
volume = 14,
number = 2,
year = 1994,
pages = "167--180"}

@inproceedings{LeightonM95,
author = "T. Leighton and B. Maggs",
title = "Fast Algorithms for Finding {$O$}(Congestion + Dilation)
   Packet Routing Schedules",
booktitle = "Proceedings of the 28th Hawaii International Conference
   on System Sciences",
month = jan,
year = 1995,
volume = 2,
pages = "555--563"}

@techreport{LeightonMR96,
author = "F T. Leighton and B. M. Maggs and A. W. Richa",
title = "Fast Algorithms for Finding {$O$}(Congestion + Dilation)
   Packet Routing Schedules",
type = "Technical Report",
number = "CMU--CS--96--152",
institution = "School of Computer Science, Carnegie Mellon University",
address = "Pittsburgh, PA",
month = jul,
year = 1996,
}

@article{LeightonMR98,
 author = "F. T. Leighton and B. M. Maggs and A. W. Richa",
 title = "Fast Algorithms for Finding {$O$}(Congestion + Dilation)
 Packet Routing Schedules",
 journal = "Combinatorica",
 note = "To appear"}

@article{LeightonMRR94,
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",
volume = 17,
number = 1,
month = jul,
year = 1994,
pages = "157--205"}

@inproceedings{LeightonMS92a,
author = "T. Leighton and B. Maggs and R. Sitaraman",
title = "On the Fault Tolerance of Some Popular Bounded-Degree
   Networks",
booktitle = "Proceedings of the 33rd Annual Symposium on
   Foundations of Computer Science",
month = oct,
year = 1992,
pages = "542--552"}

@techreport{LeightonMS92b,
author = "T. Leighton and B. Maggs and R. Sitaraman",
title = "On the Fault Tolerance of Some Popular Bounded-Degree
  Networks",
type = "Technical Report",
number = "CS--TR--385--92",
institution = "Department of Computer Science, Princeton University",
address = "Princeton, NJ",
month = sep,
year = 1992}

@article{LeightonMS98,
author = "F. T. Leighton and B. M. Maggs and R. K. Sitaraman",
title = "On the fault tolerance of some popular bounded-degree
   networks",
journal = "{SIAM} Journal on Computing",
note = "To appear"}

@inproceedings{LeisersonM86a,
author = "C. E. Leiserson and B. M. Maggs",
title = "Communication-Efficient Parallel Graph Algorithms",
booktitle = "Proceedings of the 1986 International Conference on
   Parallel Processing",
month = aug,
year = 1986,
pages = "861--868"}

@techreport{LeisersonM86b,
author = "C. E. Leiserson and B. M. Maggs",
title = "Communication-Efficient Parallel Graph Algorithms",
type = "Technical Memo",
number = "MIT/LCS/TM-318",
institution = "MIT Laboratory for Computer Science",
address = "Cambridge, MA",
month = dec,
year = "1986"}

@article{LeisersonM88,
author = "C. E. Leiserson and B. M. Maggs",
title ="Communication-Efficient Parallel Graph Algorithms for Distributed
   Random-Access Machines",
journal = "Algorithmica",
volume = 3,
number = 1,
pages = "53--77",
year = 1988}

@bachelorsthesis{Maggs85,
author = "B. M. Maggs",
title = "{\it Computing Minimum Spanning Trees on a Fat-Tree Architecture.}
   {Bachelor's thesis, Department of Electrical
   Engineering and Computer Science, Massachusetts Institute of
   Technology, Cambridge, MA}",
month = may,
year = 1985}

@mastersthesis{Maggs86,
author = "B. M. Maggs",
title = "{\it Communication-Efficient Parallel Graph Algorithms}",
school = "Department of Electrical Engineering and Computer Science,
   Massachusetts Institute of Technology",
address = "Cambridge, MA",
month = may,
year = 1986}

@phdthesis{Maggs89a,
author = "B. M. Maggs",
title = "Locality in Parallel Computation",
school = "Department of Electrical Engineering and Computer Science,
   Massachusetts Institute of Technology",
address = "Cambridge, MA",
month = sep,
year = 1989}

@incollection{Maggs89b,
author = "B. Maggs",
title = "Beyond Parallel Random-Access Machines",
booktitle = "Opportunities and Constraints of Parallel Computing", 
editor = "J. L. C. Sanz",
publisher = "Springer-Verlag",
year = 1989,
pages = "83--84"}

@techreport{Maggs89c,
 author = "B. M. Maggs",
 title = "Locality in Parallel Computation",
 type = "Technical Report",
 number = "MIT/LCS/TR-469",
 institution = "MIT Laboratory for Computer Science",
 address = "Cambridge, MA",
 month = sep,
 year = 1989}

@article{Maggs93,
author = "B. M. Maggs",
title = "Randomly Wired Multistage Networks",
journal = "Statistical Science",
volume = 8,
number = 1,
month = feb,
year = 1993,
pages = "70--75"}

@inproceedings{Maggs96,
author = "B. M. Maggs",
title = "A Critical Look at Three of Parallel Computing's Maxims",
booktitle = "Proceedings of the 1996 International Symposium on Parallel
   Architectures, Algorithms, and Networks",
month = jun,
year = 1996,
pages = "1--7"}

@inproceedings{MaggsMT95,
author = "B. M. Maggs and L. R. Matheson and R. E. Tarjan",
title = "Models of Parallel Computation: A Survey and Synthesis",
booktitle = "Proceedings of the 28th Hawaii International Conference
   on System Sciences",
vol = 2,
month = jan,
year = 1995,
pages = "61--70"}

@article{MaggsP88,
author = "B. M. Maggs and S. A. Plotkin",
title = "Minimum-Cost Spanning Tree as a Path-Finding Problem",
journal = "Information Processing Letters",
volume = 26,
number = 6,
month = jan,
year = 1988,
pages = "291--293"}

@techreport{MaggsP92,
author = "B. M. Maggs and C. G. Plaxton",
title = "Sorting-Based Selection Algorithms for Hypercubic Networks",
type = "Technical Report",
number = "TR--92--22",
institution = "Department of Computer Science, University of Texas",
address = "Austin, TX",
month = apr,
year = 1992}

@inproceedings{MaggsR93,
author = "B. Maggs and M. Rauch",
title = "An Algorithm for Finding Predecessors in Integer Sets",
booktitle = "Proceedings of the 3rd Workshop on Algorithms and
   Data Structures",
volume = "709 of Lecture Notes in Computer Science",
publisher = "Spring-Verlag",
month = aug,
year = 1993,
pages = "483--493"}

@inproceedings{MaggsS92,
author = "B. M. Maggs and R. K. Sitaraman",
title = "Simple Algorithms for Routing on Butterfly Networks with
   Bounded Queues",
booktitle = "Proceedings of the 24th Annual {ACM} Symposium on
   Theory of Computing",
month = may,
year = 1992,
pages = "150--161"}

@article{MaggsS98,
author = "B. M. Maggs and R. K. Sitaraman",
title = "Simple Algorithms for Routing on Butterfly Networks with
   Bounded Queues",
journal = "{SIAM} Journal on Computing",
note = "To appear"}

@unpublished{MaggsS99,
author = "B. M. Maggs and E. J. Schwabe",
title = "Real-time emulations of bounded-degree networks",
month = aug,
year = 1997,
note = "Unpublished manuscript"}

@techreport{MaggsV96,
author = "B. M. Maggs and B. {V\"{o}cking}",
title = "Improved Routing and Sorting on Multibutterflies",
type = "Technical Report",
number = "CMU--CS--96--192",
institution = "School of Computer Science, Carnegie Mellon University",
address = "Pittsburgh, PA",
month = nov,
year = 1996}

@inproceedings{MaggsV97,
author = "B. M. Maggs and B. {V\"{o}cking}",
title = "Improved Routing and Sorting on Multibutterflies",
booktitle = "Proceedings of the 29th Annual {ACM} Symposium on
 the Theory of Computing",
month = may,
year = 1997,
pages = "517--530"}
}

@unpublished{MaggsMVW97,
author = "B. M. Maggs and F. Meyer auf der
Heide and B. {V\"{o}cking} and M. Westermann",
title = "Exploiting Locality for Data Management
in Systems of Limited Bandwidth",
month = apr,
year = 1997,
note = "Unpublished manuscript"}