The Wheels of the Orthogonal Latin Squares Polytope: Classification and Valid Inequalities

G. Appa (), D. Magos () and I. Mourtos ()
Additional contact information
G. Appa: London School of Economics
D. Magos: Technological Educational Institute of Athens
I. Mourtos: University of Patras

Journal of Combinatorial Optimization, 2005, vol. 10, issue 4, No 5, 365-389

Abstract: Abstract A wheel in a graph G(V,E) is an induced subgraph consisting of an odd hole and an additional node connected to all nodes of the hole. In this paper, we study the wheels of the intersection graph of the Orthogonal Latin Squares polytope (P I ). Our work builds on structural properties of wheels which are used to categorise them into a number of collectively exhaustive classes. These classes give rise to families of inequalities that are valid for P I and facet-defining for its set-packing relaxation. The classification introduced allows us to establish the cardinality of the whole wheel class and determine the range of the coefficients of any variable included in a lifted wheel inequality. Finally, based on this classification, a constant-time recognition algorithm for wheel-inducing circulant matrices, is introduced.

Keywords: Orthogonal Latin Squares; wheel inequality; facet (search for similar items in EconPapers)
Date: 2005
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-005-4924-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:10:y:2005:i:4:d:10.1007_s10878-005-4924-4

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-005-4924-4

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().