CSE 736 - Schedule

Note: this page will be updated on or before every Tuesday at noon, so that you can print out the related materials before coming to the seminar. This excludes the first seminar.

Date	Speaker	Topic
Wed Jan 23	Hung Q. Ngo	Class information Brief introduction to the field Indirect Networks Matching Theory and Related Problems
Chapter 1 of my thesis Matching Theory (last updated Tuesday Jan 29, 2002) Linear Algebra (last updated Wednesday Jan 23, 2002) Puzzle
Wed Jan 30	Hung Q. Ngo	More Graph Theory & Matching Theory Clos Networks: rearrangeably nonblocking.
Indirect Networks and Clos Networks (last updated Monday Jan 28, 2002) Puzzle
Wed Feb 06	Hung Q. Ngo	Clos Networks: SNB, WSNB and associated problems.
Indirect and Clos Networks (last updated Tuesday Feb 05, 2002) - added the new section on WSNB and a few minor fixes. Matching Theory (last updated Tuesday Feb 05, 2002) - updated the section on basic definitions and a few minor corrections. Puzzle
Wed Feb 13	Hung Q. Ngo	The Benes Conjecture Multicasting, Broadcasting in Indirect Networks
The Benes Conjecture Puzzle Homework 1 (due Wed Feb 27): do exercises 8.4, 8.10, 8.11, 8.12 in the updated chapter on matching theory. (This is for those who want to get A/F grades only) NP-Completeness H. Wilf's Algorithms and Complexity book (read chapters 1, 3 and 5) A compendium of NP optimization problems (for reference) Stephen Cook, The P versus NP Problem, April, 2000. Manuscript prepared for the Clay Mathematics Institute for the Millennium Prize Problems (revised November, 2000).
Wed Feb 20	Hung Q. Ngo	NP-Completeness Introduction to Approximation Algorithms
Ding-Zhu Du and Ker I Ko's book on approximation algorithms: Chapter 1: Introduction to Approximation Algorithms Chapter 2: Linear Programming Chapter 3: Greedy Approach Chapter 7: Adaptive Partition Petr Slavik's thesis has a good introductory chapter on NP-completeness and several chapters on set cover problems. There was a typo in exercise 8.12 of the chapter on matching theory. Thanks to Joaquin for pointing this out. Here is the chapter with the correction. Puzzle Graph Theory In Practice (Link Provided by Vikas P. Verma)
Wed Feb 27	Hung Q. Ngo	Approximation Algorithms: Greedy Approach and Linear Programming
Puzzle Read Du & Ko's notes, chapters on Greedy Approach and Linear Programming G. Xue, "Minimum Cost QoS Unicast and Multicast Routing in Communication Networks" Guha and Khuler, Approximation Algorithms for Connected Dominating Sets Homework 2 (due Wed. Mar 13): This is on NP-completeness. Even if you don't want to get A/F grades, you should do the homeworks to see how good you understand materials presented in class.
Wed Mar 06	Hung Q. Ngo	More on Linear Programming Several Problems in Optical Networks Several Problems in Wireless Networks
Puzzle
Wed Mar 13	Hung Q. Ngo	Several Problems in Optical Networks Several Problems in Wireless Networks
Puzzle
Wed Mar 20	Purnima M Mavinkurve	Efficient Communication Strategies for Ad-Hoc Wireless Networks
Wed Mar 20	Yang Chen	Performance Analysis of Wavelength Assignment Policies in All-Optical Networks with Limited-Range Wavelength Conversion
Puzzle Homework 3 (due Wed. Apr 24): This is on Approximation Algorithms Exercises 2.10, 2.11, 2.12 of Du & Ko's Chapter 2: Linear Programming Exercise 3.17 of Du & Ko's Chapter 3: Greedy Strategies (Note that Part (5) asks you to show Theorem 3.4.3)
Wed Mar 27	No class	Fall Recess
Probability Theory Algebraic Graph Theory The Probabilistic Method
Wed Apr 03	Dazhen Pan	Computing Approximate Blocking Probabilities in Wavelength Routed All-Optical Networks
Wed Apr 03	Sumesh J Philip	Broadcast in radio networks.
Puzzle
Wed Apr 10	Prabhat K Tripathi	The complexity of end to end communication in memoryless networks
Wed Apr 10	Himanshu Mehra	Power consumption in packet radio networks
Puzzle
Wed Apr 17	Vivek Kumar	Protection and Restoration in Optical Networks.
Wed Apr 17	Ravindranath Gummadidala	TCP-like Congestion Control for Layered Multicast Data Transfer
Puzzle
Wed Apr 24	Rajesh Sriperumbudur	A class of interconnection networks for multicasting.
	Sumit Eapen	A Necessary Condition for Wise-sense Nonblocking Clos Network
	Joaquin Carbon	Characterizing Indirect Network Topologies and Their Line-graph Topologies
Puzzle
Wed May 01	Jikai Li	Fairness in Routing and Load Balancing.
Wed May 01	Elena Braynova	Selection Networks
Puzzle

Interconnection Network Seminar (CSE736) SUBNET group Spring 2002

Interconnection Network Seminar (CSE736)
SUBNET group
Spring 2002