Questions tagged [partial-order]

The tag has no usage guidance.

14 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
5
votes
0answers
259 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 ...
3
votes
0answers
71 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 ...
3
votes
0answers
90 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, \...
3
votes
0answers
91 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 ...
2
votes
0answers
20 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$ ...
2
votes
0answers
127 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) ...
2
votes
0answers
271 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 ...
1
vote
0answers
33 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 ...
1
vote
0answers
18 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 ...
1
vote
0answers
18 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 ...
1
vote
0answers
32 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 $...
1
vote
0answers
44 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'...
0
votes
0answers
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 ...
0
votes
0answers
224 views

Longest chain of pair of points

For chaining two points A and B ...