Fractional covers for forests and matchings

DOI10.1007/BF02591725zbMath0532.90073MaRDI QIDQ3315281

Laurence A. Wolsey, Manfred W. Padberg

Publication date: 1984

Published in: Mathematical Programming (Search for Journal in Brave)

zbMATH Keywords

combinatorial optimizationellipsoid algorithmpolynomial algorithmsforestsspanning treesfinite undirected graphb- matchingsfractional covering problems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Integer programming (90C10) Deterministic network models in operations research (90B10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (7)

Improving a family of approximation algorithms to edge color multigraphs ⋮ Strength of a graph and packing of trees and branchings ⋮ Finding and Recognizing Popular Coalition Structures ⋮ Packing and covering with integral feasible flows in integral supply-demand networks ⋮ Densities, Matchings, and Fractional Edge-Colorings ⋮ Clique-connecting forest and stable set polytopes ⋮ Packing algorithms for arborescences (and spanning trees) in capacitated graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The ellipsoid method and its consequences in combinatorial optimization
• Methods of Nonlinear 0-1 Programming
• Khachiyan’s algorithm for linear programming
• Odd Minimum Cut-Sets and b-Matchings
• Selected Applications of Minimum Cuts in Networks
• Minimum cuts and related problems
• Network Flows, Minimum Coverings, and the Four-Color Conjectures
• Maximum matching and a polyhedron with 0,1-vertices
• Blocking and anti-blocking pairs of polyhedra

This page was built for publication: Fractional covers for forests and matchings