Autocorrelation coefficient for the graph bipartitioning problem

DOI10.1016/S0304-3975(97)00176-XzbMath0902.90134OpenAlexW2072294492MaRDI QIDQ1127331

Vassilios Zissimopoulos, Eric Angel

Publication date: 13 August 1998

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(97)00176-x

zbMATH Keywords

simulated annealinglocal searchautocorrelation lengthgraph bipartitioning problem

Mathematics Subject Classification ID

Searching and sorting (68P10) Combinatorial optimization (90C27)

Related Items

Penalty and partitioning techniques to improve performance of QUBO solvers ⋮ Autocorrelation measures for the quadratic assignment problem ⋮ On the classification of NP-complete problems in terms of their correlation coefficient ⋮ Elementary landscape decomposition of the frequency assignment problem ⋮ Neutrality in fitness landscapes. ⋮ On the landscape ruggedness of the quadratic assignment problem ⋮ The linear ordering problem: instances, search space analysis and algorithms ⋮ Probabilistic characterization of random Max \(r\)-Sat ⋮ The Normalized Autocorrelation Length of Random Max  $$r$$ -Sat Converges in Probability to $$(1-1/2^r)/r$$

Cites Work

• Unnamed Item
• Unnamed Item
• Correlated and uncorrelated fitness landscapes and how to tell the difference
• Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
• Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
• An Efficient Heuristic Procedure for Partitioning Graphs
• The landscape of the traveling salesman problem