Vertex adjacencies in the set covering polyhedron

DOI10.1016/J.DAM.2016.10.024MaRDI QIDQ730484zbMATH OpenOpenAlexFDO

Authors Néstor E. Aguilera, Ricardo D. Katz, P. Tolomei

Publication date 28 December 2016

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

Full work available at URL https://arxiv.org/abs/1406.6015

zbMATH Keywords

polyhedral combinatoricsvertex adjacencyset-covering polyhedron

Mathematics Subject Classification ID

Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20) Graph theory (05C99)

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.

Recommendations

• Some advances on the set covering polyhedron of circulant matrices
• On the facial structure of the set covering polytope
• Some insight into characterizations of minimally nonideal matrices
• On the set covering polyhedron of circulant matrices
• On the 0,1 facets of the set covering polytope

Cites work

• scientific article; zbMATH DE number 3659288 (Why is no real title available?)
• scientific article; zbMATH DE number 16723 (Why is no real title available?)
• A catalog of minimally nonideal matrices
• A new infinite family of minimally nonideal matrices
• Adjacency on combinatorial polyhedra
• Adjacency on the constrained assignment problem
• Cyclic Scheduling via Integer Programs with Circular Ones
• Ideal 0, 1 matrices
• Ideal polytopes and face structures of some combinatorial optimization problems
• On certain polytopes associated with graphs
• On the width-length inequality
• On the width—length inequality
• The Hirsch conjecture for the fractional stable set polytope
• The adjacency relation on the traveling salesman polytope is NP-Complete
• The stable set polytope of quasi-line graphs

Cited in

(7)

• 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
• Row family inequalities for the set covering polyhedron
• Backtracking Algorithms for Constructing the Hamiltonian Decomposition of a 4-regular Multigraph

Describes a project that uses

Uses Software

• PORTA
• cdd

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)