Autocorrelation coefficient for the graph bipartitioning problem

DOI10.1016/S0304-3975(97)00176-XMaRDI QIDQ1127331zbMATH OpenOpenAlexFDO

Authors Eric Angel, V. Zissimopoulos

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

autocorrelation lengthgraph bipartitioning problemlocal searchsimulated annealing

Mathematics Subject Classification ID

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

Recommendations

• On the classification of NP-complete problems in terms of their correlation coefficient
• Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
• Combining simulated annealing with local search heuristics
• Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning

Cites work

• An Efficient Heuristic Procedure for Partitioning Graphs
• Correlated and uncorrelated fitness landscapes and how to tell the difference
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• 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
• The landscape of the traveling salesman problem

Cited in

(10)

• The linear ordering problem: instances, search space analysis and algorithms
• On the classification of NP-complete problems in terms of their correlation coefficient
• Probabilistic characterization of random Max r-Sat
• Penalty and partitioning techniques to improve performance of QUBO solvers
• The Normalized Autocorrelation Length of Random Max  $$r$$ -Sat Converges in Probability to $$(1-1/2^r)/r$$
• Autocorrelation measures for the quadratic assignment problem
• scientific article; zbMATH DE number 2013561 (Why is no real title available?)
• Neutrality in fitness landscapes.
• On the landscape ruggedness of the quadratic assignment problem
• Elementary landscape decomposition of the frequency assignment problem

This page was built for publication: Autocorrelation coefficient for the graph bipartitioning problem

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