All reports by Author Ivan Hu:

__
TR22-158
| 18th November 2022
__

Ivan Hu, Andrew Morgan, Dieter van Melkebeek#### Query Complexity of Inversion Minimization on Trees

Ivan Hu, Andrew Morgan, Dieter van Melkebeek

We consider the following computational problem: Given a rooted tree and a ranking of its leaves, what is the minimum number of inversions of the leaves that can be attained by ordering the tree? This variation of the well-known problem of counting inversions in arrays originated in mathematical psychology. It ... more >>>