23.6k citations
- National Institute for Theoretical PhysicsZA225 papers
- Peking UniversityCN163 papers
- Centre National de la Recherche ScientifiqueFR143 papers
- University of the WitwatersrandZA139 papers
- University of Cape TownZA132 papers
- Chinese Academy of SciencesCN115 papers
- Institut National de Physique Nucléaire et de Physique des ParticulesFR113 papers
- University of CambridgeGB110 papers
- State Key Laboratory of Nuclear Physics and Technology109 papers
- University of ManchesterGB108 papers
- University of OsloNO105 papers
- Kyoto UniversityJP104 papers
6 papers · 2 filters
Reductions of Binary Trees and Lattice Paths induced by the Register Function
Benjamin Hackl, Clemens Heuberger, Helmut Prodinger
The register function (or Horton-Strahler number) of a binary tree is a well-known combinatorial parameter. We study a reduction procedure for binary trees which offers a new inter…
Dual-Pivot Quicksort: Optimality, Analysis and Zeros of Associated Lattice Paths
Martin Aumüller, Martin Dietzfelbinger, Clemens Heuberger +2
We present an average case analysis of a variant of dual-pivot quicksort. We show that the used algorithmic partitioning strategy is optimal, i.e., it minimizes the expected number…
Dominating and Irredundant Broadcasts in Graphs
Kieka Mynhardt, Riana Roux
A broadcast on a nontrivial connected graph G=(V,E) is a function f from V(G) to {0,1,...,diam(G)} such that f(v) does not exceed the eccentricity of v. The cost of f is the sum of…
Additive functionals of -ary increasing trees
Dimbinaina Ralaivaosaona, Stephan Wagner
A tree functional is called additive if it satisfies a recursion of the form , where are the branches of the tree and …
-Quasiadditive Functions
Sara Kropf, Stephan Wagner
In this paper, we introduce the notion of -quasiadditivity of arithmetic functions, as well as the related concept of -quasimultiplicativity, which generalises strong -add…
Counting Zeros in Random Walks on the Integers and Analysis of Optimal Dual-Pivot Quicksort
Martin Aumüller, Martin Dietzfelbinger, Clemens Heuberger +2
We present an average case analysis of two variants of dual-pivot quicksort, one with a non-algorithmic comparison-optimal partitioning strategy, the other with a closely related a…