Priority functions for the approximation of the metric TSP
From MaRDI portal
Publication:2444775
DOI10.1016/j.ipl.2013.05.002zbMath1296.68193OpenAlexW1969154297MaRDI QIDQ2444775
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
ordered binary decision diagramsapproximation algorithmsimplicit graph algorithmstraveling salesperson problem
Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
Randomized OBDD-based graph algorithms ⋮ On the OBDD representation of some graph classes ⋮ Randomized OBDD-Based Graph Algorithms ⋮ On efficient implicit OBDD-based algorithms for maximal matchings
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- On symbolic OBDD-based algorithms for the minimum spanning tree problem
- On the effect of local changes in the variable ordering of ordered decision diagrams
- Symbolic model checking: \(10^{20}\) states and beyond
- The Euclidean traveling salesman problem is NP-complete
- Reduction of OBDDs in linear time
- Exponential space complexity for OBDD-based reachability analysis
- Symbolic topological sorting with OBDDs
- Symbolic graphs: Linear solutions to connectivity related problems
- An Efficient Implicit OBDD-Based Algorithm for Maximal Matchings
- Implicit Computation of Maximum Bipartite Matchings by Sublinear Functional Operations
- On Symbolic Representations of Maximum Matchings and (Un)directed Graphs
- On two geometric problems related to the travelling salesman problem
- On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication
- Exponential Lower Bounds on the Space Complexity of OBDD-Based Graph Algorithms
- An Efficient Parallel Biconnectivity Algorithm
- Graph-Based Algorithms for Boolean Function Manipulation
- On the Complexity of the Hidden Weighted Bit Function for Various BDD Models
- Branching Programs and Binary Decision Diagrams
- The parallel complexity of TSP heuristics
- In Pursuit of the Traveling Salesman
- SOFSEM 2006: Theory and Practice of Computer Science
- SOFSEM 2004: Theory and Practice of Computer Science
