# Tagged Questions

The tag has no usage guidance.

36 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). ...
70 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 (...
24 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 ...
47 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. ...
66 views

271 views

### Prove that any directed cycle in the graph of a partial order must only involve one node

So I have the question: Prove that any directed cycle in the graph of a partial order must only involve one node. So I know that a partial order must be transitive, antisymmetric, and reflective, ...
174 views

### How to prove substring is a partial order

u is defined to be a substring of a string v if v = xuy for some string x and y. Either or both possibly empty. How to you prove that a substring relation on any set of strings is a partial order?
112 views

### trouble with bijection definition [closed]

I have a bijection problem that I cannot get my head around. It goes like this: let f: A -> B and g: B -> C be functions such that g o f is a bijection. Prove that f must be one-to-one and that g ...
Imagine I have an ordering on a bunch of elements like so: Where an arrow $X \leftarrow Y$ means $X < Y$. It is also transitive: $\left(X < Y\right) \wedge \left(Y < Z\right) \implies \... 1answer 77 views ### Extracting the set of chains from a partial order Given a partial ordered set (poset)$S$, is there a known procedure or algorithm to find the set of chains (i.e. subsets of$S$where every two elements are comparable)? Note: I am asking here ... 1answer 138 views ### Is there an efficient method to store large DAGs? I have a DAG representing strict partial order where each node is an assignment of variables$V$to their values$v$. Each arc$(u,w)$represents a change in one variable value such that$u\succ w$. ... 2answers 144 views ### Are these two relations on integers partial orders? Are the following relations$R_1$and$R_2$defined on the set$\mathbb{Z}$of integers partial orders? (A partial order is reflexive, antisymmetric and transitive.)$aR_1b$if and only if$a =...
Inputs. I am given a finite set $S$ of symbols. I know there should exist some total order $<$ on $S$, but I'm not given this ordering and it could be anything. I am also given a collection of ...