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)

    No comments: