The ordinary nodes correspond to the number of times an edge has been selected in the PRDG. A hyperedge is from a subset of (ordinary) nodes to a subset of nodes. Either the head of the edge, or the tail of the edge can be a zero size subset.
Now define the arity of a hyperedge as the sum of its indegrees and outdegrees.
Some simple observations:
for a hypernode v with an edge S to T, if indegree(v) = outdegree(v) = 1 (or card(S)=card(T)=1), then we can "club" the two singleton sets to make another singletonset. The hyperedges which begin or end at the vertices of the sets S and T can be made to correspondingly begin or end at the new vertex, which can be called its own singleton set.
The hypernodes can be stored in a priority queue, which supports the following operations:
Also, a hypernode v such that indegree(v) = 0 or (outdegree(v) =0) can be removed from the queue. This would lead us to a pruning of the graph:
removal of the hypernode from the priority queue: This hypernode may not be at the top of the priority queue.
pruning the hyperedges which begin or end at these vertices
--
TO DO: try to see some examples of the particular linear programs of unitary form.
solve the dual linear programs
look at the original and dual graphs
Posts
