Jump to content

Talk:Order-maintenance problem

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Path labels

[edit]

Two aspects of the way path labels are currently presented are unclear to me:

  1. In the current set-up, several paths are indistinguishable because they only differ by leading zeros. For example, nodes X and 14 in the article's example get the labels (0221)_3 and (221)_3, respectively, both of which equal 25. I assume that the final 1 should be added _in front_ of the branch labels. In the mentioned example, the labels would then be (1022)_3 and (122)_3, which are distinct.
  2. Why use a ternary system? The algorithms explained on the page do not seem to care about whether the right-branch label (currently 2) is or is not distinguishable from the leaf label (1).

Matzu (talk) 11:56, 1 October 2015 (UTC)[reply]

Indeed. Also, there are no citations in that section. 76.99.148.129 (talk) 20:33, 7 October 2017 (UTC)[reply]