Complexity of the weighted max-cut in Euclidean space

DOI10.1134/S1990478914040012zbMATH Open1324.05188OpenAlexW2037094620MaRDI QIDQ5264746FDOQ5264746

A. V. Kel'manov, Alexander Ageev, Artem Pyatkin

Publication date: 27 July 2015

Published in: Journal of Applied and Industrial Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s1990478914040012

Recommendations

• NP-hardness of the Euclidean Max-Cut problem
• MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
• scientific article; zbMATH DE number 1496855
• The maximum cut problem
• A randomized approximation scheme for metric MAX-CUT

zbMATH Keywords

cutEuclidean spaceNP-hard problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Signed and weighted graphs (05C22)

Cites Work

• Title not available (Why is that?)
• Reducibility among Combinatorial Problems
• Title not available (Why is that?)
• Some simplified NP-complete graph problems
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• Title not available (Why is that?)
• On complexity of some problems of cluster analysis of vector sequences
• On the complexity of a search for a subset of ``similar vectors
• Title not available (Why is that?)
• Title not available (Why is that?)
• A randomized approximation scheme for metric MAX-CUT
• Data Collection for the Sloan Digital Sky Survey—A Network-Flow Heuristic
• Title not available (Why is that?)
• Estimation of Distribution Algorithm for the Max-Cut Problem

Cited In (4)

• Edge-Cuts of Optimal Average Weights
• Exact algorithms of searching for the largest size cluster in two integer 2-clustering problems
• NP-hardness of some quadratic Euclidean 2-clustering problems
• On the complexity of some quadratic Euclidean 2-clustering problems

This page was built for publication: Complexity of the weighted max-cut in Euclidean space

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