scientific article; zbMATH DE number 1397185
In many combinatorial optimization problems, it is worth considering the convex hull of the set of admissible solutions. Sometimes the combinatorial properties of this polytope are important in designing algorithms that solve the problem at hand. The article under review deals with the polytope \({\mathcal P_k}(G)\) of \(k\)-factors in a graph \(G\) and gives some necessary and sufficient combinatorial conditions for the adjacency of vertices of \({\mathcal P_k}(G)\). A sample result is as follows: If the symmetric difference of two \(k\)-factors induces either an even cycle or a pair of odd cycles with precisely one vertex in common, then the corresponding vertices of \({\mathcal P_k}(G)\) are adjacent. For the entire collection see [Zbl 0889.00011].
- Combinatorial structure and adjacency of vertices of polytope of \(b\)-factors
- A necessary condition for facetness of comb inequalities for a polytope of connected 2k-factors
- Adjacency of the best and second best valued solutions in combinatorial optimization problems
- scientific article; zbMATH DE number 1285729
- On the facets of combinatorial polytopes
- Adjacency of the best and second best valued solutions in combinatorial optimization problems
- Combinatorial structure and adjacency of vertices of polytope of \(b\)-factors
- A necessary condition for facetness of comb inequalities for a polytope of connected 2k-factors
- Determining adjacent vertices on assignment polytopes
- scientific article; zbMATH DE number 1285729 (Why is no real title available?)
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4936766)
