Bipartite subgraphs of integer weighted graphs

Noga Alon; Eran Halperin

doi:10.1016/S0012-365X(97)00041-1

Bipartite subgraphs of integer weighted graphs

Noga Alon, Eran Halperin

Research output: Contribution to journal › Article › peer-review

28 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((ⁿ₂) + m) = ⌊1/4n²⌋ + min(⌈1/2n⌉, f(m)). This supplies the precise value of f(p) for many values of p including, e.g., all p = (ⁿ₂) + (^m₂) when n is large enough and 1/4m² ≤ 1/2n.

Original language	English (US)
Pages (from-to)	19-29
Number of pages	11
Journal	Discrete Mathematics
Volume	181
Issue number	1-3
DOIs	https://doi.org/10.1016/S0012-365X(97)00041-1
State	Published - Feb 15 1998
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/S0012-365X(97)00041-1

Cite this

@article{59db1fc794b74cb1bb18fb8d8fde9a23,

title = "Bipartite subgraphs of integer weighted graphs",

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.",

author = "Noga Alon and Eran Halperin",

year = "1998",

month = feb,

day = "15",

doi = "10.1016/S0012-365X(97)00041-1",

language = "English (US)",

volume = "181",

pages = "19--29",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "1-3",

}

TY - JOUR

T1 - Bipartite subgraphs of integer weighted graphs

AU - Alon, Noga

AU - Halperin, Eran

PY - 1998/2/15

Y1 - 1998/2/15

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0038369163&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0038369163&partnerID=8YFLogxK

U2 - 10.1016/S0012-365X(97)00041-1

DO - 10.1016/S0012-365X(97)00041-1

M3 - Article

AN - SCOPUS:0038369163

SN - 0012-365X

VL - 181

SP - 19

EP - 29

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -

Bipartite subgraphs of integer weighted graphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this