<p>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.</p>

<p><a href="http://dx.doi.org/10.1007/11785293_34" rel="nofollow">http://dx.doi.org/10.1007/11785293_34</a></p>

<p><a href="http://dx.doi.org/10.1007/s00453-004-1082-5" rel="nofollow">http://dx.doi.org/10.1007/s00453-004-1082-5</a></p>

CC BY-SA 3.0
2011-08-22T10:47:07.663Z
Which is also called a 'skyline' apparently, according to one of those papers.  Thank you!
Beef
CC BY-SA 3.0
2011-08-20T22:51:26.033Z
2011-08-20T22:51:26.033Z
Alexander Tiskin
<p>Given a DAG, which can represent a partial order and has at least one topological sort.</p>

<p>For example the graph</p>

<pre><code>  &gt;B
 /  \
A    &gt;D
 \  /
  &gt;C
</code></pre>

<p>has two topological sorts "ABCD" and "ACBD".</p>

<p>My question is the following:
<em>Is there a name for the following total order sort of sets:</em></p>

<p><code>S:  ( {A} , {B,C} , {D} )</code></p>

<p>The inductive definition is similar to constructing a topological sort: </p>

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

<p>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.</p>

CC BY-SA 3.0
2011-08-16T18:09:32.210Z
I would just call it a greedy partition into antichains.
Andrew D. King
CC BY-SA 3.0
2011-08-16T18:43:07.193Z
alternately, you could call it a layered decomposition.
Suresh Venkat
<graph-theory><co.combinatorics><graph-algorithms><terminology>
What is a totally ordered sort of sets of a partial order called?
Beef
# What is a totally ordered sort of sets of a partial order called?

(Asked by: username_0 on 2011-08-16)

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: 

Put the all the graph minima (nodes with no input edges) in set #i S: ( {A} )
Remove the graph minima from the graph.  G:= G \ {A}
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.

**Tags:** graph-theory, co.combinatorics, graph-algorithms, terminology

> **Comments:**
> **username_1**: I would just call it a greedy partition into antichains.  
> **username_2**: alternately, you could call it a layered decomposition.  

---

## 1 answers

### Answer by username_3 on 2011-08-20. Score: 7 | Accepted answer

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>

> **Comments:**
> **username_0**: Which is also called a 'skyline' apparently, according to one of those papers.  Thank you!  

---

