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

DOI10.1007/S11434-007-0407-6zbMATH Open1134.68375OpenAlexW2020616975MaRDI QIDQ2482999FDOQ2482999

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

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

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)

Cites Work

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

Cited In (2)

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

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)