ST: Advanced Algorithms for Communication Networks
and VLSI CAD - CS 6/75995
(Research oriented Course)
Spring 2003
Tuesday, Thursday 2:45 -4:00 PM
MSB 376
Instructor Office Hours Email Telephone
Dr. Feodor Dragan
Room 254 MSB
TR 1:30 - 2:30 and 4:15 - 5:15 p.m.
and by appointment
dragan@cs.kent.edu (330) 672-9058
Outline: The course will
focus on advanced algorithms for practical problems arising in Communication
Networks and VLSI CAD. This is a graduate level and research
oriented course. The course should result in at least one common (all
participants of the course) publishable paper .
Course Content: We will discuss the following
topics.
Network design; minimum spanning trees, diameter-bounded
minimum spanning trees, light approximate shortest path trees, Steiner
trees, tree covers and spanners.
Network decompositions; clusters, covers and partitions.
Facility location problems; center and median problems,
r-domination problems.
Message routing, hierarchical cluster-based routing, deadlock-free
routing, interval routing, labeling routing schemes, routing in mobile
ad-hoc networks.
Proximity preserving labeling schemes.
Protocols for improvement of communication networks survivability
and reliability.
Heuristics and approximation algorithms for physical design
of VLSI CAD.
Near-optimal cuts of graphs, node multiway cuts, balanced
separators of graphs.
Hierarchical placement (top-down and bottom-up techniques),
clock routing.
Tools for design methods of field-programmable gate arrays.
Prerequisites
CS 4/56101 (Design and Analysis of Algorithms).
Texts
Lecture notes
D. Peleg, “Distributed Computing: A Locality-Sensitive Approach”,
SIAM Monographs on Discrete Mathematics and Applications, 2000.
N. A. Sherwani, “Algorithms for VLSI Physical Design
Automation” (3rd edition), Kluwer Academic, 1999.
J. Cheriyan and R. Ravi, “Approximation Algorithms
for Networks Problems”, http://www.gsia.cmu.edu/afs/andrew/gsia/ravi/WWW/new-lecnotes.html
A number of recent journal and conference papers.
Supplementary Text
S.H.Gerez, “Algorithms for VLSI Design Automation”,
John Wiley & Sons, 1999.
C. E. Perkins (ed.), “Ad Hoc Networking”, Addison
Wesley, 2000.
A. B. Kahng and G. Robins, “On Optimal Interconnections for
VLSI”, Kluwer Academic Publishers, 1995
D. Hochbaum (ed.), “Approximation Algorithms for NP-hard
Problems”, PWS Publishing Co. 1995.
T. H. Cormen, C. E. Leiserson and R. L. Rivest,
“Introduction to Algorithms” (2nd edition), MIT Press, 2001.
Course Requirements: Research project, presentations
and take-home final exam.
Students with Disabilities
In accordance with university policy, if you have a documented
disability and require accommodations to obtain equal access in this course,
please contact the instructor at the beginning of the semester or when
given an assignment for which an accommodation is required. Students with
disabilities must verify their eligibility through the Office of Student
Disability Services (SDS) in the Michael Schwartz Student Services Center
(672-3391).