## Tuesday, June 21, 2005

### A simple proof for existence of rational schedules

If total-unimodularity of incidence matrices of digraphs implies max-flow min-cut theorem, why should it not imply integral schedules?
Premise: The incidence matrix of the PRDG is TUM.
To prove: either there exists a null-weight cycle or there exists a multi-dimensional time schedule

let the weight of an edge e_i be given by w(e_i) \in \mathcal(Z)^d
(we will talk about the unitarization case later)

--
to do:
• check up darte-vivien for the main statement for schedules
• check up the main results about interval graphs: in particular, about unit-interval graphs: and PQ trees in any books

• --
notes from schrijver-notes
Interval graphs are TUM
Interval graphs are one more special cases of network matrices (directed graphs are the other special case of network matrices)