# Questions tagged [partial-order]

The tag has no usage guidance.

54 questions
Filter by
Sorted by
Tagged with
22 views

### Efficient cardinality of set overlap relation

Assume that we have a set S of sets s. Every pair (s,s') in ...
101 views

### Methods for generating DAG with small Minimum Path Cover

On a directed acyclic graph $G=(V,E)$ the Minimum Path Cover (MPC) is the minimum number of paths that can be constructed on the DAG such that all vertices are covered by at least one path. If one was ...
24 views

### How do we know that $F^{n + 1}(\overrightarrow{\emptyset}) = F(F^n(\overrightarrow{\emptyset}))$?

I am currently studying the textbook Principles of Program Analysis by Flemming Nielson, Hanne R. Nielson, and Chris Hankin. Chapter 1.3 Data Flow Analysis says the following: The least solution. The ...
49 views

### Showing that $F$ is a monotone function

I am currently studying the textbook Principles of Program Analysis by Flemming Nielson, Hanne R. Nielson, and Chris Hankin. Chapter 1.3 Data Flow Analysis says the following: The least solution. The ...
25 views

### Components of subset partial order

Given a collection C of sets, there are a number of proposed algorithms for building the subset partial order, e.g. this paper. But is there any work on algorithms ...
53 views

### Finding connected components without building the graph first

What are good algorithms for finding connected components in a graph defined by a set of elements X, where each x in ...
35 views

### Why is there so little literature on partial order production?

Please excuse or improve the poor title of this question. My question is rather undirected, but I guess I am trying to find out if I might be missing a keyword for my problem. So there is plenty of ...
34 views

### Optimally find one of the total orderings for a poset based on some metadata about the elements

Given a finite, partially ordered set with the following two properties: Every element in the set has one of two types: "A" or "B". The type does not define the total ordering of the set and is ...
22 views

### What are all linear extensions of the product order of $\{1, \dots, M\} \times \{1, \dots, N\}$?

Note: I have read somewhere that finding all linear extensions of a partial order is in general a #P-complete problem (which apparently means difficult, and thus no closed form expression), but just ...
41 views

99 views

261 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$ ...
326 views

### Transform a DAG to fork-join format

I have a directed acyclic graph where the nodes are tasks and the edges are dependency relations between tasks - the edges go from the dependency to the task that depends on it. It is possible that ...
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 ...
102 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 ...
99 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 ...
226 views

### Longest chain of pair of points

For chaining two points A and B ...
534 views

155 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$...
156 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). ...
305 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 (...
43 views

### What is an efficient algorithm to see if a set of nodes ultimately depend on a certain node in a DAG?

Hopefully this question makes sense. Basically, given a DAG, a set of nodes A, and another node b, I'd like to know if node b is an ancestor of any of the nodes in A in that graph. This is my current ...
103 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. Describe an ...
470 views

### Path optimization in a DAG: maximizing number of least cost arcs

I've got the following problem. I've a graph $G=(V,E)$ as in the picture and I have to calculate the optimal path from $R$ to $S$. The optimal path has to maximize the number of least cost arcs. In ...
32 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, ...
47 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'...
391 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\...
5k views

1k views

### Prove that any directed cycle in the graph of a partial order must only involve one node

So I have the question: Prove that any directed cycle in the graph of a partial order must only involve one node. So I know that a partial order must be transitive, antisymmetric, and reflective, ...