Bipartite subgraphs of integer weighted graphs

Noga Alon, Eran Halperin

Research output: Contribution to journalArticlepeer-review

19 Scopus citations

Abstract

For every integer p > 0, let f(p) be the minimum possible value of the maximum weight of a cut in an integer weighted graph with total weight p. It is shown that for every large n and every m < n, f((n2) + m) = ⌊1/4n2⌋ + min(⌈1/2n⌉, f(m)). This supplies the precise value of f(p) for many values of p including, e.g., all p = (n2) + (m2) when n is large enough and 1/4m2 ≤ 1/2n.

Original languageEnglish (US)
Pages (from-to)19-29
Number of pages11
JournalDiscrete Mathematics
Volume181
Issue number1-3
DOIs
StatePublished - Feb 15 1998
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Bipartite subgraphs of integer weighted graphs'. Together they form a unique fingerprint.

Cite this