Maximum cuts: Improvements and local algorithmic analogues of the Edwards-Erdős inequality

DOI10.1016/S0012-365X(98)00115-0zbMath0929.05044MaRDI QIDQ1297468

Adam Idzik, Stanisław Bylka, Zsolt Tuza

Publication date: 2 September 1999

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

partitionlocal searchinequalitymaximum cutlower boundbipartite subgraphlocal switching algorithms

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Problems and results on judicious partitions ⋮ Pseudo-Boolean optimization ⋮ Satisfactory graph partition, variants, and generalizations ⋮ Judicious partitions of bounded‐degree graphs ⋮ On the effectiveness of immune inspired mutation operators in some discrete optimization problems ⋮ Eigenvector-based identification of bipartite subgraphs ⋮ Walk-preserving transformation of overlapped sequence graphs into blunt sequence graphs with GetBlunted

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Triangle-free partial graphs and edge covering theorems
• A linear time algorithm for graph partition problems
• Laplacian eigenvalues and the maximum cut problem
• On some extremal problems in graph theory
• Bipartite subgraphs
• .879-approximation algorithms for MAX CUT and MAX 2SAT
• Largest bipartite subgraphs in triangle-free graphs with maximum degree three
• Maximumk-colorable subgraphs
• A note on bipartite subgraphs of triangle‐free graphs
• Linear-Time Approximation Algorithms for the Max Cut Problem
• Bipartite Subgraphs of Triangle-Free Graphs
• Some Extremal Properties of Bipartite Subgraphs

This page was built for publication: Maximum cuts: Improvements and local algorithmic analogues of the Edwards-Erdős inequality