A polynomial algorithm for the min-cut linear arrangement of trees
- 1 October 1985
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 32 (4) , 950-988
- https://doi.org/10.1145/4221.4228
Abstract
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.Keywords
This publication has 10 references indexed in Scilit:
- Minimizing width in linear layoutsPublished by Springer Nature ,2005
- On optimal linear arrangements of treesComputers & Mathematics with Applications, 1984
- Upper and Lower Bounds on the Complexity of the Min-Cut Linear Arrangement Problem on TreesSIAM Journal on Algebraic Discrete Methods, 1982
- A comparison of two variations of a pebble game on graphsTheoretical Computer Science, 1981
- On the area of binary tree layoutsInformation Processing Letters, 1980
- The Pebbling Problem is Complete in Polynomial SpaceSIAM Journal on Computing, 1980
- The space complexity of pebble games on treesInformation Processing Letters, 1980
- A Minimum Linear Arrangement Algorithm for Undirected TreesSIAM Journal on Computing, 1979
- Complexity Results for Bandwidth MinimizationSIAM Journal on Applied Mathematics, 1978
- Storage requirements for deterministic polynomialtime recognizable languagesJournal of Computer and System Sciences, 1976