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
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, Solving matching problems with linear programming, Weighted Triangle-Free 2-Matching Problem with Edge-Disjoint Forbidden Triangles, THE PROPORTIONAL COLORING PROBLEM: OPTIMIZING BUFFERS IN RADIO MESH NETWORKS, Deciding Emptiness of the Gomory-Chvátal Closure is NP-Complete, Even for a Rational Polyhedron Containing No Integer Point, Scaling: A general framework, Separating clique tree and bipartition inequalities in polynomial time, Efficiently list‐edge coloring multigraphs asymptotically optimally, Advances on strictly \(\varDelta \)-modular IPs, Plowing with precedence in polynomial time, Constant-factor approximation algorithms for parity-constrained facility location and \(k\)-center, A traditional Benders' approach to sports timetabling, Valid Inequalities and Separation Algorithms for the Set Partitioning Problem, Unnamed Item, The multi‐purpose K‐drones general routing problem, Facet Generating Techniques, Unnamed Item, Densities, Matchings, and Fractional Edge-Colorings, An exact algorithm for solving the ring star problem, Classical cuts for mixed-integer programming and branch-and-cut, Fractional covers for forests and matchings, Extended formulations in combinatorial optimization, A decomposition algorithm for the ring spur assignment problem, Computational and statistical tradeoffs via convex relaxation, Branch and cut methods for network optimization, Extended formulations in combinatorial optimization, Unnamed Item, The ABACUS system for branch-and-cut-and-price algorithms in integer programming and combinatorial optimization, Min-Max K -vehicles windy rural postman problem, Provably good solutions for the traveling salesman problem, The convex hull of a linear congruence relation in zero-one variables, A new contraction technique with applications to congruency-constrained cuts, A branch-price-and-cut algorithm for the min-maxk-vehicle windy rural postman problem, On Four Problems in Graph Theory, Approximation algorithms in combinatorial scientific computing, Efficient Approximation Algorithms for Weighted $b$-Matching, Complete Description of Matching Polytopes with One Linearized Quadratic Term for Bipartite Graphs, On edge-colouring indifference graphs, A Characterization of Graphs with Fractional Total Chromatic Number Equal to, Popularity, Mixed Matchings, and Self-Duality, Fractionally Edge Colouring Graphs with Large Maximum Degree in Linear Time, Unnamed Item
