Questions tagged [total-ordering]

The tag has no usage guidance.

4
votes
2answers
192 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, ...
7
votes
3answers
273 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 ...
5
votes
1answer
570 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. ...
6
votes
1answer
102 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
1answer
544 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 ...
1
vote
0answers
452 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 ...
13
votes
2answers
830 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 ...