Local optimization on graphs

DOI10.1016/0166-218X(89)90025-5zbMath0675.90085OpenAlexW2007873061MaRDI QIDQ1122503

Donna Crystal Llewellyn, Michael A. Trick, Craig A. Tovey

Publication date: 1989

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(89)90025-5

zbMATH Keywords

heuristicneighborhood graphlocal optimumpolynomial time local search

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05) Applications of game theory (91A80) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99) Algorithms in computer science (68W99)

Related Items (26)

Unique-Maximum and Conflict-Free Coloring for Hypergraphs and Tree Graphs ⋮ On the quantum query complexity of local search in two and three dimensions ⋮ On the black-box complexity of Sperner's Lemma ⋮ Extending shelling orders and a hierarchy of functions of unimodal simple polytopes ⋮ Ordered colourings ⋮ A lower bound for on-line ranking number of a path ⋮ Edge ranking of graphs is hard ⋮ Almost Envy-Freeness with General Valuations ⋮ Graph unique-maximum and conflict-free colorings ⋮ Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds ⋮ Ordered coloring of grids and related graphs ⋮ The unbiased black-box complexity of partition is polynomial ⋮ Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs ⋮ Representing Fitness Landscapes by Valued Constraints to Understand the Complexity of Local Search ⋮ Quantum and classical query complexities of local search are polynomially related ⋮ Towards a Complexity Theory of Randomized Search Heuristics: Ranking-Based Black-Box Complexity ⋮ On the diameter of tree associahedra ⋮ Optimal vertex ranking of block graphs ⋮ Probability and convergence for supra-majority rule with Euclidean preferences ⋮ Ranking-based black-box complexity ⋮ (Strong) conflict-free connectivity: algorithm and complexity ⋮ Width, depth, and space: tradeoffs between branching and dynamic programming ⋮ On the deterministic complexity of searching local maxima ⋮ Dividing and conquering the square ⋮ Ordered Coloring Grids and Related Graphs ⋮ Enhanced algorithms for local search

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A simplified NP-complete satisfiability problem
• Lower bounds on the worst-case complexity of some oracle algorithms
• Das Geschlecht des vollständigen paaren Graphen
• A separator theorem for graphs of bounded genus
• Some NP-complete problems in quadratic and nonlinear programming
• Generalized Nested Dissection
• On the Problem of Partitioning Planar Graphs
• Multidimensional Searching Problems
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Low order polynomial bounds on the expected performance of local improvement algorithms
• The Genus of the n-Cube
• Lengths of snakes in boxes

This page was built for publication: Local optimization on graphs