2
$\begingroup$

Given a DAG, which can represent a partial order and has at least one topological sort.

For example the graph

  >B
 /  \
A    >D
 \  /
  >C

has two topological sorts "ABCD" and "ACBD".

My question is the following: Is there a name for the following total order sort of sets:

S: ( {A} , {B,C} , {D} )

The inductive definition is similar to constructing a topological sort:

  1. Put the all the graph minima (nodes with no input edges) in set #i S: ( {A} )
  2. Remove the graph minima from the graph. G:= G \ {A}
  3. repeat step 1. with i := i+1 as long as the graph is non-empty

I find this in several computer science domains. For example method selection in CLOS (Common Lisp), a parallel scheduler of a DAG where nodes are tasks and edges dependencies, the list of all enabled sets in dataflow or petri-net model executions, etc. I haven't found a single nomenclature or even a reference for it though. It sounds simple and pervasive enough to merit one.

$\endgroup$
2
  • 7
    $\begingroup$ I would just call it a greedy partition into antichains. $\endgroup$ Aug 16 '11 at 18:09
  • $\begingroup$ alternately, you could call it a layered decomposition. $\endgroup$ Aug 16 '11 at 18:43
7
$\begingroup$

In the context of geometric dominance orders, the standard term is "layers of maxima" (in your case, minima). Obviously, the same term can be used for any partial order.

http://dx.doi.org/10.1007/11785293_34

http://dx.doi.org/10.1007/s00453-004-1082-5

$\endgroup$
1
  • $\begingroup$ Which is also called a 'skyline' apparently, according to one of those papers. Thank you! $\endgroup$
    – Beef
    Aug 22 '11 at 10:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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