## Saturday, June 18, 2005

### Presence of multi-dimensional schedules in a graph theoretic way

Suppose we assume that Bx <> 0
This can be written as two inequalities
• Bx >= 1
• Bx <= -1
• We can search for a vector x that satisfies these constraints using a graph-theoretic fashion.
Hints:
• look up the max-flow min-cut proof for TUM.
• how did Tarjan solve the problem?
• How can this problem be solved in that way?
• What does multi-dimensional schedules mean in a graph theoretic way?

• Note: Interval graphs are duals of directed graphs. If we transpose the incidence matrix of a directed graph, we obtain a interval graph. Correction: We obtain a interval matrix, not a interval graph. Question: how are interval matrices and interval graphs related?

Things to do
-----------
read the max-flow min-cut from the lecture notes

The theorem essentially uses the fact that if a graph is directed, its incidence matrix is TUM
It can also be checked for TUMity in polynomial time
--

how are network matrices different from directed graphs

some terminology
Weakly connected digraph: if the underlying directed graph is connected
------------------
interval graphs idea
--
interval graphs idea
exercises from lecture notes and cook..
---------------
NOTES from Golumbic:
interval graphs lead to PQ trees => how does that help?
----------------
Interval graphs Vs. interval matrices: What is the difference?
----------------
• TUMity is a hereditary property.

• Goldberg and Sailesh Rao have an extremely fast algorithm in a graph theoretic way for the max-flow problem. Have a look at it. This is the link.

• -----------
A simple proof:
STMT1: TUMity of the directed graph to proof of KMW: This is in the spirit of the max-flow min-cut proof.
statement of KMW: either there exists a null-weight cycle or there exists a (possibly multi-dim-time) schedule
STMT2: Decompose the input PRDG into one whose dependences can lead to a TUM matrix. Use the equivalent of Menger's theorem for getting possibly faster schedules possibly in a better runninhg time