scientific article; zbMATH DE number 3588048

zbMATH Open0377.68036MaRDI QIDQ4155835FDOQ4155835

Authors: M. R. Garey, Ron Graham, D. S. Johnson 

Publication date: 1976

Title of this publication is not available (Why is that?)

Mathematics Subject Classification ID

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

Cited In (69)

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

This page was built for publication:

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