Tuesday, July 05, 2005

Unitary graph zero cycle detection

We can unitarize a PRDG arbitrarily, so that all the components of the graph are from the set {-1,0,+1}.

In 2-dimensions, all the edge weights have been mapped to the 9 points on a unit square.
1 2 3
4 5 6
7 8 9

Now point 5 does not add to the weight of any cycle.
Call the points (1,4,7) as -ve-red, call points (3,6,9) as +ve-red
Call the points (7,8,9) as -ve-blue, call points (1,2,3) as +ve-blue

To do: Look at the examples in KMW
unitarization may not be necessary, if we somehow convert a distance vector into into its angle represented by a value on the unit-hypercube and magnitude represented by ????????????
In higher dimensions, we can consider the 3X3 matrix, with some less number of nodes as base case and properly split graphs of large number of nodes, edges and high dimensions.
To Do: do a search for fast linear programming algorithms when the matrices are unitary. May want to search for linear programming unit cost etc...
Imagine the graph annotated by the the vectors. Now Decompose the components into atmost two components, each is from of 2,4,6,8. Remove the edges which donot have components that influence the components on another side.?????