Questions tagged [total-ordering]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...
Zachary Vance's user avatar
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 ...
DRMacIver's user avatar
  • 434
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}$ ...
Max Libbrecht's user avatar
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. ...
Arthur MILCHIOR's user avatar
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 ...
0__'s user avatar
  • 173
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, ...
senseiwa's user avatar
  • 185
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 ...
Johannes Rudolph's user avatar