Priority functions for the approximation of the metric TSP

DOI10.1016/J.IPL.2013.05.002MaRDI QIDQ2444775zbMATH OpenOpenAlexFDO

Authors Beate Bollig, Michael Capelle

Publication date 11 April 2014

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2013.05.002

zbMATH Keywords

approximation algorithmsimplicit graph algorithmsordered binary decision diagramstraveling salesperson problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Recommendations

• Approximating the metric TSP in linear time
• Approximating the Metric TSP in Linear Time
• Algorithms – ESA 2005
• Improved deterministic approximation algorithms for max TSP
• Fast Minimum-Weight Double-Tree Shortcutting for Metric TSP

Cites work

• An efficient implicit OBDD-based algorithm for maximal matchings
• An Efficient Parallel Biconnectivity Algorithm
• Branching Programs and Binary Decision Diagrams
• Exponential Lower Bounds on the Space Complexity of OBDD-Based Graph Algorithms
• Exponential space complexity for OBDD-based reachability analysis
• Graph-Based Algorithms for Boolean Function Manipulation
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• Implicit computation of maximum bipartite matchings by sublinear functional operations
• In pursuit of the traveling salesman. Mathematics at the limits of computation
• On symbolic OBDD-based algorithms for the minimum spanning tree problem
• On symbolic representations of maximum matchings and (Un)directed graphs
• On the Complexity of the Hidden Weighted Bit Function for Various BDD Models
• On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication
• On the effect of local changes in the variable ordering of ordered decision diagrams
• On two geometric problems related to the travelling salesman problem
• Reduction of OBDDs in linear time
• SOFSEM 2004: Theory and Practice of Computer Science
• SOFSEM 2006: Theory and Practice of Computer Science
• Symbolic graphs: Linear solutions to connectivity related problems
• Symbolic model checking: \(10^{20}\) states and beyond
• Symbolic topological sorting with OBDDs
• The Euclidean traveling salesman problem is NP-complete
• The parallel complexity of TSP heuristics
• The traveling salesman problem. A computational study.

Cited in

(6)

• Randomized OBDD-based graph algorithms
• A priori TSP in the Scenario Model
• On the OBDD representation of some graph classes
• scientific article; zbMATH DE number 5008243 (Why is no real title available?)
• Randomized OBDD-based graph algorithms
• On efficient implicit OBDD-based algorithms for maximal matchings

Describes a project that uses

Uses Software

• Concorde

This page was built for publication: Priority functions for the approximation of the metric TSP

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