More facets from fences for linear ordering and acyclic subgraph polytopes

DOI10.1016/0166-218X(92)00151-BzbMath0817.52017OpenAlexW1976786056MaRDI QIDQ1326756

Jon Lee, Janny M. Y. Leung

Publication date: 1 August 1995

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

Full work available at URL: https://doi.org/10.1016/0166-218x(92)00151-b

zbMATH Keywords

acyclic subgraphfacetlinear ordering polytope

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Combinatorial optimization (90C27) Directed graphs (digraphs), tournaments (05C20)

Related Items

Applying mod-\(k\)-cuts for solving linear ordering problems, A survey on the linear ordering problem for weighted or unweighted tournaments, On non-\(\{0,{1\over 2},1\}\) extreme points of the generalized transitive tournament polytope, Probabilistic biclassification and random variable representations, On the partial order polytope of a digraph, The interval order polytope of a digraph, General transitivity conditions for fuzzy reciprocal preference matrices., Revised GRASP with path-relinking for the linear ordering problem, Facet Generating Techniques, Facets of linear signed order polytopes., Weak order polytopes., Fence facets from non-regular graphs for the linear ordering polytope, The strongest facets of the acyclic subgraph polytope are unknown, Rank aggregation in cyclic sequences, An updated survey on the linear ordering problem for weighted or unweighted tournaments, The biorder polytope, Determining the automorphism group of the linear ordering polytope, Facets of the linear ordering polytope: a unification for the fence family through weighted graphs, How to recycle your facets, A branch and bound algorithm for the minimum storage-time sequencing problem, Weighted graphs defining facets: A connection between stable set and linear ordering polytopes, Combinatorial optimization and small polytopes, Workload balancing and loop layout in the design of a flexible manufacturing system, Unnamed Item, Signed orders, choice probabilities, and linear polytopes

Cites Work

• A spectral approach to polyhedral dimension
• A spectral method for concordant polyhedral faces
• Induced binary probabilities and the linear ordering polytope: A status report
• Polyhedral structure and properties of a model for layout design
• A necessary but insufficient condition for the stochastic binary choice problem
• Facet Generating Techniques
• On the acyclic subgraph polytope
• Facets of the linear ordering polytope
• Finding a minimum feedback arc set in reducible flow graphs
• Optimal Weighted Ancestry Relationships
• Unnamed Item
• Unnamed Item
• Unnamed Item