CS 6381: Combinatorics and Graph Algorithms

                                                                    ECSS 2.201; TR: 10:00--11:15

Instructor: R. Chandrasekaran

Office: ECSN 4.622 (Please Note: This is in the "old" building!!

Phone: (972) 883-2032 E-mail: see main page
Office Hours: TR:  3:00 -- 4:00.
URL: http://www.utdallas.edu/~chandra

Teaching Assistant : Mehmet Baysan

Office: M 2:15-3:45 at 4.201; W 12:15-2:45 at open lab first floor
 

email:

Prerequisites: CS 6363 ; or consent of the instructor.

IMPORTANT!!!: Class on May 1 will meet at ECSS 4.910 at 10:00 since our regular room is occupied at a that time for an exam. Please let your friends in the class know if you see this. 

Grading Scheme

Homework and presentations (Schedule TBA)

Course Outline

1. Graph Theory
   • Definitions and Concepts
2. Matrices Associated with Graphs
   • Node-Arc Incidence Matrix
   • Arc Chain Incidence Matrix
   • The Loop or Mesh Matrix
   • The Node-Edge Incidence Matrix
   • The Cut-set Matrix
   • Orthogonolity
3. Single Commodity Maximum Flow Problem
   • Formulation as an LP
   • Max-Flow-Min-Cut Theorem
   • Labeling Algorithm
   • Finite Termination of Maximum Flow Algorithm
     • Ford-Fulkerson Example
     • Queyranne Example
   • Strongly Polynomial Algorithms
     • Edmonds-Karp
     • Dinic
     • Karzanov
     • Maheshwari et al.
   • Special Cases
     • Undirected Networks
     • Parallel Arcs
     • Multiple Origins/Destinations
     • Node Capacities
   • Arc Chain Formulation and Chain Decomposition of Flows
   • Lower Bounds and Exogeneous Flows
   • Picard-Queyranne work and Structure of Cuts
   • MIT Work
   • Single Commodity Multi-route Maximum Flow Problem
   • Single Commodity Fault Tolerant Maximum Flow Problem
   • Examples of Multi-route and Fault Tolerant Flows
4. Single Commodity Multi-terminal Flows
5. Spanning Tree Problem
6. Shortest Path Problem
   • Structure
     • Specified Pair of Nodes
     • One Origin Several Destinations
     • All Pairs
     • Acyclic Graphs
     • Undirected Graphs
   • Data
     • Nonnegative Distances
     • Time Dependent Distances
     • Non-negative Cycles
   • Methods Used
     • Linear Programming Formulation
     • Dynamic Programming
     • Inductive Algorithm
     • Analog Devices
     • Matching Formulations
   • Objective Functions
     • Negative Cycle Detection
     • Ratio Functions
     • Ratio Functions on Cycles
     • kth Shortest Paths
     • Shortest Paths Through Specified Nodes
     • Odd and Even Shortest paths
   • Applications
     • PERT
     • Reliability
     • Ship Routing
     • Investments in Blocking Systems
7. Minimum Cost Flows (Example added new!!! June 25-2003)
   • Transportation and Primal Dual Algorithm
   • Out-of-kilter Algorithm
   • Klein's Algorithm
   • Edmonds-Karp Scaling
   • Zadeh's Examples
   • Strongly Polynomial Algorithms
     • E. Tardos
     • Fujishige
     • Simplex
     • Goldberg-Tarjan
     • PERT-CPM
8. Unimodularity and Integrality
9. Matching
   • Bipartite
   • General
   • Applications
     • Chinese Postman Problem
     • Scheduling
     • Odd and Even Shortest Paths
     • Shortest Paths in Undirected Networks with no Negative Cycles
     • Geometric Applications
     • Applications to Chemistry
   • Ellipsoid Algorithm and the Odd-Cut Problem
   • T-joins and T-cuts
   • Claw-free Graphs
   • Matching Example-bipartite
10. Blocking Systems and Polyhedra
    • Bottleneck Problems
    • Blocking Systems
    • Blocking and Antiblocking Polyhdera
    • Perfect Graph Theorem
11.  
12. Multicommodity Flows
    • General Problem
    • Two Commodity
      • T.C. Hu's work
      • M. Sakarovitch
      • Rothschild and Whinston
    • H-Graphs
      • Single Star
      • Two Stars
      • Complete Graph and its Equivalents
      • Cut Based Problems
      • (2,3)-Metric Based Problems
13. Matroids 
    • Introduction
    • Equivalent Axioms
      • Independence
      • Circuits
      • Bases
      • Rank Function
      • Hyperplanes, flats etc.
      • Greedy Algorithm
    • Optimization Problems and Algorithms
      • Covering
      • Partition
      • Intersection
      • Parity
    • Polyhedral Charecterizations
    • Operations
      • Union
      • Deletion
      • Contraction
      • Truncation
      • Minors
      • Duals
      • Splitters
      • Decomposition and Composition
    • Applications
      • Testing Graphicness
      • Testing Regularity (Total Unimodularity)
      • Max-Flow-Min-Cut Matroids
    • Pseudomatroids
14. Total Dual Integrality
    • General Theory
    • Integer Rounding
    • General Algorithm for Solving TDI Optimization Problems
    • Testing
    • Special Cases
    • Hilbert Basis
15. Geometry of Numbers
    • Introduction
    • Lattice Basis Reduction Techniques
    • Lenstra's Algorithm
    • Scarf's Work
    • Tardos - Frank Simultaneous Approximation
    • Other Applications

Assignments

• Assignment #1
• Solution #1
• Solution #1.7  
• Assignment #2
• Solution #1.6,1.7 
• Assignment #3
• Assignment #4
• Solution #2.1 
• Solution #2.2-1
• Solution #2.2-2
• Solution #2.3
• Solution #3.3
• Solution #3.4
• Books
• Books-ii
• Topics and Papers

Click here to go back ...