Wednesday, August 10, 2005

unitarization and directed hypergraphs: more thoughts

It is clear that unitarization results in a directed hypergraph. Also, a zero-weight cycle is a path from a vertex to itself.

Fact: if the given graph has a 1-dimensional schedule, it has one sequential loop. If it has as 2-d schedule, it has a 2-d schedule.
So, what can we say about the presence of a k-d schedule and the limits of doing something in the graph with 1 and d? (ala sandwitch theorem.)

What can we say about the presence of d-dim schedules?

Are you sure that the depth is min(n,d). Or does it have to be d?

No comments: