Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > COUNTING INVERSIONS:
Reports tagged with counting inversions:
TR22-158 | 18th November 2022
Ivan Hu, Andrew Morgan, Dieter van Melkebeek

Query Complexity of Inversion Minimization on Trees

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 >>>




ISSN 1433-8092 | Imprint