Premium
Local bipartite turán graphs and graph partitioning
Author(s) -
Lee Jon,
Ryan Jennifer
Publication year - 1994
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230240302
Subject(s) - combinatorics , bipartite graph , mathematics , heuristic , computation , lagrangian , discrete mathematics , adjacency list , class (philosophy) , graph , mathematical optimization , computer science , algorithm , artificial intelligence
Motivated by the NP‐hard problem of finding a minimum‐weight balanced bipartition of an edge‐weighted complete graph, we studied the class of graphs having the same degrees as bipartite Turán graphs. In particular, we established 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 that we exploit in a heuristic for the partitioning problem, as well as in the computation of a Lagrangian bound. Preliminary computational results with the heuristic appear to be quite promising. Further results are established linking various adjacency concepts and measures of nonbipartiteness for such graphs. We also demonstrate the potential power of the Lagrangian bound via a family of examples. © 1994 by John Wiley & Sons, Inc.