Integer Decomposition for Polyhedra Defined by Nearly Totally Unimodular Matrices
From MaRDI portal
Publication:5470794
DOI10.1137/S089548010343569XzbMath1113.90101MaRDI QIDQ5470794
Publication date: 1 June 2006
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s089548010343569x
circular arc graph; coloring; cyclic scheduling; totally unimodular; nearly bipartite graph; integer decomposition
90C10: Integer programming
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C15: Coloring of graphs and hypergraphs
Related Items
Tight relative t-designs on two shells in hypercubes, and Hahn and Hermite polynomials, On semidefinite programming bounds for graph bandwidth, Upper bounds for packings of spheres of several radii, Parameterized shifted combinatorial optimization, Semidefinite programming bounds for binary codes from a split Terwilliger algebra, Testing additive integrality gaps, Coloring fuzzy circular interval graphs, Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry, An axiomatic duality framework for the theta body and related convex corners, A numerical algorithm for block-diagonal decomposition of matrix \(*\)-algebras with application to semidefinite programming, The triple distribution of codes and ordered codes, Numerical block diagonalization of matrix \(\ast\)-algebras with application to semidefinite programming, Polyhedra with the integer Carathéodory property, Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem, The stable set polytope of quasi-line graphs, Commutative association schemes, Mixed integer reformulations of integer programs and the affine TU-dimension of a matrix, Graph bisection revisited, The unimodular intersection problem, On semidefinite programming relaxations of maximum \(k\)-section, On the number of matrices to generate a matrix \(\ast\)-algebra over the real field, The representation polyhedron of a semiorder., Box-total dual integrality, box-integrality, and equimodular matrices, Semidefinite programming for permutation codes, Colorings of \(k\)-balanced matrices and integer decomposition property of related polyhedra, High dimensional Hoffman bound and applications in extremal combinatorics, SDP Relaxations for Some Combinatorial Optimization Problems, Coloring Fuzzy Circular Interval Graphs, One-Dimensional Quantum Cellular Automata over Finite, Unbounded Configurations
