On the max-cut of sparse random graphs
We consider the problem of estimating the size of a maximum cut (Max-Cut problem) in a random Erdős-Rényi graph on n nodes and ⌊cn⌋ edges. It is shown in Coppersmith et al. that the size of the maximum cut in this graph normalized by the number of nodes belongs to the asymptotic region [c/2 + 0.376...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Published: |
Wiley
2019
|
| Online Access: | http://hdl.handle.net/1721.1/120495 https://orcid.org/0000-0001-8898-8778 https://orcid.org/0000-0002-3726-1517 |