ST:
Advanced Algorithms for Graphs and Networks - CS 6/79995
(Research oriented Course)
Fall 2005
Tuesday, Thursday 12:15 - 1:30 PM
MSB 276
Instructor Office Hours Email Telephone
Dr. Feodor Dragan
Room 254 MSB
TR 2:30 - 4:30 p.m.
and by appointment dragan
at cs.kent.edu
(330) 672-9058
Outline: The course will
focus on advanced algorithms for practical problems arising in
Communication
Networks. This is a graduate level and research
oriented course.
Course Content: We
will discuss the following
topics.
Basics
Graph theory definitions,
shortest paths
The set covering problem
Network Design
Minimum spanning trees
Light approximate shortest path
trees
Minimum routing cost spanning trees
Optimal communication spanning
trees
Diameter-bounded minimum spanning
trees
The Steiner tree problem
Minimum k-connected spanning
subgraphs
Tree covers and (flow-)
spanners and collective
spanners
Proximity preserving labeling
schemes and routing
labeling schemes
Facility Location Problems
Center and median problems
Uncapacitated facility location
Near-Optimal Cuts of Graphs
Minimum cuts
Balanced separators of graphs
Bicriteria Approximation
Bicriteria approximation algorithms for network
design problems
Prerequisites
CS 4/56101 (Design and Analysis of Algorithms).
B.Y.
Wu and K.-M. Chao “Spanning Trees and Optimization Problems”, CRC
Press, 2003
D.
Hochbaum (ed.) “Approximation Algorithms for NP-hard Problems” PWS
Publ.Co.
1995
D.
Peleg “Distributed Computing: A Locality-Sensitive Approach” SIAM
Monographs on
Discrete Mathematics and Applications, 2000
T. H. Cormen,
C. E. Leiserson, R. L. Rivestand C.
Stein “Introduction to
Algorithms”, MIT Press, 2001 (2nd edition)
A number of recent journal and
conference papers.
Course Requirements: Research
project, presentations
and take-home final exam.
Students with Disabilities: University
policy 3342-3-18 requires that students with disabilities be provided
reasonable accommodations to ensure their equal access to course
content. If you have a documented disability and require
accommodations, please contact the instructor at the beginning of the
semester to make arrangements for necessary classroom adjustments.
Please note, you must first verify your eligibility for these through
Student Disability Services (contact 330-672-3391 or visit
www.kent.edu/sds for more information on registration
procedures).