Questions tagged [partial-order]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
0 answers
54 views

Data structure for finding greatest lower bound with respect to a partial order

I have some partial order $\preceq \,\,\subset A \times A$, I'd like a data structure with the following operations: $Insert(a, x, T)$: add $(a, x)$ to the collection $T$ $Find(x, T)$: find the ...
user avatar
  • 3,728
0 votes
1 answer
17 views

Define a directed edge in a DAG using partial ordering

I am trying to describe a novel type of DAG's construction algorithm. The directed edges of the graph corresponds to a partial ordering: i.e. any directed edge $e$ spanning from $f$ to $t$ also ...
user avatar
  • 111
1 vote
0 answers
31 views

How to compute all inequivalent (under Aut(P)) nonnegative integer weight assignments (with fixed sum) to the vertices of a finite poset P?

Let $P$ be a poset on $n$ points, $\text{Aut}(P)$ its automorphism group, and $a_1,a_2,\dots,a_k$ the lengths of the orbits under $\text{Aut}(P)$. Goal: An algorithm to generate a member from each ...
user avatar
1 vote
0 answers
49 views

Finding all minimal upper bounds in a partially ordered set

I have a partially ordered set of numbers, represented as a vector<set<int>> (e.g. if $2 \preceq 4$ in this order, then ...
user avatar
1 vote
1 answer
31 views

Efficient cardinality of set overlap relation

Assume that we have a set S of sets s. Every pair (s,s') in ...
user avatar
1 vote
1 answer
29 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 ...
user avatar
1 vote
1 answer
56 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 ...
user avatar
0 votes
0 answers
117 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 ...
user avatar
3 votes
0 answers
36 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 ...
user avatar
0 votes
2 answers
71 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 ...
user avatar
1 vote
2 answers
52 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 ...
user avatar
1 vote
0 answers
37 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 ...
user avatar
  • 11
1 vote
0 answers
27 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 ...
user avatar
0 votes
2 answers
43 views

Scheduling: Existence of specific total order

A question arising from a scheduling problem: I have a finite set $X$ with elements $x_i$ and some preorder $\leq$. I have pairs $p_j$ of $x_i$ (i.e. $p_j$ = $(x_k, x_l)$) with the property that $x_k \...
user avatar
  • 103
0 votes
2 answers
147 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, ...
user avatar
3 votes
1 answer
54 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 ...
user avatar
1 vote
0 answers
20 views

Construct neighbourhood relation graph for n sequences

Given $n$ sequences with length $m$, $s_i=\langle c_1^ic_2^i\dots c_m^i\rangle, i = 1,\dots, n$, where $c^i_j\in D$ is a partial ordered set and the partial order relation $\sqsubseteq$ on $D$ answers ...
user avatar
  • 123
2 votes
0 answers
28 views

Poset data structure to find least element, greater or equal to given

Let $A$ be a finite set, and $S \subset \mathcal{P}(A)$. Is there a data structure for $S$ that would allow to quickly retrieve an element $q \in S $, given a key $p \in \mathcal{P}(A)$, such that $q$ ...
user avatar
  • 145
3 votes
0 answers
76 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 ...
user avatar
1 vote
1 answer
96 views

Does every Partially Ordered relation and its dual have the same number of topological orderings?

Given the Hasse Diagram of a Partially Ordered Relation, is it the case that both the POSET itself and its dual POSET have the same number of topological orderings? I have tried a few examples, and ...
user avatar
3 votes
0 answers
117 views

Matching relative order in subsequence of fixed length

I encountered this problem from game development which I will formulate in a more formal way: Given a sequence $A = a_1, a_2, \dots, a_m$ and a permutation of $\{1, \dots, n\}$, $B = b_1, b_2, \...
user avatar
1 vote
1 answer
44 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 ...
user avatar
  • 113
4 votes
1 answer
37 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 ...
user avatar
3 votes
0 answers
106 views

effective, efficient algorithms on antichains

In a partially ordered set L, an antichain is a subset A of L such that no two elements of A are comparable. Antichains are commonly used to represent upward-closed subsets of L, that is, sets S such ...
user avatar
2 votes
1 answer
60 views

Counting number of permutations respecting partial order

Suppose that we have an array $A$ of $n$ elements with some partial order known, e.g. for example as a $n\times n$ matrix containing $c_{ij} \in \{-1, 0, 1\}$ where $0$ represents unknown and $-1, 1$ ...
user avatar
  • 12.3k
5 votes
0 answers
311 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 ...
user avatar
1 vote
1 answer
45 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 ...
user avatar
  • 413
2 votes
0 answers
138 views

Two related partial order relations

We will consider a set whose elements I call "precedences". Precedences are related by two relations: "is subclass of" and "higher than", which are specified by some pairs (given on algorithm input) ...
user avatar
  • 413
1 vote
0 answers
35 views

Minimize number of comparisons to discover a strict total order

$S$ is a set of $n$ elements with some unknown strict total order. The goal is to discover the greatest $k$ elements, where each step consists of comparing $m\ge 2$ elements at once (so if we compare $...
user avatar
1 vote
1 answer
280 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$ ...
user avatar
2 votes
0 answers
411 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 ...
user avatar
  • 21
0 votes
0 answers
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 ...
user avatar
3 votes
1 answer
119 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 ...
user avatar
1 vote
2 answers
102 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 ...
user avatar
  • 121
0 votes
0 answers
232 views

Longest chain of pair of points

For chaining two points A and B ...
user avatar
7 votes
1 answer
643 views

Finding longest chain in poset in subquadratic time

Let $(A,\leq)$ be some finite poset. For $a,a' \in A$ we can determine in constant time whether or not $a \leq a'$. The height of an $A$ is by definition the greatest $n$ such that there are elements $...
user avatar
5 votes
2 answers
79 views

How to efficiently determine whether a relation is total?

I have a set $S$ of pairs $(x_1,x_2)$ with $x_1,x_2 \in X$ for some set $X$. I want to know whether this defines a total relation on $X$. In other words, whether: If $(a,b)$ in $S$ and $(b,c)$ in $...
user avatar
4 votes
1 answer
167 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$...
user avatar
  • 484
3 votes
1 answer
246 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). ...
user avatar
4 votes
1 answer
342 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 (...
user avatar
  • 143
2 votes
1 answer
52 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 ...
user avatar
  • 161
0 votes
1 answer
117 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 ...
user avatar
1 vote
1 answer
89 views

Pairs distance to ordering?

Thanks to anon for contributing this wording: Every permutation $\pi:\{1,\cdots,n\}\to\{1,\cdots,n\}$ induces an $n\times n$ array $A(\pi)$ of the absolute differences, whose $ij$ entry is $|\pi(i)-\...
user avatar
  • 209
1 vote
2 answers
488 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 ...
user avatar
1 vote
0 answers
34 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, ...
user avatar
1 vote
0 answers
52 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'...
user avatar
  • 610
3 votes
1 answer
393 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\...
user avatar
  • 173
2 votes
1 answer
160 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 ...
user avatar
2 votes
2 answers
559 views

Search in a partial ordering defined by tuples of numbers

This is a graph theory and partial ordering problem. Consider a set of triples {(di,ai,ci)}i=1...N, which specify edges between two nodes A and B, d denotes a departure time, a an arrival time and c a ...
user avatar
  • 202
5 votes
1 answer
363 views

What does Tarski's Fixed-Point theorem give us that that Y-Combinator does't

I'm taking a graduate course on the theory of functional programming, based on Paul Taylor's "Practical Foundations of Mathematics." I understand the statement of Tarski's theorem about how for any $\...
user avatar
  • 29.1k