scientific article; zbMATH DE number 3637616

zbMath0409.90081MaRDI QIDQ4197644

William H. Cunningham, A. B. Marsh III

Publication date: 1978

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Computational Complexity Integer Programming Graph Theory Polyhedral Combinatorics Computational Experience Blossom Algorithm Linear Programming Duality Matching Polyhedron Optimum B- Matching Optium Matching Post-Optimality Primal Algorithm Total Dual Integrality

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Numerical mathematical programming methods (65K05) Integer programming (90C10) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Efficient dual simplex algorithms for the assignment problem, Solving matching problems with linear programming, Integer round-up property for the chromatic number of some $h$-perfect graphs, On the feedback vertex set polytope of a series-parallel graph, Constrained multi-object auctions and $b$-matching, Algorithms for finding k-best perfect matchings, New primal and dual matching heuristics, Node-Balancing by Edge-Increments, Excluded $t$-Factors in Bipartite Graphs: Unified Framework for Nonbipartite Matchings, Restricted 2-Matchings, and Matroids, Linear-Time Approximation for Maximum Weight Matching, Matching problems with generalized upper bound side constraints, Total dual integrality and integer polyhedra, On the complexity of recognizing integrality and total dual integrality of the $\{0,1/2\}$-closure, An algorithmic approach to dual integrality of matching and extensions, Stochastic packing integer programs with few queries, A weighted independent even factor algorithm, Total dual integrality and b-matchings, Bi-criteria and approximation algorithms for restricted matchings, Las Vegas RNC algorithms for unary weighted perfect matching and $T$-join problems, Optimal Matching Forests and Valuated Delta-Matroids, A weighted even factor algorithm, Proving total dual integrality with cross-free families—A general framework, Tight integral duality gap in the Chinese postman problem, A genuinely polynomial primal simplex algorithm for the assignment problem, A combinatoric interpretation of dual variables for weighted matching and $f$-factors, A min-max relation for stable sets in graphs with no odd-$K_ 4$, Facets of the independent path-matching polytope, An identity for matching and skew-symmetric determinant, The cyclical scheduling problem, Weighted restricted 2-matching, When Is the Matching Polytope Box-Totally Dual Integral?, A genetic-based framework for solving (multi-criteria) weighted matching problems., The Schrijver system of the flow cone in series-parallel graphs, On dual integrality in matching problems, Optimum matching forests II: General weights, Minimum cost $b$-matching problems with neighborhoods, Short proofs on the matching polyhedron, A Minimal Totally Dual Integral Defining System for the b-Matching Polyhedron, Total weak unimodularity: Testing and applications, Unnamed Item, Combinatorial analysis (nonnegative matrices, algorithmic problems), A note on matchings and separability, Some basic exchange properties in combinatorial optimization and their application to constructing the k-best solutions, Packings by cliques and by finite families of graphs, An integer analogue of Carathéodory's theorem, Fast algorithms for the undirected negative cost cycle detection problem