Complexity of the weighted max-cut in Euclidean space

DOI10.1134/S1990478914040012MaRDI QIDQ5264746zbMATH OpenOpenAlexFDO

Authors Alexander Ageev, A. V. Kel'manov, 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

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)

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

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2159019 (Why is no real title available?)
• scientific article; zbMATH DE number 2086928 (Why is no real title available?)
• scientific article; zbMATH DE number 1839431 (Why is no real title available?)
• scientific article; zbMATH DE number 1860688 (Why is no real title available?)
• A randomized approximation scheme for metric MAX-CUT
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• Data Collection for the Sloan Digital Sky Survey—A Network-Flow Heuristic
• Estimation of distribution algorithm for the max-cut problem
• NP-completeness of some problems of a vectors subset choice
• On complexity of some problems of cluster analysis of vector sequences
• On the complexity of a search for a subset of ``similar vectors
• Reducibility among combinatorial problems
• Some simplified NP-complete graph problems

Cited in

(5)

• Edge-Cuts of Optimal Average Weights
• Exact algorithms of searching for the largest size cluster in two integer 2-clustering problems
• NP-hardness of the Euclidean Max-Cut problem
• 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)