# Questions tagged [partial-order]

The tag has no usage guidance.

44 questions
Filter by
Sorted by
Tagged with
3answers
5k views

1answer
327 views

0answers
246 views

### How to convert a dependency graph to series-parallel representation?

I'm given a finite partial order, in the form of a dependency graph between items, and I'd like to have it in series-parallel form (Wikipedia). So formally, given a finite partial order $\le$ on a ...
1answer
150 views

### Disproving well-quasi-order by providing an infinite anti-chain

I am currently studying the theory behind Well-Quasi-Orders. However I am having some issues in understanding how an infinite anti-chain can be produced to disprove the claim that a partial order $P$...
1answer
359 views

### What is the name of the property where $f(A) \supseteq f(B)$ when $A\supseteq B$?

Suppose I have a function $f$ on sets. What is the property of $f$ called when, for all sets $x$, $y$: $f(x)$ is a superset of $f(y)$ when $x$ is a superset of $y$ i.e. \forall x,y : x\...
2answers
255 views

### Given many partial orders, check them for consistency and report any that are not consistent

Inputs. I am given a finite set $S$ of symbols. I know there should exist some total order $<$ on $S$, but I'm not given this ordering and it could be anything. I am also given a collection of ...
1answer
24 views

### Algorithm to establish a global ranking given individual rankings

I am looking for an algorithm(s) that can compute a global ranking (partial ordering) given individual rankings, in some kind of principled manner. I want to establish a partial-ordering of some ...
1answer
128 views

### Generalized sorting algorithm on partially ordered set generated by a relation

Assume we have a finite set $X$ of elements and any relation $\preceq$ on $X$. Such a relation may or may not generate a reflexive transitive anti-symmetric relation $\leq$ on $X$ (a partial order). ...
1answer
250 views

### Is < binary relation a strict partial order on IEEE doubles?

To me it looks that it is: irreflexivity: NaN < NaN == false transitivity: if a < b and b < c then a < c (the antecedent is never true for NaNs) asymmetry: if a < b then not b < a (...
1answer
24 views

### Computing minimum partition of poset of $N$ intervals into chains in $o(N^{2.5})$ time?

Consider a set $P$ of $N$ intervals $\{I_i = (l_i, r_i)\}$ partially ordered according the standard interval order: $I_i < I_j$ iff $r_i \le l_j$. I want to find a minimum cardinality partition of ...
1answer
68 views

### Efficiently determine relative ordering between two elements in a PO-set

What algorithms/heuristics exist for efficiently determining the relative order between two elements in a partially ordered set? In my case, the PO-set is stored as a directed acyclic graph where an ...
0answers
70 views

### Measuring the Union of Products of Intervals

Verbose Motivation for this Question Inspired by this paper about how the problem of counting unlabelled subtrees that are unique up to isomorphism is #P-complete, I was thinking about the problem ...
0answers
85 views

1answer
44 views

### Checking if the mimimum is unique

We have a finite poset and its subset $S$. We can enumerate elements of $S$ using an iterator. I need to check if there are more than one minimal elements of $S$ (regarding the above poset). The ...
2answers
98 views

### How to solve this partial order reduction in $O(n^2)$?

There are two orderings of numbers from the same set. Number $a$ is "immediately before" $b$ iff $a$ appears before $b$ in both sequences and there is no other number that appears between them in both ...
1answer
41 views

### Is this algorithm for partial ordering of sets complete and sound?

I need to build a partial order tree of sets for analysis. Where the order is defined as A <= B <=> for all x in A, y in B, x <= y. I realized that if ...
1answer
232 views

### The sorting problem for partially ordered sets

I have two questions about sorting for posets, one easy and one hard: Easy: Suppose we have a set of objects and a partial order. Given any two objects such that $a \leq b$, we want to delete $b$ ...
1answer
85 views

0answers
21 views

### Algorithm for partial order width [duplicate]

I want to compute the partial order width i.e. the size of the maximum antichain in a given partial order. By Dilworth's Theorem this is the same as minimal chains required to decompose the graph, ...
0answers
44 views

### Complete Partial Order of Partial Functions with Different Outputs

Since a partial function can be seen as a set of tuples, there is a trivial CPO defined by the subset relation on partial functions of the same (co-)domain. However, this is not really useful. What I'...
1answer
91 views

### What kind of order is binary tree ancestry?

Let isAncestor be a relation on binary tree nodes such that isAncestor x y means y can be ...
1answer
146 views

### trouble with bijection definition [closed]

I have a bijection problem that I cannot get my head around. It goes like this: let f: A -> B and g: B -> C be functions such that g o f is a bijection. Prove that f must be one-to-one and that g ...
2answers
48 views

### Efficiently computing minimal elements over partially ordered sets

I have a list of sets that I would like to sort into a partial order based on the subset relation. In fact, I do not require the complete ordering, only the minimal elements. If I am not mistaken, ...
0answers
27 views

### Retroactively ordering actors' concurrent activity on disjoint sections of a data-structure

Hi! I'm new here, a terrible computer-scientist, and have no idea what I'm doing; I'm more expecting / hoping for links to research on algorithms or data-structures that contribute to problems like ...
0answers
216 views

### Longest chain of pair of points

For chaining two points A and B ...
1answer
95 views

### Selection algorithm variant for an array

Have a problem that's a variant of the linear time selection algorithm of a randomized array that I'm struggling with. Let $A = A[1], ..., A[n]$ be an array of $n \ge 4$ distinct keys. ...
1answer
475 views

### How to prove substring is a partial order

u is defined to be a substring of a string v if v = xuy for some string x and y. Either or both possibly empty. How to you prove that a substring relation on any set of strings is a partial order?