×

zbMATH — the first resource for mathematics

A polynomial algorithm for the min-cut linear arrangement of trees. (English) Zbl 0633.68063
An algorithm is presented that finds a min-cut linear arrangement of a tree in O(n log n) time. An extension of the algorithm determines the number of pebbles needed to play the black and white pebble game on a tree.

MSC:
68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
05C05 Trees
91A05 2-person games
PDF BibTeX XML Cite
Full Text: DOI