Questions tagged [partial-order]
The partial-order tag has no usage guidance.
66
questions
0
votes
0
answers
40
views
Creating a partial order from a total order with a concurrency oracle
I have a total order represented as a Hasse diagram (basically a linked list of ordered elements) and a concurrency oracle.
The concurrency orracle is a function, that tells me which pairs of elements ...
- 131
3
votes
0
answers
44
views
Map-like data structure with subsets as keys
I am looking for a map-like data structure with the following properties:
it uses subsets of some set S as keys. The size of S is potentially unbounded, but does not change during the runtime
the ...
- 131
2
votes
0
answers
20
views
Algorithm for finding an embedding of a cover diagram
I am making some notes on order theory for my own self study (and certainly anyone else that wants to read them).
I'm impressed with what mermaid can do out of the ...
- 125
1
vote
1
answer
26
views
Terminology for number of topological sorts
Is there a standard terminology for the topological sort count over a partial order? I went with magnitude of a poset rather than dimension as this is too close to linear algebra terminology. I wonder ...
- 428
1
vote
1
answer
43
views
relation based on a given partial order - does it have a name?
Let $P$ be a partial order on $X.$ Does the relation $E(P)=$ { $(x,y)\in (X\times X)\setminus P:P$ $\cup$ { $(x,y)$ } is a partial order on $X$ } have a name? If not, what's a good thing to call it?
- 123
0
votes
1
answer
47
views
Is there any Algorithm to check a vertex\node's partial order in terms of other vertices\nodes for a given graph?
For the given figure, let's consider vertex v3. For v3, v0 has a higher partial order,v1 & v2 has the same partial order, and v4 & v5 have lower order than v3, e.g., higher: {v0}, same: {v1,v2}...
- 1
0
votes
0
answers
34
views
Iterative algorithm for assembly index? [duplicate]
DOI: 10.3390/e24070884 provides pseudocode for computing the assembly index of an object. It is written as recursive algorithm, which might be fine. But I would like to implement an iterative version ...
- 125
3
votes
1
answer
195
views
Lamport Timestamps and Causality
I'm having trouble understanding lamport timestamps in practice and how they guarantee causal ordering.
Definitions
Lamport defines the "happens before" relationship in his paper. He states ...
- 133
2
votes
0
answers
63
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 ...
- 3,758
0
votes
1
answer
32
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 ...
- 131
1
vote
0
answers
32
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 ...
- 123
1
vote
0
answers
60
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 ...
- 3,127
1
vote
1
answer
45
views
Efficient cardinality of set overlap relation
Assume that we have a set S of sets s.
Every pair (s,s') in ...
- 177
1
vote
1
answer
32
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 ...
- 201
1
vote
1
answer
61
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 ...
- 201
0
votes
0
answers
121
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 ...
- 92
3
votes
0
answers
38
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 ...
- 177
0
votes
2
answers
77
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 ...
- 177
1
vote
2
answers
59
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 ...
- 177
1
vote
0
answers
41
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 ...
- 11
1
vote
0
answers
29
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 ...
0
votes
2
answers
44
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 \...
- 103
0
votes
2
answers
204
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, ...
- 177
3
votes
1
answer
62
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 ...
- 227
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 ...
- 123
2
votes
0
answers
30
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$ ...
- 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 ...
- 375
1
vote
1
answer
103
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 ...
3
votes
0
answers
123
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, \...
- 131
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 ...
- 113
5
votes
1
answer
49
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 ...
- 213
3
votes
0
answers
119
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 ...
- 181
2
votes
1
answer
73
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$ ...
- 12.5k
5
votes
0
answers
337
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 ...
1
vote
1
answer
46
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 ...
- 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) ...
- 413
1
vote
0
answers
40
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 $...
- 386
1
vote
1
answer
288
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$ ...
- 700
3
votes
0
answers
471
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 ...
- 31
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 ...
- 101
3
votes
1
answer
131
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 ...
- 690
1
vote
2
answers
103
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 ...
- 121
0
votes
0
answers
240
views
7
votes
1
answer
744
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
$...
- 431
5
votes
2
answers
82
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 $...
- 345
4
votes
1
answer
170
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$...
- 474
3
votes
1
answer
276
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). ...
- 133
4
votes
1
answer
394
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 (...
- 143
2
votes
1
answer
56
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 ...
- 161
0
votes
1
answer
131
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 ...
- 139