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

    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?
    ----------------
  • 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

    No comments: