On the Power of Nodes of Degree Four in the Local Max-Cut Problem

DOI10.1007/978-3-642-13073-1_24zbMATH Open1284.05304OpenAlexW1567483970MaRDI QIDQ3563008FDOQ3563008

Authors: Burkhard Monien, Tobias Tscheuschner 

Publication date: 28 May 2010

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-13073-1_24

Recommendations

• Local approximation of the maximum cut in regular graphs
• Local approximation of the maximum cut in regular graphs
• Node and edge relaxations of the max-cut problem
• Local improving algorithms for large cuts in graphs with maximum degree three
• Settling the complexity of local max-cut (almost) completely
• Local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree
• On \(L\)-borderenergetic graphs with maximum degree at most 4
• A refined algorithm for maximum independent set in degree-4 graphs
• Weight choosability of graphs with maximum degree 4
• Approximating Minimum-Power Degree and Connectivity Problems

zbMATH Keywords

complexitylocal searchmax-cutPLSdegree four

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85)

Cited In (7)

• Computing Stable Outcomes in Hedonic Games
• Integer Linear Programs and Local Search for Max-Cut
• Representing fitness landscapes by valued constraints to understand the complexity of local search
• Settling the complexity of local max-cut (almost) completely
• Stability based on single-agent deviations in additively separable hedonic games
• Local approximation of the maximum cut in regular graphs
• Computing Stable Outcomes in Symmetric Additively Separable Hedonic Games

This page was built for publication: On the Power of Nodes of Degree Four in the Local Max-Cut Problem

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