Local optimization on graphs
From MaRDI portal
Publication:1122503
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
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
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
