Generalized edge packings

DOI10.1007/BF01587091MaRDI QIDQ1825138zbMATH OpenOpenAlexFDO

Authors Dominique De Werra

Publication date 1989

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01587091

zbMATH Keywords

augmenting chaingeneralized edge packingmaximum capacitated b-matchingmaximum odd chain packingnetwork flow techniquesnode coveringsundirected graph

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Deterministic network models in operations research (90B10) Integer programming (90C10) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Review text

In an undirected graph G a generalized edge packing is a collection of (not necessarily edge-disjoint) chains of odd length such that all chains have distinct endpoints. Previously, edge disjoint generalized edge packings, called odd chain packings, having been discussed by the author [Discrete Math. 51, 319-321 (1984; Zbl 0545.05049)] and \textit{W. R. Pulleyblank} and the author [Odd chain packings, to appear in Eur. J. Comb.]. In particular, finding a maximum odd chain packing is known to be polynomially reductible to finding a maximum capacitated b-matching. Obviously, matchings are odd chain packings. Here, basic properties of matchings are generalized to generalized edge packings, e.g. the augmenting chain theorem, matching matroids, and the Berge-Norman-Rabin theorem on matchings and node coverings. Although reformulations of some of the problems studied as capacitated b-matching problems are possible, simple and direct derivations independent of b-matching theory are given. For bipartite graphs, min-max results analogous to the theorem of König on matchings can be proved using elementary network flow techniques.

Recommendations

• Odd path packings
• Node coverings with odd chains
• On the use of augmenting chains in chain packings
• Partitions into odd chains
• Chain packing in graphs
• Integer Programming and Combinatorial Optimization
• Graph packings
• Efficient subgraphs packing
• Matchings of cycles and paths in directed graphs
• Optimal packing of induced stars in a graph

Cites work

• An Algorithm for a Minimum Cover of a Graph
• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• scientific article; zbMATH DE number 3325507 (Why is no real title available?)
• Odd path packings
• Partitions into odd chains
• The Factors of Graphs
• The Schrijver system of odd join polyhedra
• Variation on a theorem of König

Cited in

(3)

• On the use of augmenting chains in chain packings
• Node coverings with odd chains
• Partitions into odd chains

This page was built for publication: Generalized edge packings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1825138)