Fully dynamic sequential and distributed algorithms for MAX-CUT

DOI10.4230/LIPICS.FSTTCS.2020.33MaRDI QIDQ6839871zbMATH OpenFDO

Authors Omer Wasim, Valerie King

Publication date 23 March 2026

Copyright license Creative Commons Attribution 3.0 Unported

Full work available at URL https://doi.org/10.4230/LIPICS.FSTTCS.2020.33

zbMATH Keywords

distributed computingdata structuresparallel computingdynamic graph algorithmsapproximate maximum cut

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Cites work

• scientific article; zbMATH DE number 6850309 (Why is no real title available?)
• scientific article; zbMATH DE number 7378709 (Why is no real title available?)
• scientific article; zbMATH DE number 6297759 (Why is no real title available?)
• .878-approximation algorithms for MAX CUT and MAX 2SAT
• A combinatorial, primal-dual approach to semidefinite programs
• A deamortization approach for dynamic spanner and dynamic maximal matching
• An On-Line Edge-Deletion Problem
• Approximation algorithms for combinatorial problems
• Distributed computation in dynamic networks
• Distributed computation in dynamic networks via random walks
• Dominating sets and connected dominating sets in dynamic graphs
• Dynamic algorithms via the primal-dual method
• Dynamic graph connectivity in polylogarithmic worst case time
• Fast Distributed Approximation for Max-Cut
• Fully Dynamic Maximal Independent Set with Sublinear in n Update Time
• Fully Dynamic Maximal Matching in O (log n) Update Time
• Fully dynamic maximal independent set with sublinear update time
• Fully dynamic maximal matching in constant update time
• Fully-dynamic MIN-cut
• Improved Analysis of a Max-Cut Algorithm Based on Spectral Partitioning
• Maintaining a large matching and a small vertex cover
• Max cut and the smallest eigenvalue
• Online and dynamic algorithms for set cover
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Optimal cuts in graphs and statistical mechanics
• Optimal dynamic distributed MIS
• Parallel Batch-Dynamic Graphs: Algorithms and Lower Bounds
• Parallel algorithms for geometric graph problems
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
• Randomized fully dynamic graph algorithms with polylogarithmic time per operation
• Simple deterministic algorithms for fully dynamic maximal matching
• Sorting, searching, and simulation in the MapReduce framework

This page was built for publication: Fully dynamic sequential and distributed algorithms for MAX-CUT

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