Finding good approximate vertex and edge partitions is NP-hard
- 1 May 1992
- journal article
- Published by Elsevier in Information Processing Letters
- Vol. 42 (3) , 153-159
- https://doi.org/10.1016/0020-0190(92)90140-q
Abstract
No abstract availableKeywords
This publication has 7 references indexed in Scilit:
- Some simplified NP-complete graph problemsPublished by Elsevier ,2002
- Partitioning Planar GraphsSIAM Journal on Computing, 1992
- A Heuristic Algorithm for Small Separators in Arbitrary GraphsSIAM Journal on Computing, 1990
- An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithmsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- Graph bisection algorithms with good average case behaviorCombinatorica, 1987
- A Separator Theorem for Planar GraphsSIAM Journal on Applied Mathematics, 1979
- An Efficient Heuristic Procedure for Partitioning GraphsBell System Technical Journal, 1970