Efficiently solvable special cases of hard combinatorial optimization problems

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items (3)

The two-stripe symmetric circulant TSP is in P ⋮ Using well-solvable minimum cost exact covering for VLSI clock energy minimization ⋮ Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Steiner minimal trees for regular polygons
Steiner problem in Halin networks
A primer of the Euclidean Steiner problem
A special case of the \(n\)-vertex traveling-salesman problem that can be solved in O(\(n\)) time
Permutational extreme values of autocorrelation coefficients and a Pitman test against serial dependence
The Steiner tree problem
Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
The quadratic assignment problem with a monotone anti-Monge and a symmetric Toeplitz matrix: Easy and hard cases
Recognition of \(d\)-dimensional Monge arrays
Cut and patch Steiner trees for ladders
Hamiltonian cycles in circulant digraphs with two stripes
Polynomially solvable cases of the traveling salesman problem and a new exponential neighborhood
Perspectives of Monge properties in optimization
On the recognition of permuted Supnick and incomplete Monge matrices
Universal conditions for algebraic travelling salesman problems to be efficiently solvable
Sequence comparison with mixed convex and concave costs
Quadratic assignment problems on series-parallel digraphs
The Product Matrix Traveling Salesman Problem: An Application and Solution Heuristic
Steiner Trees for Ladders
The structure of circular decomposable metrics
Steiner Trees on a Checkerboard
Halin graphs and the travelling salesman problem
A Travelling Salesman Model for the Sequencing of Duties in Bus Crew Rotas
Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem

This page was built for publication: Efficiently solvable special cases of hard combinatorial optimization problems