×

zbMATH — the first resource for mathematics

A remark on max-cut problem with an application to digital-analogue convertors. (English) Zbl 0585.90085
Summary: We introduce notions of a distance-decreasing weight function and of an alternating cut. For a class of distance-decreasing weights we solve the max-cut problem. In general, we prove that alternating cuts are near optimal. This has application to digital-analogue convertors.

MSC:
90C35 Programming involving graphs or networks
90C90 Applications of mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Garey, M.R.; Johnson, D.S., Computers and intractibility: A guide to the theory of NP-completeness, (1979), Freeman San Francisco, CA
[2] Grötschel, M.; Pulleyblank, W.R., Weakly bipartite graphs and the MAX-cut problem, Operations research letters, 1, 23-27, (1981) · Zbl 0494.90078
[3] Hadlock, F.O., Finding a maximum cut of a planar graph in polynomial time, SIAM J. computing, 4, 221-225, (1975) · Zbl 0321.05120
[4] Hoeschele, D.F., Analog-to-digital/digital-to-analog conversion techniques, (1968), Wiley New York · Zbl 0187.14304
[5] J. Nešetřil and S. Poljak, On a combinatorial optimization theme (submitted to Aplikace Matematiky).
[6] J. Rohn and V. Dostál, Personal communication.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.