A polynomial algorithm for the MIN CUT linear arrangement of trees
- 1 November 1983
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 274-281
- https://doi.org/10.1109/sfcs.1983.2
Abstract
An algorithm is presented which finds a min-cut linear arrangement of a tree in O(nlogn) 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 15 references indexed in Scilit:
- Upper and Lower Bounds on the Complexity of the Min-Cut Linear Arrangement Problem on TreesSIAM Journal on Algebraic Discrete Methods, 1982
- Black-white pebbles and graph separationActa Informatica, 1981
- The complexity of searching a graphPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1981
- A dense gate matrix layout method for MOS VLSIIEEE Transactions on Electron Devices, 1980
- The space complexity of pebble games on treesInformation Processing Letters, 1980
- Optimal tree layout (Preliminary Version)Published by Association for Computing Machinery (ACM) ,1980
- Complexity Results for Bandwidth MinimizationSIAM Journal on Applied Mathematics, 1978
- Storage requirements for deterministic polynomialtime recognizable languagesJournal of Computer and System Sciences, 1976
- Automatic layout of low-cost quick-turnaround random-logic custom LSI devicesPublished by Association for Computing Machinery (ACM) ,1976
- Large Scale Integration of MOS Complex Logic: A Layout MethodIEEE Journal of Solid-State Circuits, 1967