The Graph of the Pedigree Polytope is Asymptotically Almost Complete (Extended Abstract)
From MaRDI portal
Publication:2971660
DOI10.1007/978-3-319-53007-9_26zbMath1490.90252arXiv1611.08419OpenAlexW2558060969MaRDI QIDQ2971660
Mozhgan Pourmoradnasseri, Abdullah Makkeh, Dirk Oliver Theis
Publication date: 7 April 2017
Published in: Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1611.08419
Related Items (1)
Cites Work
- A counterexample to the Hirsch conjecture
- Pancyclic properties of the graph of some 0-1 polyhedra
- A note on the relationship between the graphical traveling salesman polyhedron, the Symmetric Traveling Salesman Polytope, and the metric cone
- Vertex adjacencies in the set covering polyhedron
- Hamiltonicity in (0-1)-polyhedra
- On the graphical relaxation of the symmetric traveling salesman polytope
- Partial monotonizations of Hamiltonian cycle polytopes: Dimensions and diameters
- Study of the pedigree polytope and a sufficiency condition for nonadjacency in the tour polytope
- Combinatorial bounds on nonnegative rank and extended formulations
- Hidden vertices in extensions of polytopes
- The skeleton of the symmetric Traveling Salesman Polytope
- The graphical relaxation: A new framework for the symmetric traveling salesman polytope
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- An alternate formulation of the symmetric traveling salesman problem and its properties
- The common face of some 0/1-polytopes with NP-complete nonadjacency relation
- On the facial structure of symmetric and graphical traveling salesman polyhedra
- On pedigree polytopes and Hamiltonian cycles
- The Graph of the Pedigree Polytope is Asymptotically Almost Complete (Extended Abstract)
- The adjacency relation on the traveling salesman polytope is NP-Complete
- A Lower Bound for Adjacencies on the Traveling Salesman Polytope
- Symmetry Matters for Sizes of Extended Formulations
- Integer Programming and Combinatorial Optimization
- Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
This page was built for publication: The Graph of the Pedigree Polytope is Asymptotically Almost Complete (Extended Abstract)
