All Library Books, journals and Electronic Records Telegrafenberg

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

  • 1
    ISSN: 1432-5217
    Keywords: Max-cut ; decision problem ; optimization problem ; polynomial transformation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Zusammenfassung Wir zeigen, daß folgende Probleme polynomial äquivalent sind: 1) Gegeben ein (gewichteter) GraphG, ein cutC vonG. Entscheide obC optimal ist oder nicht. 2) Gegeben ein (gewichteter) GraphG, ein cutC vonG. Entscheide, obC optimal ist oder nicht, und falls nicht, finde einen besseren cutC′. Eine Konsequenz hiervon ist, wie wir sehen werden, daß ein Optimalitätstest Orakel einen polynomialen Algorithmus zur approximativen Lösung von Max Cut Problemen liefert. Insbesondere folgt, daß das Erkennen von maximalen cuts in ungewichteten Graphen NP-schwer ist.
    Notes: Abstract We show that the following two problems are polynomially equivalent: 1) Given a (weighted) graphG, and a cutC ofG, decide whetherC is maximal or not. 2) Given a (weighted) graphG, and a cutC ofG, decide whetherC is maximal or not, and in case it is not, find a better solutionC′. As a consequence, an optimality testing oracle may be used to design a polynomial time algorithm for approximately solving the (weighted) Max-Cut Problem. This in turn implies that recognizing optimal cuts in an unweighted graph is NP-hard.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...