CS 6381-001: Combinatorics and Graph
Algorithms
FALL
2021: TR: 10:00 -- 11:15 a.m. ECSN:
2.112(HYBRID)
Instructor: R. Chandrasekaran
Office: ECSS 4.611
Phone: (972) 883-2032
E-mail:
chandra AT utdallas DOT edu
Office Hours: M: 1:30 -- 3:00
URL: http://www.utdallas.edu/~chandra
Teaching Assistant :
Office hours and Office:
email:
Prerequisites: CS 6363 ; or consent of the instructor.
Instructions
for this course
Audio/Video Files
Lecture#1
Lecture#2
Lecture#3
Lecture#4
Lecture#5
Lecture#6
Lecture#7
Lecture#8
Lecture#9
Lecture#10
Lecture#11
Lecture#12
Lecture#13
Lecture#14
Lecture#15
Lecture#16
Lecture#17
Lecture#18
Lecture#19
Lecture#20
Lecture#21
Lecture#22
Lecture#22B
Lecture#23
Lecture#24
Lecture#25
Lecture#26
Lecture#27
Lecture#28
Lecture#29
Lecture#30
Lecture#31
Lecture#32
Course Outline
- Graph Theory
- 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
- Orthogonality
- Single Commodity Maximum Flow
Problem
- Single Commodity
Multi-terminal Flows
- Spanning Tree Problem
- 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
- 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
- Unimodularity and Integrality
- 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
- Blocking Systems and
Polyhedra
- Bottleneck Problems
- Blocking Systems
- Blocking and Antiblocking Polyhdera
- Perfect Graph Theorem
-
- Multicommodity Flows
- General Problem
- Two Commodity
- T.C. Hu's work
- M. Sakarovitch
- Rothschild and Whinston
- H-Graphs
- 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
- Total Dual Integrality
- General Theory
- Integer Rounding
- General Algorithm for Solving TDI Optimization
Problems
- Testing
- Special Cases
- Hilbert Basis
- Geometry of Numbers
- Introduction
- Lattice Basis Reduction Techniques
- Lenstra's Algorithm
- Scarf's Work
- Tardos - Frank Simultaneous Approximation
- Other Applications
Assignments
Click here to go back ...