Monday, July 18, 2005

directed hypergraphs and MDS scheduling

Assume we have unitarized the PRDG. Also, there exists no self-loops (A zero means no edge. That's it). We obtain a (n+d)*m matrix. What if we interpret this as a directed hypergraph?
--
We are looking for a cycle, the edge weights of which sums to zero. So does this map to the presence of a cycle in the new model?
A simple example with 2 vertices and anti-parallel edges of weights (1,-1) and (-1,1) shows a cycle in the new graph. What does this mean?
Are we asking for an APSP in hypergraphs?
We are looking at a type of graphs called directed hypergraphs. Call them DHG. How is a DHG represented? Show figures of the representation.
Found the tutorial paper.
--
Does this mapping from PRDG to DHG map to detection of cycles in the new graph?
Define a path and cycle. B-arc, F-arc.
We can do a DFS and assign to each vertex a DFS number.
--
To do: make examples and check them, especially the ones similar to KMW.
What does MDS mean? coloring?
--
Call as fictitious nodes, nodes that correspond to the bottom part of the block matrix. Cycles which involve the fictitious nodes donot seem to matter. Classify this statement.
Statement of the zero cycle detection: begin at an "actual" node and do a DFS. If we reach a node back, then we get to a cycle. Is this right?

--
To do: read how does a DFS detects cycles: types of edges: tree edges, back edges, cross edges and forward edges.
--
did some part of DV-KMW-EX.
A "ZC" should touch both the original vertices and also the new vertices.
Partition the nodes into actual nodes and dist-nodes (call them D-nodes). A ZC in the PRDG should touch both nodes and D-nodes.
--
Group the nodes into the G-nodes and D-nodes. If there exists a cycle which has at least one node from G-set and atleast one node from D-set, then we have a zero-cycle in the original PRDG. Mark a hyperedge e (u_1...u_i -> v_1...v_j) as dashed if u_k (k \in 1..i) \in G-set and v_l (l \in 1...j) \in D-set. Or otherwise.

Look up the definition of Hypergraph from here. Also, get the definition of dual of a hypergraph, among other definitions.
This is a restatement of the Farkas lemma.
--
Modular Memory allocation: fibonacci example.