Approximation and intractability results for the maximum cut problem and its variants
- 1 January 1991
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 40 (1), 110-113
- https://doi.org/10.1109/12.67327
Abstract
No abstract availableThis publication has 12 references indexed in Scilit:
- How to make a graph bipartiteJournal of Combinatorial Theory, Series B, 1988
- A remark on max-cut problem with an application to digital-analogue convertorsOperations Research Letters, 1986
- A fast parallel algorithm for the maximal independent set problemJournal of the ACM, 1985
- A graph-theoretic via minimization algorithm for two-layer printed circuit boardsIEEE Transactions on Circuits and Systems, 1983
- An approximation algorithm for the hamiltonian walk problem on maximal planar graphsDiscrete Applied Mathematics, 1983
- How well can a graph be n-colored?Discrete Mathematics, 1981
- Complexity of Partial SatisfactionJournal of the ACM, 1981
- P-Complete Approximation ProblemsJournal of the ACM, 1976
- Finding a Maximum Cut of a Planar Graph in Polynomial TimeSIAM Journal on Computing, 1975
- A Theorem on GraphsAnnals of Mathematics, 1931