Errol's History (vita) Return to Errol's Homepage

Errol L. Lloyd

Curriculum Vita
June 2013

Research Specialty

Education

        BS       Computer Science, Penn State University, 1975
        BS       Mathematics, Penn State University, 1975
        SM       Electrical Engineering and Computer Science
                   Massachusetts Institute of Technology, 1977
        PhD      Computer Science
                    Massachusetts Institute of Technology, 1980
                    Thesis Advisor: Ronald L. Rivest
                    Thesis: Scheduling Task Systems with Resources

Professional Experience

        9/10 -        Chair, Computer and Information Sciences, University of Delaware 
        9/94 -          Professor, Computer and Information Sciences, 
                             University of Delaware
        8/03-7/04       Visiting Professor (sabbatical), Computer Science and Engineering, 
                             Arizona State University 
        9/94-8/99       Chair, Computer and Information Sciences, 
                             University of Delaware
        8/97-10/98      Interim Director, Center for Applied Science and Engineering in
                              Rehabilitation, University of Delaware
        9/89-8/94       Associate Professor of Computer and Information 
                               Sciences,  University of Delaware
        8/88-8/89       Program Director, Computer and Computation Theory 
                               Program, National Science Foundation
        9/86-8/89       Associate Professor of Computer Science, University of 
                               Pittsburgh (on leave 8/88 to 8/89)
        9/80-8/86       Assistant Professor of Computer Science, University of 
                               Pittsburgh
        9/75-5/80       Research Assistant, Department of Electrical Engineering
                               and Computer Science, M.I.T. (one semester per year)
        9/75-5/80       Teaching Assistant, Department of Electrical Engineering
                               and Computer Science, M.I.T. (one semester per year)
        6/78-9/78       Senior Programmer, Weather Services Corporation
        6/77-9/77       Systems Programmer, Data Resources, Inc.
        6/75-8/75       Assistant Engineering Programmer, Burroughs Corp
        6/74-9/74       Junior Programmer, Burroughs Corporation

Professional Affiliations

        Member of the Association for Computing Machinery (ACM)
        Member of ACM Special Interest Groups SIGACT and SIGMOBILE

Professional Honors

        University of Delaware Faculty Excellence in Teaching Award - 1994
        NSF Outstanding Performance Award - 1989
        Distinguished Visitor - Department of Computer Science, University of Tennessee - 1987
        Nominated (by the department) for a Chancellor's Distinguished 
                Teaching Award University of Pittsburgh - 1987 and 1988

Professional Activities

        Lecturer for IBM Short Course on Programming Languages, Toronto, Canada - 1988
        Member - NSF - Visiting Team to DIMACS (S&T Center) - 1990
        Panelist - NSF - Research Initiation Awards 
        Panelist - NSF - Visiting Professorships for Women 
        Member of the Industrial and Professional Advisory Committee for the Department of Computer  
                Science and Engineering, Penn State University - 1995-2001
        Workshop Chair - ACM Computer Science Conference - 1996
        Lecturer for UDel Engineering Outreach Program, Short Course on 
                C++ and Object Oriented Programming - 1996
        General Chair - DIAL M for Mobility Workshop - 2000
        Area Editor - "Mobile Algorithms and Complexity" of  SIGMOBILE's
            Mobile Computing and Communications Review (MC2R) - 2002-2005.
        Chair of External Review Team for Computer Science at the College of William and Mary - 2009
        Steering Committee Member - DIAL M for Mobility Workshop - 2001-present
        Area Editor - Ad Hoc Networks (journal) - 2007-present
        External Program Review Team for Graduate Programs in Computer Science at the University of New Hampshire, 2013.
        Program Committees - recent only 

          IEEE Infocom 2010, 2011, 2012, 2013
          ICC Ad-hoc, Sensor and Mesh Networking Symposium, 2010, 2011, 2012
          SENSORNETS - International Conference on Sensor Networks, 2012
          ICACCI -- International Conference on Advances in Computing, Communications and Informatics, 2011
          IEEE Wireless Communications and Networking Conference, 2011, 2012
          IEEE Globecom Symposium on Wireless Ad hoc and Sensor Networks, 2010, 2011, 2012 
          IEEE Globecom Wireless Network Symposium, 2010
          International Wireless Communications and Mobile Computing Conference, 2011, 2012

External Funding

        National Science Foundation, $32,259
        Complexity and Optimization, 9/81 - 3/84

        National Science Foundation, $47,672
        Heuristics for NP-Hard Optimization Problems, 10/83 - 4/86

        National Science Foundation, $89,112
        Incremental Approximations,  9/92 - 9/95

        REU Supplement from NSF for $5000, 5/93-4/94

        US Army - Federated Research Laboratory Program: ATIRP
        Joint with:  9 other CIS and EE faculty
                     Lockheed-Martin, Bellcore, GTE, Motorola 
                     U. of Maryland, Howard U., CUNY, and MIT
        Award portion to UDEL CIS: $1.5 million 1/96-1/01
        My project:  Scheduling and Routing in Packet Radio Networks
                     Award portion: $250,000 1/96-4/01

        National Science Foundation CISE Research Infrastructure
                     Grant:  co-PI with 4 co-PIs, and 13 participating
                     CIS and ECE faculty:  $633,513, 7/97-6/02.
        US Army Research Laboratories, $3.5 million (UD CIS portion)
        Collaborative Technology Alliance Program: CTA: 01-10
                Co-PI (with 4 others) for UD portion. 
        U.S. Army Research Office Scientific Services Program 
         administered by Battelle Memorial Institute, Contract No. W911NF-11-D-0001, 
         Analysis of Connected Dominating Set Algorithms, $40,000, 6/12-3/13.
        National Science Foundation, $416,102
         Ken Barner, PI and 4 co-PIs, including me, Award DUE-1241711
         Collaborative Project:   A Regional Cybersecurity Education Initiative.

PhD Students

        S.S. Ravi - 1984 - Heuristics for PLA Folding: An Analytical Approach 
                (Distinguished Teaching Professor, SUNY Albany) 

        J.R.S. Blair - 1986 - The Effects of Wire Topology on Channel Routing 
                (Professor, US Military Academy - West Point)

        V. Winters - 1987 - Effective Generation of Effective Minimal Perfect Hash Functions 

        S. Ramanathan - 1992 - Communication Scheduling in Packet Radio Networks
                (Principal Scientist, BBN) 

        Z. Ivkovich - 1995 - Incremental approximations 
                (Associate Professor of Finance, Michigan State University ) 

        H. Tadepalli - 1996 - Scheduling DAGs with Communication Constraints
                (Principal System Architect,  Broadcom) 

        X. Ma - 2000 - Adaptive Broadcast Scheduling in Multi-hop Packet Radio Networks 
                (Staff Scientist, Lucent Technologies)
        R. Liu - 2004 - Topology Control for Ad hoc Networks
                (Sr. Research Statistician Developer, SAS)
        Q. Huang - 2004 - Multimedia Gateway Call Routing and Scheduling 
                (Senior Developer,  Bloomberg LP) 
        L. Zhao - 2007 - Topology Control for Mobile Ad-hoc Networks  
               (Data Analyst, WorldQuant )
        F. Che - 2011  - Topology Control and Relay Node Placement
               (Google)


Publications

  1. "On triangulations of a set of points in the plane," Proceedings of the Eighteenth Annual IEEE Symposium on the Foundations of Computer Science (FOCS), 1977, 228-240.
  2. "List scheduling bounds for UET systems with resources," Information Processing Letters, 10 (1980), 28-31.
  3. "Concurrent task systems," Operations Research, 29 (1981), 189-201.
  4. "Coffman-Graham scheduling of UET task systems with 0-1 resources," Information Processing Letters, 12 (1981), 40-45.
  5. "Critical path scheduling with resource and processor constraints," Journal of the ACM, 29 (1982), 781-811 (earlier version: STOC 1980).
  6. "An O(n log m) algorithm for the Josephus Problem," Journal of Algorithms, 4 (1983), 262-270.
  7. "On a simple deadlock recovery problem," Information Processing Letters, 16 (1983), 175-178.
  8. "One layer routing without component constraints," Journal of Computer and System Sciences, 28 (1984), 420-438 (with S.S. Ravi).
  9. "Feedback vertex sets and cyclically reducible graphs," Journal of the ACM, 32 (1985), 296-313 (with M.L. Soffa and C.-C. Wang).
  10. "On the worst case performance of buddy systems," Acta Informatica, 22 (1985), 451-473 (with M.C. Loui).
  11. "Two processor scheduling with limited preemption," Performance Evaluation, 6 (1986), 307-312.
  12. "Minimizing channel density in standard cell layout," Algorithmica, 2 (1987), 267-282 (with J.R.S. Blair, S. Kapoor, K. Supowit).
  13. "Scheduling with semaphore constraints," Operations Research Letters, 6 (1987), 121-124.
  14. "On locating minimum feedback vertex sets," Journal of Computer and System Sciences, 37 (1988), 292-311 (with M.L. Soffa and C.-C. Wang).
  15. "The complexity of near-optimal PLA folding," SIAM Journal on Computing, 17 (1988), 696-710 (with S.S. Ravi).
  16. "A fast algorithm for finding interlocking sets," Information Processing Letters, 32 (1989), 47-50.
  17. "Concurrent Readers and Writers", Proceedings 5th International Workshop on Distributed Algorithms (WDAG) (1991), LNCS 579, Editors: S. Toueg, P. Spirakis, and L. Kirousis (with P. Jayanti and A. Sethi), 212-228.
  18. "A fine grained approach to scheduling asynchronous multimprocessors," in Proc. 4th International Conference on Computing and Information, Toronto, May 1992, 139-142 (with B. Malloy and M. L. Soffa).
  19. "Minimizing external wires in generalized single-row routing," IEEE Transactions on Computers, 41(1992) 771-775 (with J.R.S. Blair).
  20. " On the Complexity of Distance-2 Coloring with Applications to Radio Networks," in Proc. 4th International Conference on Computing and Information, Toronto, May 1992, 71-74 (with S. Ramanathan)
  21. "On the Complexity of Link Scheduling in Multi-hop Radio Networks," in Proc. 26th Conference on Information Sciences and Systems, Princeton University, Mar. 1992, 491-495 (with S. Ramanathan). PDF
  22. "The impact of wire topology on single-row routing," Journal of Circuits, Systems and Computers, 2(1992), 101-112 (with J.R.S. Blair).
  23. "Graph theoretic analysis of PLA folding heuristics," Journal of Computer and Systems Sciences, 46(1993), 326-348 (with S.S. Ravi) .
  24. "Scheduling algorithms for multihop radio networks," IEEE/ACM Transactions on Networking, 1(1993), 166-177 (with S. Ramanathan). Earlier version: Proceedings ACM SIGCOMM conference (1992) (with S. Ramanathan), 211-222. PDF
  25. "Fully dynamic maintenance of vertex cover," Proceedings of 19th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'93), J. van Leeuwen, editor, Lecture Notes in Computer Science No. 790, Springer--Verlag , 99-111, with Z. Ivkovich).
  26. PDF
  27. "Efficient Distributed Algorithms for Channel Assignment in Multihop Radio Networks", Journal of High Speed Networks, 2(1993), 405-423 (with R. Ramanathan).
  28. "Scheduling DAGs for asynchronous multiprocessor execution," IEEE Transactions on Parallel and Distributed Computing, 5(1994), 498-508 (with B. Malloy and M.L.Soffa).
  29. "On k-coloring a set of intervals", Discrete Applied Mathematics 59(1995), 225-235 (with M. Carlisle).
  30. PDF
  31. "River routing with a generalized model," Journal of Computer and System Sciences, 53(1996) 525-544 (with J.R.S. Blair).
  32. "Scheduling task trees on linear arrays of processors", International Parallel Processing Syposium (IPPS), 1996, 584-590 (with H. Tadepalli).
  33. "A fundamental restriction on fully dynamic maintenance of bin packing," Information Processing Letters, 59(1996), 229-232 (with Z. Ivkovich).
  34. PDF
  35. "Partially dynamic bin packing can be solved within 1+e in (amortized) polylogarithmic time", Information Processing Letters 63(1997) (with Z. Ivkovich), 45-50.
  36. PDF
  37. "Experimental results on broadcast scheduling in packet radio networks," Proceedings of the 1st ATIRP Annual Conference, 1997 (with X. Ma).
  38. "Fully dynamic algorithms for bin packing: Being mostly myopic helps," SIAM Journal on Computing, 28(1998), 574-611 (with Z. Ivkovich). Earlier version: Proceedings of the 1st European Symposium on Algorithms (ESA), (T. Lengauer, ed.) Lecture Notes in Computer Science No. 726, Springer--Verlag (1993), 226-237, (with Z. Ivkovich). PDF
  39. "An incremental algorithm for broadcast scheduling in packet radio networks," Proceedings of MILCOM 98 (1998) (with X. Ma), 5 pages on CD-ROM. A preliminary version appeared in: "Practical adaptive algorithms for channel assignment in multihop packet radio networks," Proceedings of 2nd Advanced Telecommunications Information Distribution Research Program Conference (ATIRP) (1998) (with X. Ma)), 60-64.
  40. PDF
  41. "A distributed protocol for adaptive broadcast scheduling in packet radio networks," Workshop record of the 2nd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIAL M for Mobility), 1998 (with X. Ma), 10 pages. A related version appeared in: "Distributed broadcast scheduling," Proceedings of 3rd Advanced Telecommunications Information Distribution Research Program Conference (ATIRP) (1999), (with X. Ma). PDF
  42. "Throughput/Delay of Broadcast Scheduling in Multihop Packet Radio Networks ," Proceedings of the 4th Advanced Telecommunications Information Distribution Research Program Conference (ATIRP) (2000), 239-244, (with X. Ma).
  43. "Experimental Evaluation of a Distributed Broadcast Scheduling Protocol for Multihop Radio Networks ," 5th Advanced Telecommunications Information Distribution Research Program Conference (ATIRP) (2001),  (with X. Ma).
  44. "Evaluation of a Distributed Broadcast Scheduling Protocol for Multihop Radio Networks," Proceedings of MILCOM 2001 (with X. Ma).
  45. PDF
  46. "A Distributed Protocol For Adaptive Link Scheduling in Ad-hoc Networks," Proceedings of the IASTED International Conference on Wireless and Optical Communications (WOC2001) (2001), 43-48, (with R. Liu).
  47. PDF
  48. "Algorithmic aspects of topology control problems for ad hoc networks," Proceedings of the Third ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc) (2002), 123--134 (with M. Marathe, R. Ramanathan, S.S. Ravi, and R. Liu).
  49. PDF
  50. "Analysis of Queuing Delay in Multimedia Gateway Call Routing," Proceedings of the Third International Conference on Internet Computing (IC2002) (2002),193-198 (with Q. Huang). PDF
  51. "Broadcast scheduling for TDMA in Wireless Multi-Hop Networks," Handbook of Wireless Networks and Mobile Computing, Ivan Stojmenovic, Editor, John Wiley and Sons, Inc. (2002), 347-370
  52. "Performance analysis of cost optimization algorithms in multimedia gateway call routing," International Conference on Design, Analysis, and Simulation of Distributed Systems (DASD) ( 2003), 147-154 (with Q. Huang). DOC
  53. "Algorithmic aspects of topology control," Proceedings of CTA Conference on Communications and Networks (2003), 17-22 (with R. Liu, S.S. Ravi, M. Marathe, R. Ramanathan).
  54. "Topology control with diameter constaint," Proceedings of CTA Conference on Communications and Networks (2003), 313-318 (with R. Liu).
  55. "A parameterized cost model to order classes for integration testing of C++ applications," Proceedings of International Symposium on Software Reliability Engineering (ISSRE'03), (2003), 353-364. (with B. Malloy and P. Clarke). PDF
  56. "Algorithmic aspects of topology control problems for ad-hoc networks," ACM Journal on Mobile Networks and Applications (MONET), 10(1-2) 2005, 19-34 (with R. Liu, S.S. Ravi, M. Marathe, R. Ramanathan). PDF
  57. "Topology control problems under symmetric and asymmetric power thresholds," Proc. International Conference on Ad hoc and Wireless Networks (ADHOC-NOW'03), (LNCS 2865), 187-198. (with S. Krumke, R. Liu, M. Marathe, R. Ramanathan, S.S. Ravi). PDF
  58. "Cost constrained fixed job scheduling", Proceedings of the 8th Italian Conference, ICTCS 2003, Bertinoro, Italy, October 2003, "Theoretical Computer Science (LNCS 2841)", 111-124 (with Q. Huang). PDF
  59. "CLTC: A cluster-based topology control framework for ad-hoc networks," IEEE Trans. on Mobile Computing, 3(1) 2004, 18-32 (with C.-C. Shen, C. Srisathatpornphat, R. Liu, Z. Huang, C. Jaikaeo). PDF
  60. "Approximating the minimum number of maximum power users in ad hoc networks", ACM J. on Mobile Networks and Applications (MONET) 11, 2006, 129-142 (earlier version in Proc. Third ADHOC-NOW, Lecture Notes in CS, Vol. 3158 (Edited by I. Nikolaidis, M. Barbeau and E. Kranakis), 2004, pp. 1--13.) (with R. Liu and S.S. Ravi). PDF
  61. "A study of test coverage adequacy in the presence of stubs", Journal of Object Technology, 4:5 (2005) 117-137 (with B. Malloy). the paper
  62. "The impact of clustering in distributed topology control", International Conference on Communications in Computing 2006 (CIC'06), (with L. Zhao). PDF
  63. "The implementation of an extensible system for comparison and visualization of class ordering methodologies," Journal of Systems and Software 79:8 (2006), 1092-1109 (with N. Kraft, B. Malloy, P. Clarke) PDF
  64. "A Carrier Sense Multiple Access Protocol with Power Backoff (CSMA/PB)", Proceedings of the Fifth IFIP Annual Mediterranean Ad Hoc Networking Workshop (MedHocNet'06), (2006), 76-83 (with V. Syrotiuk, C. Colbourn, M. Cui). PDF
  65. "Topology Control for Simple Mobile Networks", IEEE Globecom 2006 - Wireless Ad Hoc and Sensor Networks Symposium, 2006, 6 pages on CD-ROM (with L. Zhao and S.S. Ravi). PDF
  66. "Topology Control for Constant Rate Mobile Networks", IEEE Globecom 2006 - Wireless Communications and Networking Symposium, 2006, 6 pages on CD-ROM (with L. Zhao and S.S. Ravi). PDF
  67. "Relay Node Placement in Wireless Sensor Networks", IEEE Transactions on Computers 56(2007), 134-138, (with G. Xue). PDF
  68. "A Carrier Sense Multiple Access Protocol with Power Backoff (CSMA/PB)", Journal of Ad Hoc Networks 5(2007), 1233-1250, (with V. Syrotiuk, C. Colbourn, M. Cui). PDF
  69. "Fault-tolerant Relay Node Placement in Heterogeneous Wireless Sensor Networks," IEEE Infocom 2007, (with X. Han, X. Cao, E. Lloyd, C-C. Shen). PDF
  70. "Topology Control Problems for Wireless Ad Hoc Networks," Handbook of Approximation Algorithms and Metaheuristics, Teofilo Gonzalez, Editor, Chapman and Hall/CRC (2007), 67-1 to 67-20, (with S.S. Ravi)
  71. "Optimal Relay Node Fault Recovery", 2nd International Workshop on Advances in Wireless Sensor Networks (IWASN), 2007, 8 pages on CD-ROM (with F. Che, and L. Zhao). PDF
  72. "Efficient Probe Selection Algorithms for Fault Diagnosis," Telecommunications Systems Journal 37(2008), 109-125 (with M. Natu and A. Sethi). PDF
  73. "Deploying Directional Sensor Networks with Guaranteed Connectivity and Coverage," 5th IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks - SECON 2008, 8 pages on CD (with X. Han, X. Cao and C.-C. Shen). PDF
  74. "Improved topology control algorithms for Simple Mobile Networks," Ad Hoc Nets '09, 10 pages PDF (F. Che, E. Lloyd and L. Zhao).
  75. "The Complexity of RP Selection in Multicast Channelization," Milcom '09, 6 pages PDF (with F. Che)
  76. "Incremental Channelization," Milcom '09, 6 pages PDF (with F. Che)
  77. "On-line Bin Packing", Fundamental Problems in Computing - Essays in Honor of Professor Daniel J. Rosenkrantz, S.S. Ravi, S. Shukla, K. Sandeep, eds. (2009), 25 pages (with Z. Ivkovic)
  78. "Fault-tolerant Relay Node Placement in Heterogeneous Wireless Sensor Networks," IEEE Trans. on Mobile Computing, 9(2010), 643 - 656. (with X. Han, X. Cao and C.-C. Shen).
  79. "Topology Control in Constant Rate Mobile Ad Hoc Networks," Wireless Networks, 16(2010), 467 - 480. (with L. Zhao and S.S. Ravi). PDF
  80. "Reverse Engineering Interface Protocols for Comprehension of Large C++ Libraries during Code Evolution Tasks," Journal of Software Engineering and Knowledge Engineering}, 24 pages (2011), (with Edward B. Duffy, Jason O. Hallstrom and Brian A. Malloy).
  81. "Relay Node Placement with Limited Relays," IEEE Globecom 2012, 7 pages (2012) PDF (with F. Che, J. Hallstrom, and S.S. Ravi).
  82. "Deploying Directional Sensor Networks with Guaranteed Connectivity and Coverage," Submitted to a journal (with X. Han, X. Cao and C.-C. Shen).
  83. "Simulation Analysis of Distributed CDS Algorithms," Submitted to a conference (with Y. Khadke, K. Ma, B. Graff, M. Patel), 2013.