Local bipartite Turan graph partitioning

Jennifer Ryan and Jon Lee
Additional contact information
Jennifer Ryan: CORE, Université catholique de Louvain, B-1348 Louvain-la-Neuve, Belgium

No 1992019, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: Motivated by the NP-Hard problem of finding a minimum-weight balanced bipartition of an edge-weighted complete graph, we study the class of graphs having the same degrees as bipartite 'fur.an graphs. In particular, we establish a maximal set of linear equations satisfied by the counts of the possible incidences of 3- and 4-cycles on such graphs. This leads to extremal results which we exploit in a heuristic for the partitioning problem. Preliminary computational results appear to be quite promising. Further results are established linking various adjacency concepts and measures of non-bipartiteness for such graphs. We also discuss a Lagrangian bound for the partitioning problem and demonstrate its potential power via a family of examples.

Date: 1992-03-01
References: Add references at CitEc
Citations:

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp1992.html (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:1992019

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().