ST: Advanced Algorithms for Graphs and Networks - CS 6/79995

(Research oriented Course)

Spring 2009

MW 2:15 pm - 3:30 pm

MSB 276

Instructor
Office Hours   
   
      
Email 
Telephone

Dr. Feodor Dragan 
Room 254 MSB
MW 1:45 – 2:15  PM, M 3:30 – 5:00 pm  
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 and Analysis of Data. This is a graduate level and research oriented course.
  • Course Content:  We will have discussions on some of the following topics and more.
    • Location problems: centers, medians, centroids, diameter, p-centers, r-domination,  p-medians
    • Labeling schemes: NCA-queries, adjacency, connectivity, reachability, distance, routing
    • Network design: minimum spanning trees, diameter-bounded minimum spanning trees, light approximate shortest path trees, Steiner trees, optimal communication spanning trees,  tree covers and spanners, tree spanners, collective tree spanners, flow spanners
    • Navigating in a graph: Message routing, hierarchical cluster-based routing, interval routing, labeling routing schemes, routing in mobile ad-hoc networks, pseudo coordinates, navigating with aid.
    • Balanced separators of graphs and their use.
  • Prerequisites
    CS 4/56101 (Design and Analysis of Algorithms).
  • Supplementary Texts
    • Lecture notes
    • D. Peleg, Distributed Computing: A Locality-Sensitive Approach, SIAM Monographs on Discrete Mathematics and Applications, 2000.
    • J. Spinrad, Efficient Graph Representations, Fields Institute Monographs, 19, 2003.
    • B.Y. Wu and K.-M. Chao “Spanning Trees and Optimization Problems”, CRC Press, 2003
    • J. Cheriyan and R. Ravi,  Approximation Algorithms for Networks Problems, http://www.gsia.cmu.edu/afs/andrew/gsia/ravi/WWW/new-lecnotes.html
    • D. Hochbaum (ed.) “Approximation Algorithms for NP-hard Problems” PWS Publ.Co. 1995
    • T. H. Cormen, C. E. Leiserson, R. L. Rivest   and C. Stein “Introduction to Algorithms”, MIT Press, 2001 (2nd edition)
    • A number of recent journal and conference papers.
  • Course Requirements: Research project, presentations and final exam-quiz (12:45 - 3:00 p.m. Wed. May 13). 
  • Cheating and Plagiarism: Copying the solution from another student or jointly writing up the solution of a problem constitutes plagiarism. You are not permitted to use solutions to assigned problems from earlier terms.  Such activities and other unapproved or anti-intellectual behavior violate the University's plagiarism rules and can result in severe penalties. Behavior of this type is unfair to both yourself (in missed learning opportunities) and to the other students. University rules on plagiarism are given here and on sanctions are here.
  • Student Accessibility: University Policy 3342-3-01.3 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 Accessibility Services (contact 330-672-3391 or visit www.kent.edu/sas for more information on registration procedures).
  • Registration Requirement:  The official registration deadline for this course is Feb. 1, 2009.  University policy requires all students to be officially registered in each class they are attending.  Students who are not officially registered for a course by published deadlines should not be attending classes and will not receive credit or a grade for the course.  Each student must confirm enrollment by checking his/her class schedule (using Student Tools in FlashFast) prior to the deadline indicated.  Registration errors must be corrected prior to the deadline


F. Dragan
dragan at cs kent edu
Spring  2009