This can be written as two inequalities

**Hints:**

**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**

read the same from Schrijver

read the same from Cook

read the same from Schrijver

read the same from Cook

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

--

read about network matrices from all three sources

how are network matrices different from directed graphs

read about network matrices from all three sources

how are network matrices different from directed graphs

some terminology

Weakly connected digraph: if the underlying directed graph is connected

------------------

interval graphs idea

--

read about network matrices from all three sources

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?

----------------

*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**

## No comments:

Post a Comment