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

DOI10.1007/978-3-642-13073-1_24MaRDI QIDQ3563008zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

complexitylocal searchmax-cutPLSdegree four

Mathematics Subject Classification ID

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

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

Cited in

(7)

• 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
• 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

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)