On pedigree polytopes and Hamiltonian cycles

DOI10.1016/j.disc.2005.11.030zbMath1103.90078OpenAlexW2171367973MaRDI QIDQ2497514

Yanyan Li

Publication date: 4 August 2006

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2005.11.030

zbMATH Keywords

Hamiltonian cyclesflows in networkssymmetric traveling salesman problemmultistage insertion formulationnonadjacency testingpedigree polytope

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational aspects related to convexity (52B55) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45)

Related Items

Study of the pedigree polytope and a sufficiency condition for nonadjacency in the tour polytope, The Graph of the Pedigree Polytope is Asymptotically Almost Complete (Extended Abstract), Hamiltonian decomposition and verifying vertex adjacency in 1-skeleton of the traveling salesperson polytope by variable neighborhood search, Scheduling algorithms for flexible flowshops: Worst and average case performance, Traveling Salesman Problem and Membership in Pedigree Polytope - A Numerical Illustration, Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard, Performance of scheduling algorithms for no-wait flowshops with parallel machines, Backtracking Algorithms for Constructing the Hamiltonian Decomposition of a 4-regular Multigraph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Neighbor relations on the convex of cyclic permutations
• An analytical comparison of different formulations of the travelling salesman problem
• The traveling salesman problem and its variations
• An alternate formulation of the symmetric traveling salesman problem and its properties
• Integer Programming Formulation of Traveling Salesman Problems
• Dynamic Programming Treatment of the Travelling Salesman Problem
• Adjacency of the Traveling Salesman Tours and $0 - 1$ Vertices
• The adjacency relation on the traveling salesman polytope is NP-Complete
• Technical Note—An n-Constraint Formulation of the (Time-Dependent) Traveling Salesman Problem
• Separating clique tree and bipartition inequalities in polynomial time
• Solution of a Large-Scale Traveling-Salesman Problem
• On the Tours of a Traveling Salesman
• On the equivalence of the multistage-insertion and cycle-shrink formulations of the symmetric traveling salesman problem