Vertex adjacencies in the set covering polyhedron
From MaRDI portal
Publication:730484
DOI10.1016/J.DAM.2016.10.024zbMATH Open1352.05179arXiv1406.6015OpenAlexW1548698003MaRDI QIDQ730484FDOQ730484
P. Tolomei, Néstor E. Aguilera, Ricardo D. Katz
Publication date: 28 December 2016
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Abstract: We describe the adjacency of vertices of the (unbounded version of the) set covering polyhedron, in a similar way to the description given by Chvatal for the stable set polytope. We find a sufficient condition for adjacency, and characterize it with similar conditions in the case where the underlying matrix is row circular. We apply our findings to show a new infinite family of minimally nonideal matrices.
Full work available at URL: https://arxiv.org/abs/1406.6015
Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20) Graph theory (05C99)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- On certain polytopes associated with graphs
- Adjacency on combinatorial polyhedra
- A catalog of minimally nonideal matrices
- Ideal 0, 1 matrices
- On the width—length inequality
- Cyclic Scheduling via Integer Programs with Circular Ones
- A new infinite family of minimally nonideal matrices
- The stable set polytope of quasi-line graphs
- The Hirsch conjecture for the fractional stable set polytope
- On the width-length inequality
- The adjacency relation on the traveling salesman polytope is NP-Complete
- Adjacency on the constrained assignment problem
- Ideal polytopes and face structures of some combinatorial optimization problems
Cited In (6)
- Hamiltonian decomposition and verifying vertex adjacency in 1-skeleton of the traveling salesperson polytope by variable neighborhood search
- Addendum to: ``Vertex adjacencies in the set covering polyhedron
- The Graph of the Pedigree Polytope is Asymptotically Almost Complete (Extended Abstract)
- Determining adjacent vertices on assignment polytopes
- Finding a second Hamiltonian decomposition of a 4-regular multigraph by integer linear programming
- Backtracking Algorithms for Constructing the Hamiltonian Decomposition of a 4-regular Multigraph
Uses Software
This page was built for publication: Vertex adjacencies in the set covering polyhedron
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q730484)
