Odd Minimum Cut-Sets and b-Matchings
From MaRDI portal
Publication:3965907
DOI10.1287/moor.7.1.67zbMath0499.90056OpenAlexW2123805664MaRDI QIDQ3965907
No author found.
Publication date: 1982
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/moor.7.1.67
cutting-planesfinite undirected graphconstraint identificationb-matching problemsblossom constrainteven and odd verticesminimum cut-set of odd cardinalitynonnegative edge-weights
Numerical mathematical programming methods (65K05) Integer programming (90C10) Combinatorial aspects of matroids and geometric lattices (05B35)
Related Items (only showing first 100 items - show all)
Polyhedral proof methods in combinatorial optimization ⋮ A separation algorithm for the matchable set polytope ⋮ Edge-colouring of join graphs ⋮ Exact approaches for the orderly colored longest path problem: performance comparison ⋮ Decomposition and optimization over cycles in binary matroids ⋮ On the complexity of some basic problems in computational convexity. I. Containment problems ⋮ Two-phase branch-and-cut for the mixed capacitated general routing problem ⋮ A branch-and-cut framework for the consistent traveling salesman problem ⋮ Edge-colouring of joins of regular graphs. I ⋮ A branch-and-cut algorithm for the profitable windy rural postman problem ⋮ New techniques for cost sharing in combinatorial optimization games ⋮ A construction for binary matroids ⋮ Lower bounds and heuristics for the windy rural postman problem ⋮ The traveling purchaser problem, with multiple stacks and deliveries: a branch-and-cut approach ⋮ Improved bounds for large scale capacitated arc routing problem ⋮ The ring spur assignment problem: new formulation, valid inequalities and a branch-and-cut approach ⋮ Generalized multiple depot traveling salesmen problem -- polyhedral study and exact algorithm ⋮ Minimizing submodular functions over families of sets ⋮ Polyhedral analysis and a new algorithm for the length constrained \(K\)-drones rural postman problem ⋮ On two-connected subgraph polytopes ⋮ Revisiting a cutting-plane method for perfect matchings ⋮ The max-cut problem on graphs not contractible to \(K_ 5\) ⋮ A branch-and-cut algorithm for the equicut problem ⋮ Incorporating facet-inducing inequalities into graphical-construct-based Lagrangian relaxation methodologies ⋮ Optimizing over the first Chvátal closure ⋮ Co-density and fractional edge cover packing ⋮ Modeling and solving the mixed capacitated general routing problem ⋮ On approximately fair cost allocation in Euclidean TSP games ⋮ On the complexity of recognizing integrality and total dual integrality of the \(\{0,1/2\}\)-closure ⋮ Postman problems on series-parallel mixed graphs ⋮ Edge-colouring graphs with bounded local degree sums ⋮ On edge-colouring indifference graphs ⋮ When the Gomory-chvátal closure coincides with the integer hull ⋮ The generalized arc routing problem ⋮ Improved lower bounds and exact algorithm for the capacitated arc routing problem ⋮ A simple minimum \(T\)-cut algorithm ⋮ A compact linear program for testing optimality of perfect matchings. ⋮ Facet identification for the symmetric traveling salesman polytope ⋮ The ellipsoid method and its consequences in combinatorial optimization ⋮ On the cut polyhedron. ⋮ Tree metrics and edge-disjoint \(S\)-paths ⋮ Undirected postman problems with zigzagging option: a cutting-plane approach ⋮ Facets from gadgets ⋮ The capacitated arc routing problem with intermediate facilities ⋮ On the transportation problem with market choice ⋮ Compact systems for T-join and perfect matching polyhedra of graphs with bounded genus ⋮ A polyhedral approach to edge coloring ⋮ A polyhedral approach to an integer multicommodity flow problem ⋮ Euclidean semi-matchings of random samples ⋮ Expressing combinatorial optimization problems by linear programs ⋮ Exploiting planarity in separation routines for the symmetric traveling salesman problem ⋮ Computing girth and cogirth in perturbed graphic matroids ⋮ Exact methods for solving the elementary shortest and longest path problems ⋮ Multiple depot ring star problem: a polyhedral study and an exact algorithm ⋮ Solving combinatorial optimization problems using Karmarkar's algorithm ⋮ An exact solution method for quadratic matching: the one-quadratic-term technique and generalisations ⋮ On the complexity of the separation problem for rounded capacity inequalities ⋮ Matching theory -- a sampler: From Dénes König to the present ⋮ On the \({\mathcal {H}}\)-free extension complexity of the TSP ⋮ A cutting plane algorithm for the windy postman problem ⋮ The hierarchical mixed rural postman problem: polyhedral analysis and a branch-and-cut algorithm ⋮ A comparison of two edge-coloring formulations ⋮ Fractionally total colouring \(G_{n,p}\) ⋮ Robust branch-and-cut-and-price for the capacitated vehicle routing problem ⋮ Lower and upper bounds for the mixed capacitated arc routing problem ⋮ A comparison of two different formulations for arc routing problems on mixed graphs ⋮ On the domino-parity inequalities for the STSP ⋮ Solving the length constrained \(K\)-drones rural postman problem ⋮ Coordinating resources in Stackelberg security games ⋮ Parity polytopes and binarization ⋮ The Cutting Plane Method is Polynomial for Perfect Matchings ⋮ Separation routine and extended formulations for the stable set problem in claw-free graphs ⋮ An \(\tilde{O}(m^{2}n)\) algorithm for minimum cycle basis of graphs ⋮ Minimizing the stabbing number of matchings, trees, and triangulations ⋮ OAR lib: an open source arc routing library ⋮ Extended formulations for radial cones ⋮ Optimal edge-coloring with edge rate constraints ⋮ Separating valid odd-cycle and odd-set inequalities for the multiple depot vehicle scheduling problem ⋮ \(\{ 0,\frac12\}\)-Chvátal-Gomory cuts ⋮ Fractional matching preclusion number of graphs and the perfect matching polytope ⋮ The optimal path-matching problem ⋮ Corrigendum to our paper The ellipsoid method and its consequences in combinatorial optimization ⋮ A cutting plane algorithm for minimum perfect 2-matchings ⋮ New inequalities for the general routing problem ⋮ Facets and algorithms for capacitated lot sizing ⋮ Four problems on graphs with excluded minors ⋮ Minimizing symmetric submodular functions ⋮ An efficient approximation algorithm for the survivable network design problem ⋮ Solving the prize-collecting rural postman problem ⋮ The rural postman problem with deadline classes ⋮ Recent trends in combinatorial optimization ⋮ A GRASP heuristic for the mixed Chinese postman problem ⋮ A branch-and-cut algorithm for the capacitated profitable tour problem ⋮ Edge coloring nearly bipartite graphs ⋮ A linear programming formulation of Mader's edge-disjoint paths problem ⋮ A primal dual integer programming algorithm ⋮ Solution of large-scale symmetric travelling salesman problems ⋮ A fast algorithm for minimum weight odd circuits and cuts in planar graphs ⋮ A cutting plane algorithm for the capacitated arc routing problem ⋮ Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles
This page was built for publication: Odd Minimum Cut-Sets and b-Matchings
