Title of article :
Maximum cuts: Improvements and local algorithmic analogues of the Edwards-Erdős inequality Original Research Article
Author/Authors :
Stanislaw Bylka، نويسنده , , Adam Idzik، نويسنده , , Zsolt Tuza، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 1999
Pages :
20
From page :
39
To page :
58
Abstract :
We propose some ‘local switching’ search algorithms for finding large bipartite subgraphs in simple undirected graphs. The algorithms are based on the ‘measure of effectiveness’ of the bipartitions of the vertex set. We analyze the worst-case behavior of these algorithms, giving general lower bounds, and also prove that the concept of switching has its limits no matter how large (fixed-size) substructures are taken in order to improve a locally optimal solution. Strengthening an early result by Edwards and Erdős, we also present two new lower bounds on the size of largest bipartite subgraphs of a graph. The first bound — involving the length of shortest odd cycles — is tight for any given girth and any number of vertices. Moreover, a corresponding bipartite subgraph can be found by a linear-time algorithm. The second bound is defined in terms of odd-degree edge-disjoint stars, and it is stronger than the Edwards-Erdős inequality whenever the graph in question contains at least two nonadjacent vertices of odd degree.
Keywords :
Local search , Maximum cut , Measure of effectiveness of a vertex bipartition , Bipartite subgraph
Journal title :
Discrete Mathematics
Serial Year :
1999
Journal title :
Discrete Mathematics
Record number :
951241
Link To Document :
بازگشت