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.
  • 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: