An improved algorithm for the traveler’s problem

Alok Aggarwal, Takeshi Tokuyama

Research output: Contribution to journalArticlepeer-review


In a paper in Journal of Algorithms13 (1992), 148-160, Hirschberg and Larmore introduced the traveler’s problem as a subroutine for constructing the B-tree. They gave an O(n5/3 log1/3n) time algorithm for solving the traveler’s problem of size n. In this paper, we improve their time bound to O(n3/2 log n). As a consequence, we build a B-tree in O(n3/2 log2n) time as compared to the O(n5/3 log4/3n) time algorithm of Hirschberg and Larmore.

Original languageEnglish
Pages (from-to)318-330
Number of pages13
JournalJournal of Algorithms
Issue number2
Publication statusPublished - 1995 Sept
Externally publishedYes

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics


Dive into the research topics of 'An improved algorithm for the traveler’s problem'. Together they form a unique fingerprint.

Cite this