Polynomial time algorithms for the MIN CUT problem on degree restricted trees
- 1 November 1982
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 262-271
- https://doi.org/10.1109/sfcs.1982.85
Abstract
Polynomial algorithms are described that solve the MIN CUT LINEAR ARRANGEMENT problem on degree restricted trees. For example, the cutwidth or folding number of an arbitrary degree d tree can be found in O(n(logn)d-2) steps. This also yields an algorithm for determining the black/white pebble demand of degree three trees. A forbidden subgraph characterization is given for degree three trees having cutwidth k. This yields an interesting corollary: for degree three trees, cutwidth is identical to search number.Keywords
This publication has 13 references indexed in Scilit:
- Some simplified NP-complete graph problemsPublished by Elsevier ,2002
- Minimal numberings of the vertices of trees — Approximate approachPublished by Springer Nature ,1987
- Upper and Lower Bounds on the Complexity of the Min-Cut Linear Arrangement Problem on TreesSIAM Journal on Algebraic Discrete Methods, 1982
- Advances in pebblingPublished by Springer Nature ,1982
- A comparison of two variations of a pebble game on graphsTheoretical Computer Science, 1981
- The complexity of searching a graphPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1981
- The space complexity of pebble games on treesInformation Processing Letters, 1980
- A Minimum Linear Arrangement Algorithm for Undirected TreesSIAM Journal on Computing, 1979
- Automatic layout of low-cost quick-turnaround random-logic custom LSI devicesPublished by Association for Computing Machinery (ACM) ,1976
- On arithmetic expressions and treesCommunications of the ACM, 1969