Share Your Experience: Take the 2024 Developer Survey

# Questions tagged [partial-order]

The tag has no usage guidance.

69 questions
Filter by
Sorted by
Tagged with
19 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 ...
1 vote
88 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 ...
• 113
25 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. ...
• 532
49 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
103 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
22 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
30 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 ...
1 vote
58 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?
1 vote
93 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
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
393 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
65 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,800
55 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
36 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 ...
1 vote
68 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,192
1 vote
72 views

### Efficient cardinality of set overlap relation

Assume that we have a set S of sets s. Every pair (s,s') in ...
1 vote
38 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 ...
• 217
1 vote
67 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 ...
• 217
149 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
44 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 ...
105 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 ...
1 vote
64 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 ...
1 vote
46 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
36 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 ...
47 views

• 131
1 vote
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
85 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
140 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 ...
82 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$ ...
• 13.6k
361 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
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 ...
• 493
139 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) ...
• 493
1 vote