Local approximation of the maximum cut in regular graphs

DOI10.1016/j.tcs.2020.03.008zbMath1433.68607arXiv1902.04899OpenAlexW2972557096MaRDI QIDQ5918122

Louis Esperet, Étienne Bamas

Publication date: 21 April 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1902.04899

zbMATH Keywords

approximation algorithmmaximum cutregular graphsdistributed algorithm

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Distributed algorithms (68W15)

Related Items (1)

Delta invariant for Eulerian digraphs

Cites Work

• Unnamed Item
• Local algorithms for independent sets are half-optimal
• Locality of not-so-weak coloring
• Off-diagonal hypergraph Ramsey numbers
• Large cuts with local algorithms on triangle-free graphs
• Extremal cuts of sparse random graphs
• Limits of locally-globally convergent graph sequences
• Lower bounds for local approximation
• Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs
• Invariant Gaussian processes and independent sets on regular graphs of large girth
• Fast Distributed Approximations in Planar Graphs
• On the Power of Nodes of Degree Four in the Local Max-Cut Problem
• Locality in Distributed Graph Algorithms
• A note on bipartite subgraphs of triangle‐free graphs
• On the max‐cut of sparse random graphs
• Fast Distributed Approximation for Max-Cut
• What can be computed locally?
• Brief Announcement
• Factors of IID on Trees
• Combinatorial Theorems on Classifications of Subsets of a Given Set
• Limits of local algorithms over sparse random graphs
• Graph colouring and the probabilistic method

This page was built for publication: Local approximation of the maximum cut in regular graphs