Return to Errol's Homepage

Errol L. Lloyd

Curriculum Vita
April 2008

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/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 
                Computer Science and Engineering, College of 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
        Program Committee - DIAL M for Mobility Workshop - 1999
        Program and General Chair - DIAL M for Mobility Workshop - 2000
        Steering Committee Member - DIAL M for Mobility Workshop - 2001-present
        Program Committee - ATIRP Conference - 2001
        Program Committee - Third IEEE Conference on Mobile and Wireless Communication Networks MWCN'2001
        Program Committee - IEEE Workshop on High Performance Switching and Routing (HPSR2004)
        Program Committee - Workshop on AlgorithmS for Wireless And mobile Networks (A_SWAN'04)
        Area Editor - "Mobile Algorithms and Complexity" of  SIGMOBILE's
            Mobile Computing and Communications Review (MC2R) - 2002-2005.
        Program Committee - IEEE International Performance Computing and Computing Conference (IPCCC'06).
        Program Committee - IEEE Symposium on Wireless Ad hoc and Sensor Networks (part of Globecom 2006)
        Program Committee - Adhoc-Now 2006
        Program Committee - ICC 2007
        Program Committee - DIALM 2007
        Program Committee - IEEE 2007 Int'l Symposium on Parallel and Distributed Processing with Applications (ISPA-07)
        Program Committee - IEEE Globecom 2007 Ad-hoc and Sensor Networking Symposium - GC'07 ASNS
        Area Editor - Ad Hoc Networks (journal) - 2007-present

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-08
                Co-PI (with 4 others) for UD portion.





PhD Students



        S.S. Ravi - 1984 - Heuristics for PLA Folding: An Analytical Approach 
                (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, Cambridge, Mass) 

        Z. Ivkovich - 1995 - Incremental approximations 
                (Assistant Professor of Finance, Univ of Illinois, Urbana-Champaign) 

        H. Tadepalli - 1996 - Scheduling DAGs with Communication Constraints
                (Senior Engineer, Intel Corporation) 

        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
                (Retek, Inc. )



        Q. Huang - 2004 - Multimedia Gateway Call Routing and Scheduling 
                (UTStarcom Inc.)



        L. Zhao - 2007 - Topology Control for Mobile Ad-hoc Networks
(Qualcomm)






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. 


  2. 
"List scheduling bounds for UET systems with resources," Information Processing
Letters, 10 (1980), 28-31.
    3. 


  3. 
"Concurrent task systems," Operations Research, 29 (1981), 189-201.
    4. 


  4. 
"Coffman-Graham scheduling of UET task systems with 0-1 resources," Information
Processing Letters, 12 (1981), 40-45.
    5. 


  5. 
"Critical path scheduling with resource and processor constraints," Journal
of the ACM, 29 (1982), 781-811 (earlier version: STOC 1980).
    6. 


  6. 
"An O(n log m) algorithm for the Josephus Problem," Journal of Algorithms,
4 (1983), 262-270.
    7. 


  7. 
"On a simple deadlock recovery problem," Information Processing Letters,
16 (1983), 175-178.
    8. 


  8. 
"One layer routing without component constraints," Journal of Computer
and System Sciences, 28 (1984), 420-438 (with S.S. Ravi).
    9. 


  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. 


  10. 
"On the worst case performance of buddy systems," Acta Informatica, 22
(1985), 451-473 (with M.C. Loui).
    11. 


  11. 
"Two processor scheduling with limited preemption," Performance Evaluation,
6 (1986), 307-312.
    12. 


  12. 
"Minimizing channel density in standard cell layout," Algorithmica, 2 (1987),
267-282 (with J.R.S. Blair, S. Kapoor, K. Supowit).
    13. 


  13. 
"Scheduling with semaphore constraints," Operations Research Letters, 6
(1987), 121-124.
    14. 


  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. 


  15. 
"The complexity of near-optimal PLA folding," SIAM Journal on Computing,
17 (1988), 696-710 (with S.S. Ravi).
    16. 


  16. 
"A fast algorithm for finding interlocking sets," Information Processing
Letters, 32 (1989), 47-50.
    17. 


  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. 



  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. 


  19. 
"Minimizing external wires in generalized single-row routing," IEEE Transactions
on Computers, 41(1992) 771-775 (with J.R.S. Blair).
    20. 


  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. 


  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. 


  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. 


  23. 
"Graph theoretic analysis of PLA folding heuristics," Journal of Computer
and Systems Sciences, 46(1993), 326-348 (with S.S. Ravi) .
    24. 


  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. 

  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


  26. 
"Efficient Distributed Algorithms for Channel Assignment in Multihop Radio
Networks", Journal of High Speed Networks, 2(1993), 405-423 (with R. Ramanathan).
    27. 


  27. 
"Scheduling DAGs for asynchronous multiprocessor execution," IEEE Transactions
on Parallel and Distributed Computing, 5(1994), 498-508 (with B. Malloy
and M.L.Soffa).
    28. 


  28. 
"On k-coloring a set of intervals", Discrete Applied Mathematics 59(1995),
225-235 (with M. Carlisle).
    29. 
PDF


  29. 
"River routing with a generalized model," Journal of Computer and System
Sciences, 53(1996) 525-544 (with J.R.S. Blair).
    30. 


  30. 
"Scheduling task trees on linear arrays of processors", International Parallel
Processing Syposium (IPPS), 1996, 584-590 (with H. Tadepalli).
    31. 


  31. 
"A fundamental restriction on fully dynamic maintenance of bin packing,"
Information Processing Letters, 59(1996), 229-232 (with Z. Ivkovich).
    32. 

PDF


  32. 
"Partially dynamic bin packing can be solved within 1+e in (amortized)
polylogarithmic time", Information Processing Letters 63(1997) (with Z.
Ivkovich), 45-50.
    33. 

PDF


  33. 
"Experimental results on broadcast scheduling in packet radio networks,"
Proceedings of the 1st ATIRP Annual Conference, 1997 (with X. Ma).
    34. 


  34. 
"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


    35. 


  35. 
"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.
    36. 

PDF


  36. 
"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


    37. 



  37. 
"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).
    38. 


  38. 
"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).
    39. 


  39. 
"Evaluation of a Distributed Broadcast Scheduling Protocol for Multihop
Radio Networks," Proceedings of MILCOM 2001 (with X. Ma).
    40. 

PDF


  40. 
"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).
    41. 

PDF

  41. 
"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).
    42. 

PDF

  42. 
"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

    43. 

  43. 
"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
    44. 

  44. 
"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

    45. 

  45. 
"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).

  46. 
"Topology control with diameter constaint," Proceedings of CTA
Conference on Communications and Networks (2003), 313-318
(with R. Liu).

  47. 
"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

  48. 
"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

  49. 
"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


  50. 
"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


  51. 
"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


  52. 
"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



  53. 
"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


  54. 
"The impact of clustering in distributed topology control", 
International Conference on Communications in Computing
2006 (CIC'06),
(with L. Zhao).

PDF


  55. 
"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


  56. 
"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 


  57. 
"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 


  58. 
"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 


  59. 
"Relay Node Placement in Wireless Sensor Networks", IEEE Transactions on Computers
56(2007), 134-138, (with G. Xue).

PDF


  60. 
"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 


  61. 
"Fault-tolerant Relay Node Placement in Heterogeneous Wireless Sensor Networks,"
IEEE Infocom 2007,
(with X. Han, X. Cao, E. Lloyd, C-C. Shen).
 PDF 


  62. 
"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) 
    63. 


  63. 
"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 


  64. 
"Efficient Probe Selection Algorithms for Fault Diagnosis,"
Telecommunications Systems Journal 37(2008), 109-125  (with M. Natu and A. Sethi).
 PDF 


  65. 
"Deploying Directional Sensor Networks with Guaranteed Connectivity and Coverage,"
To appear at 5th IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks 
 - SECON 2008 (with  X. Han,  X. Cao and C.-C. Shen). 
 PDF 


  66. 
"Topology Control in Constant Rate Mobile Ad Hoc Networks,"
To appear in Wireless Networks (with L. Zhao and S.S. Ravi).
 PDF 


  67. 
"Topology Control for Monotone Properties in
Simple Mobile Ad Hoc Networks," Submitted to a journal (with L. Zhao and S.S. Ravi).