Long Local Searches for Maximal Bipartite Subgraphs

DOI10.1137/060666615MaRDI QIDQ3394991zbMATH OpenOpenAlexFDO

Authors Hemanshu Kaul, Douglas B. West

Publication date 20 August 2009

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/23563cccf4de7330ca13a2fd28feb699c9690b2f

zbMATH Keywords

hill-climbing algorithmlarge bipartite subgraphlocal switchingMAX-CUT problem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On the number of maximal bipartite subgraphs of a graph
• The size of the largest bipartite subgraphs
• Bipartite subgraphs
• Local improving algorithms for large cuts in graphs with maximum degree three
• Largest bipartite subgraphs in triangle-free graphs with maximum degree three

This page was built for publication: Long Local Searches for Maximal Bipartite Subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3394991)