On cycle cones and polyhedra

DOI10.1016/0024-3795(89)90483-7MaRDI QIDQ5895283zbMATH OpenOpenAlexFDO

Authors William R. Pulleyblank, Collette R. Coullard

Publication date 1989

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0024-3795(89)90483-7

zbMATH Keywords

Halin graphspolynomial decomposition-based algorithmweighted girth problem

Mathematics Subject Classification ID

Paths and cycles (05C38) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Integer programming (90C10) Convex programming (90C25) Abstract computational complexity for mathematical programming problems (90C60)

Review text

Several variants of the weighted girth problem, some of which are NP-hard and some of which are solvable in polynomial time, and the polyhedra associated with each of these problems are considered. A polynomial decomposition-based algorithm for the weighted girth problem on Halin graphs is also described.

Recommendations

• On cycle cones and polyhedra
• The Circuit Polytope: Facets
• Algorithms for shortest paths and d-cycle problems
• scientific article; zbMATH DE number 1045607
• Minimum-weight subgraphs with unicyclic components and a lower-bounded girth

Cites work

• Corrigendum to our paper The ellipsoid method and its consequences in combinatorial optimization
• Halin graphs and the travelling salesman problem
• scientific article; zbMATH DE number 3904331 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3717152 (Why is no real title available?)
• scientific article; zbMATH DE number 3728302 (Why is no real title available?)
• scientific article; zbMATH DE number 3558962 (Why is no real title available?)
• scientific article; zbMATH DE number 3346402 (Why is no real title available?)
• scientific article; zbMATH DE number 3409134 (Why is no real title available?)
• On Linear Characterizations of Combinatorial Optimization Problems
• On the cone of nonnegative circuits
• Reductions to 1–matching polyhedra
• The traveling salesman problem in graphs with 3-edge cutsets

Cited in

(19)

• On the cut polyhedron.
• Circuit and bond polytopes on series-parallel graphs
• The Steiner cycle polytope
• On solving cycle problems with branch-and-cut: extending shrinking and exact subcycle elimination separation algorithms
• A combinatorial/geometric analysis of convex cyclofusene
• scientific article; zbMATH DE number 4133532 (Why is no real title available?)
• A Semiring on Convex Polygons and Zero-Sum Cycle Problems
• scientific article; zbMATH DE number 5704200 (Why is no real title available?)
• The Circuit Polytope: Facets
• scientific article; zbMATH DE number 1045607 (Why is no real title available?)
• Minimum-weight subgraphs with unicyclic components and a lower-bounded girth
• On cycle cones and polyhedra
• Facets of the p-cycle polytope
• Cycle selections
• Cycle algebras and polytopes of matroids
• On the cylinder conjecture
• Formulations and algorithms for the simple cycle problem
• Short cycles of Poncelet's conics
• Facets of the (s,t)-p-path polytope

This page was built for publication: On cycle cones and polyhedra

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5895283)