The performance of an eigenvalue bound on the max-cut problem in some classes of graphs
Discrete MathematicsPublished 1 February 1993
Charles Delorme, S. Poljak
Citations42
SJR quartileQ1
SJR score0.88
SNIP1.18
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The performance of a number ?
Abstract
The authors earlier introduced a number ϕ(G), which gives a well-computable upper bound on the maximum bipartite subgraph of a graph or, more generally, on the maximum cut of a weighted graph. In this paper we study the performance of this bound on a large variety of examples from the graph theory. We also present an alternative definition of ϕ(G) using a graph operation of vertex-splitting. Finally, we present the results of some preliminary computational experiments on randomly generated graphs.
Keywords
Computer ScienceMathematics
Graph Theory with Applications
9,089 Citations1976J. A. Bondy, U. S. R. Murty
Distance-Regular Graphs
2,112 Citations1989Andries E. Brouwer, Arjeh M. Cohen +1 more
IBM Journal of Research and DevelopmentLower Bounds for the Partitioning of Graphs
662 Citations1973W. E. Donath, Alan J. Hoffman
SIAM Journal on ComputingFinding a Maximum Cut of a Planar Graph in Polynomial Time
393 Citations1975Frank Hadlock
The problem of finding a maximum cut of an arbitrary graph is one of a list of 21 combinatorial problems (Karp–Cook list) and it is unknown whether or not there exist algorithms operating in polynomia.
Mathematical ProgrammingLaplacian eigenvalues and the maximum cut problem
186 Citations1993Charles Delorme, S. Poljak
An eigenvalue upper boundϕ(G) on the maximum cut mc (G) of a weighted graph has several interesting properties that resemble the behaviour ofmc (G), and ϕ is subadditive with respect to amalgam, and additive withrespect to disjoint sum and 1-sum.
Operations Research LettersWeakly bipartite graphs and the Max-cut problem
172 Citations1981Martin Grötschel, William R. Pulleyblank
It is shown that the max-cut problem can be solved in polynomial time for weakly bipartite graphs and an algorithm that computes a shortest path of even length is presented.
European Journal of CombinatoricsOn a Pair of Dual Subschemes of the Hamming Scheme Hn(q)
25 Citations1985A.R. Calderbank, J.-M. Goethals
This work describes how a uniformly packed linear code C determines a pair of dual subschemes and establishes restrictions on the possible distances between codewords in the dual code C ⊥.
SIAM Journal on Algebraic and Discrete MethodsOn Transportation Problems with Upper Bounds on Leading Rectangles
22 Citations1985Earl Barnes, Alan J. Hoffman
For this class of problems, if the given bounds and cost coefficients satisfy certain conditions, an optimal solution can be found by a greedy algorithm.