HackerPapers

arXiv:1606.06389cs.DS

A Linear Potential Function for Pairing Heaps

John Iacono, Mark Yagnatinsky

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

Abstract

We present the first potential function for pairing heaps with linear range. This implies that the runtime of a short sequence of operations is faster than previously known. It is also simpler than the only other potential function known to give amortized constant amortized time for insertion.

arXiv comments
Journal reference
DOI
Subjects
cs.DSData Structures and Algorithms

On Hacker News

Linked by 1 identifiable commenter in 1 comment across 1 thread, from May 2020 to May 2020.

Comments linking this paper, per year.

Discussed in comments1 thread

  1. Have you ever asked yourself “how did research get done before LateX?” 1 comment

    • Let's take an example: https://arxiv.org/pdf/1606.06389.pdf A cursory inspection seems to indicate ctrl-F is fine here? Or am I missing something?

      marvyView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.