Unique optimal solution instance and computational complexity of backbone in the graph bi-partitioning problem

DOI10.1007/S11434-007-0407-6MaRDI QIDQ2482999zbMATH OpenOpenAlexFDO

Authors He Jiang, Guoliang Chen

Publication date 2 May 2008

Published in Chinese Science Bulletin (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11434-007-0407-6

zbMATH Keywords

computational complexityNP-hardbackbone analysisgraph bi-partitioning problemunique optimal solution instance

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Backbone analysis and algorithm design for the quadratic assignment problem
• Backbone analysis and applications in heuristic algorithm design
• A note on backbones in optimization and approximation
• The computational complexity of the backbone coloring problem for bounded-degree graphs with connected backbones
• The computational complexity of \(\lambda\)-backbone colorings of graphs with \(n\)-complete backbones

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1930743 (Why is no real title available?)
• scientific article; zbMATH DE number 2242691 (Why is no real title available?)
• scientific article; zbMATH DE number 2243360 (Why is no real title available?)
• A combined evolutionary search and multilevel optimisation approach to graph-partitioning
• A mixed heuristic for circuit partitioning
• An Efficient Heuristic Procedure for Partitioning Graphs
• Configuration landscape analysis and backbone guided local search. I: Satisfiability and maximum satisfiability
• Determining computational complexity from characteristic ``phase transitions
• Landscapes, operators and heuristic search
• P-Complete Approximation Problems
• Searching for Backbones—a high-performance parallel algorithm for solving combinatorial optimization problems

Cited in

(2)

• Backbone analysis and applications in heuristic algorithm design
• Backbone analysis and algorithm design for the quadratic assignment problem

Describes a project that uses

Uses Software

• BG-WalkSAT

This page was built for publication: Unique optimal solution instance and computational complexity of backbone in the graph bi-partitioning problem

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