Questions tagged [total-ordering]
The total-ordering tag has no usage guidance.
7
questions
13
votes
2
answers
1k
views
What is a good special-case sorting algorithm?
I have a dataset which is a number of objects arranged in a 2-D grid. I know I have a strict ordering, increasing as you go left-to-right within each row, and increasing as top-to-bottom within each ...
7
votes
3
answers
311
views
Total orders which are the transitive closure of a set in P
I am wondering if there is an example of the following form. It seems highly plausible that there should be but I am struggling to come up with one.
Consider $T \subseteq \mathbb{N}^2$, a set ...
6
votes
1
answer
110
views
Algorithm for ordering a list under a similarity function?
While thinking about the best way to display confusion matrices, and I came up with the following problem:
You have a set of objects $A$, and a similarity function $s: A,A \rightarrow \mathbb{R}$ ...
5
votes
1
answer
987
views
Efficient representation of set of partial order
I guess that notions I describe are already well known, may be by combinatorician, but I do not know their name or any book/article about them. So if you have a link/title I would love to read it.
...
5
votes
1
answer
592
views
Dynamic Tree Marked Ancestor Queries
Assuming a rooted tree $T$ with vertices $V$, I am maintaining subsets of $V$, for example $M \subseteq V$ whose vertices are associated with particular labels or values. $V$ is dynamic in that it ...
4
votes
2
answers
269
views
Ordered-file maintenance
I am studying the Advanced Data Structures material and I'd like to implement the Ordered-file maintenance data structure. I have few questions in order to start.
The papers rely on a static view, ...
1
vote
0
answers
474
views
Well Defined Ordering Relations in Object Oriented Type Systems [closed]
In any Object-Oriented type system the type relation of two objects A and B can be characterized in exactly one of the following ways:
A has the same type as B
A is a subtype of B
B is a subtype of A
...