Tuesday, June 14, 2005

Network matrices and total unimodularity

Reading Schrijver book for TUM. Some notes
Bipartite graphs are TUM.
Directed graphs are TUM.
Max-flow min-cut theorem is a restatement of TUMity
Network matrices (NM) are TUM. NM
  • are a superset of directed graphs.
  • are obtained by a tree and the flow it induces on a directed graph.
  • If we call a tree on a directed graph as T and define the "flow" induced by the tree on the graph by a matrix M, we can characterize the TUMity of M.
  • There exists two matrices which are not network matrices, but are TUM.
  • Set of matrices which are TUM = set of NM matrices + those two special matrices.
    Look up these lecture notes on network matrices. The complete lecture notes is this. The lecture notes give the significant points about TUMity. Also the thesis by Koyntek, which introduces "binet matrices", a generalization of NM. There are some good explanations (esp. figures) in the thesis that are not present in either Schrijver's book or in the book by Cook et. al.

  • M seems to mean a flow. Is that right?
  • What has simplex algorithm have to do with network matrices?
  • No comments: