We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Finding local Max-Cut in graphs in randomized polynomial time.
- Authors
Gao, Lunshan
- Abstract
A maximum cut (Max-Cut) problem in graph theory is NP-hard. This paper proposes a new randomized algorithm for finding local Max-Cut in graphs by using fuzzy logic. This paper proves that: (1) the computational complexity of computing local Max-Cut in graphs is in the class of randomized polynomial time (RP); (2) the real number solution of the new algorithm satisfies ϵ - δ condition; (3) local Max-Cut solutions are maintained after defuzzification that converts real number vectors to integer vectors. Numerical experiments show that the new algorithm outperforms IBM CPLEX solvers. The new algorithm is nine times faster than the CPLEX Convex solver and more than thirty times faster than the CPLEX Global solver. The new algorithm could find local Max-Cut in signed graphs whereas CPLEX Convex solver failed to find Max-Cut in signed graphs when Laplacian matrix was not positive semidefinite.
- Subjects
INTERNATIONAL Business Machines Corp.; REAL numbers; GRAPH theory; FUZZY logic; COMPUTATIONAL complexity; FUZZY graphs; DIOPHANTINE equations; LAPLACIAN matrices
- Publication
Soft Computing - A Fusion of Foundations, Methodologies & Applications, 2024, Vol 28, Issue 4, p3029
- ISSN
1432-7643
- Publication type
Article
- DOI
10.1007/s00500-023-09230-5