Maximizing Several Cuts Simultaneously

Research output: Contribution to journalArticle

7 Citations (Scopus)

Abstract

Consider two graphs G(1) and G(2) on the same vertex set V and suppose that G(i) has m(i) edges. Then there is a bipartition of V into two classes A and B so that, for both i = 1, 2, we have eG(i) (A, B) >= m(i)/2 - root(m(i)) over bar. This gives an approximate answer to a question of Bollobas and Scott. We also prove results about partitions into more than two vertex classes. Our proofs yield polynomial algorithms.
Original languageEnglish
Pages (from-to)277-283
Number of pages7
JournalCombinatorics, Probability and Computing
Volume16
Issue number02
Early online date14 Aug 2006
DOIs
Publication statusPublished - 1 Mar 2007

Fingerprint

Dive into the research topics of 'Maximizing Several Cuts Simultaneously'. Together they form a unique fingerprint.

Cite this