scientific article; zbMATH DE number 3588048

Michael R. Garey, David S. Johnson, Ronald L. Graham

Publication date: 1976

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Deterministic network models in operations research (90B10) Directed graphs (digraphs), tournaments (05C20) Algorithms in computer science (68W99)

Related Items

Approximation Algorithms for the Traveling Salesman Problem with Range Condition, An estimate of the objective function optimum for the network Steiner problem, Faster algorithms for orienteering and \(k\)-TSP, The Computational Complexity of Trembling Hand Perfection and Other Equilibrium Refinements, Approximation algorithms for the Geometric Covering Salesman Problem, On a new edge function on complete weighted graphs and its application for locating Hamiltonian cycles of small weight, Good triangulations yield good tours, The algebraic degree of geometric optimization problems, Solving a selective dial-a-ride problem with logic-based Benders decomposition, Approximation schemes for node-weighted geometric Steiner tree problems, The simultaneous semi-random model for TSP, Querying probabilistic business processes for sub-flows, A Note on the Complexity of Comparing Succinctly Represented Integers, with an Application to Maximum Probability Parsing, Vehicle routing on road networks: how good is Euclidean approximation?, Complexity of rational and irrational Nash equilibria, The traveling salesman problem on grids with forbidden neighborhoods, Multi-shuttle crane scheduling in automated storage and retrieval systems, Strategies for Generating Well Centered Tetrahedral Meshes on Industrial Geometries, On the Order of Power Series and the Sum of Square Roots Problem, Financial networks with singleton liability priorities, A fast algorithm for Steiner trees, Financial networks with singleton liability priorities, Probabilistic analysis of some Euclidean clustering problems, An ETH-Tight Exact Algorithm for Euclidean TSP, Watchman tours for polygons with holes, Observation routes and external watchman routes, Minimum rectilinear Steiner tree of \(n\) points in the unit square, Time complexity of the analyst's traveling salesman algorithm, Constant-Factor Approximation for TSP with Disks, An optimal solution to a wire-routing problem, The Shortest Separating Cycle Problem, The structure of minimal Steiner trees in the neighborhoods of the lunes of their edges, Probabilistic analysis of solving the assignment problem for the traveling salesman problem, Unnamed Item, Watchman routes for lines and line segments, Equilibria, fixed points, and complexity classes, Constraint Satisfaction Problems over Numeric Domains, Approximating maxmin strategies in imperfect recall games using A-loss recall property, The kissing problem: how to end a gathering when everyone kisses everyone else goodbye, Directional derivative of the weight of a minimal filling in Riemannian manifolds, On the computational complexity of centers locating in a graph, On the transformation capability of feasible mechanisms for programmable matter, Worst-case minimum rectilinear Steiner trees in all dimensions, Hard to solve instances of the Euclidean traveling salesman problem, Tractability conditions for numeric CSPs, Fast geometric approximation techniques and geometric embedding problems, A problem that is easier to solve on the unit-cost algebraic RAM, Bounding the sum of square roots via lattice reduction, Efficient algorithms for sparse cyclotomic integer zero testing, On Euclidean vehicle routing with allocation, Cooperative TSP, Algebraic optimization: The Fermat-Weber location problem, Recursive Markov Decision Processes and Recursive Stochastic Games, The Euclidean traveling salesman problem is NP-complete, Rearranging data to maximize the efficiency of compression, The Complexity of Nash Equilibria in Limit-Average Games, Minimal binary trees with a regular boundary: The case of skeletons with five endpoints, NP-completeness of the Hamming salesman problem, Asymptotic expected performance of some TSP heuristics: An empirical evaluation, The optimum assignments and a new heuristic approach for the traveling salesman problem, Unnamed Item, The traveling salesman problem with few inner points, Optimal search with positive switch cost is NP-hard