Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Update: There is an answer on same question I posted on Stack Overflow.

I'm working on data structure for graph cut algorithm. Problem is to make different cuts on shortest paths. I made data structure for which I'm not sure about properties.

Input is directed graph of shortest paths, which is bounded lattice, partially ordered set with minimum and maximum element.

Define next node N(n) of node n as a set of nodes b for which a < b and there is no c with a < c < b. Similar define previous node P(n). Extend definitions on sets, N(S) union of N(n) for $n \in S$, similar for P(S).

It is easy to make different cuts on list of set of nodes $L, N(L), N(N(L)), ...$ where for each neighboring pair of sets A, N(A)=B holds that there is no partition of $A=A_1 \cup A_2$ and $B=B_1 \cup B_2$ with $B_i = N(A_i)$, $A_i = P(B_i)$ for $i=1,2$. With this property create new lattice with mapping:

  • sub-lattice to one node
  • if upper partition is found create partition cardinality number of edges.

In simple, algorithm for lattice -> lattice mapping is:

A = {minimum node}
new_node = [A]
while A, N(A) don't have partitions
  append N(A) to new_node
  A = N(A)
for each partition $B_i$
  last_new_node = new_node
  create new_node = [B_i]
  create edge last_new_node to new_node
  go to 1
At the end fix maximum node in new lattice if needed

This algorithm can be called repeatedly on new lattices. I'm concern about:

  • Is there guaranty to reach one-node lattice?
  • Is there any measure of number of iterations to reach one-node lattice? It seams to me that bound is diameter of input graph.

I appreciate link to any similar data structure.


share|cite|improve this question
up vote 0 down vote accepted

There is an answer on same question I posted on Stack Overflow.

Structure I was looking for is series-parallel partial order.

share|cite|improve this answer
Great! Thank you. I removed my comments to your question, as they were no longer relevant. – t.b. Nov 8 '11 at 13:11
It is not so easy to answer your own question with a short comment, it is automatically set as a comment to question :-) – Ante Nov 8 '11 at 13:12

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.