On the set covering polyhedron of circulant matrices

DOI10.1016/j.disopt.2008.11.001zbMath1203.90127OpenAlexW1974210811MaRDI QIDQ1015320

Silvia M. Bianchi, Gabriela R. Argiroffo

Publication date: 7 May 2009

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

Full work available at URL: https://doi.org/10.1016/j.disopt.2008.11.001

zbMATH Keywords

circulant matrixset covering polyhedronfractional extreme pointnon-Boolean facet

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Combinatorial optimization (90C27) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Hermitian, skew-Hermitian, and related matrices (15B57) Perfect graphs (05C17)

Related Items

The discriminance for a special class of circulant matrices and their diagonalization, Generalized minor inequalities for the set covering polyhedron related to circulant matrices, Some advances on the set covering polyhedron of circulant matrices, Minor related row family inequalities for the set covering polyhedron of circulant matrices, On dominating set polyhedra of circular interval graphs, The nonidealness index of circulant matrices, Computing the square roots of a class of circulant matrices, The minor inequalities in the description of the set covering polyhedron of circulant matrices, Progress on the description of identifying code polyhedra for some families of split graphs, Polyhedra associated with identifying codes in graphs, Lift-and-project ranks of the set covering polytope of circulant matrices, Unnamed Item, Unnamed Item, The computation of the square roots of circulant matrices, The nonidealness index of rank-ideal matrices, On packing and covering polyhedra of consecutive ones circulant clutters, Strength of facets for the set covering and set packing polyhedra on circulant matrices, On the dominating set polytope of web graphs, Polyhedra associated with locating-dominating, open locating-dominating and locating total-dominating sets in graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Lehman's forbidden minor characterization of ideal 0-1 matrices
• A construction for non-rank facets of stable set polytopes of webs
• The strong perfect graph theorem
• On the facial structure of the set covering polytope
• Facets and lifting procedures for the set covering polytope
• A class of facet producing graphs for vertex packing polyhedra
• The matroids with the max-flow min-cut property
• Ideal 0, 1 matrices
• Near-perfect matrices
• On certain polytopes associated with graphs
• Antiwebs are rank-perfect
• On a certain class of nonideal clutters
• Almost all webs are not rank-perfect
• Combinatorial Optimization
• On the width—length inequality