Min cut is NP-complete for edge weighted trees
- 30 June 1988
- journal article
- Published by Elsevier in Theoretical Computer Science
- Vol. 58 (1-3) , 209-229
- https://doi.org/10.1016/0304-3975(88)90028-x
Abstract
No abstract availableKeywords
This publication has 18 references indexed in Scilit:
- Recontamination does not help to search a graphJournal of the ACM, 1993
- The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-CompleteSIAM Journal on Algebraic Discrete Methods, 1986
- Searching and pebblingTheoretical Computer Science, 1986
- A polynomial algorithm for the min-cut linear arrangement of treesJournal of the ACM, 1985
- Polynomial Time Algorithms for the MIN CUT Problem on Degree Restricted TreesSIAM Journal on Computing, 1985
- A tight bound for black and white pebbles on the pyramidJournal of the ACM, 1985
- A comparison of two variations of a pebble game on graphsTheoretical Computer Science, 1981
- The Pebbling Problem is Complete in Polynomial SpaceSIAM Journal on Computing, 1980
- On Time Versus SpaceJournal of the ACM, 1977
- Storage requirements for deterministic polynomialtime recognizable languagesJournal of Computer and System Sciences, 1976