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

DOI10.1007/978-3-642-13073-1_24zbMath1284.05304OpenAlexW1567483970MaRDI QIDQ3563008

Tobias Tscheuschner, Burkhard Monien

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 searchPLSmax-cutdegree four

Mathematics Subject Classification ID

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

Related Items (5)

Computing Stable Outcomes in Hedonic Games ⋮ Computing Stable Outcomes in Symmetric Additively Separable Hedonic Games ⋮ Representing Fitness Landscapes by Valued Constraints to Understand the Complexity of Local Search ⋮ Settling the Complexity of Local Max-Cut (Almost) Completely ⋮ Local approximation of the maximum cut in regular graphs

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