Questions tagged [partial-order]
The partial-order tag has no usage guidance.
16
questions with no upvoted or accepted answers
5
votes
0answers
281 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
25 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 ...
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
99 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
94 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
22 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
130 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
327 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
34 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
22 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
47 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
102 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 ...
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
227 views
