Questions tagged [partial-order]
The partial-order tag has no summary.
70 questions
1
vote
1
answer
71
views
Efficient count of upper-right region population
Suppose you're given a population of $n$ points $(x_i, y_i)$ in the unit square $[0, 1]^2$. For a given new sample $(x, y)$, you must find the number of points in the original population satisfying $x\...
- 11
1
vote
2
answers
82
views
Algorithms for unordered vertices of the convex hull
For the sake of this question a "non-ordering" "set of vertices of convex hull" algorithm produces the collection of all points on the convex hull of its input without producing ...
- 225
1
vote
1
answer
165
views
What happens when two different nodes have the same Lamport clock ID
With Lamport clocks, each node keeps its own counter. Before sending a message, a node increments its counter by one: LC(A)=LC(A)+1, and sends ...
- 123
2
votes
1
answer
63
views
Ranked voting method where unranked candidates on a preference list aren't taken to be the least preferred?
Say there are 5 candidates, A, B, C, D, and E. An election is held using a ranked voting method. That is to say, each voter submits a preference list (the order in which they prefer candidates). E.g. ...
- 652
0
votes
0
answers
109
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
196
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
32
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 ...
- 127
1
vote
1
answer
47
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 ...
- 622
1
vote
1
answer
100
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
1
vote
1
answer
143
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}...
- 11
0
votes
0
answers
35
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 ...
- 127
3
votes
1
answer
593
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
3
votes
0
answers
117
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,810
1
vote
1
answer
95
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 ...
- 141
1
vote
0
answers
63
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