Packing subgraphs in a graph

DOI10.1016/0167-6377(82)90016-5MaRDI QIDQ1166429zbMATH OpenOpenAlexFDO

Authors Gérard Cornuéjols, David Hartvigsen, William R. Pulleyblank

Publication date 1982

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-6377(82)90016-5

zbMATH Keywords

matchingpolynomial algorithmtriangle packingmatching matroidnode partitionclique packinghypomatchable critical graph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17)

Cites work

• scientific article; zbMATH DE number 3496213 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Critical graphs, matchings and tours or a hierarchy of relaxations for the travelling salesman problem
• Paths, Trees, and Flowers

Cited in

(41)

• An improved approximation ratio for the jump number problem on interval orders
• Edge decompositions and rooted packings of graphs
• Matchings of cycles and paths in directed graphs
• Packings and perfect path double covers of maximal planar graphs
• Algorithms for finding an independent \(\{K_1,K_2\}\)-packing of maximum weight in a graph
• On the complexity of some edge-partition problems for graphs
• Fractional matchings and the Edmonds-Gallai theorem
• Independent packings in structured graphs
• Generalized partitions of graphs
• Packings by Complete Bipartite Graphs
• Clustering with lower-bounded sizes. A general graph-theoretic framework
• On the tree packing problem
• A refined analysis on the jump number problem of interval orders
• Good characterizations for some degree constrained subgraphs
• On the complexity of digraph packings
• Antifactors of regular bipartite graphs
• Induced graph packing problems
• The superstar packing problem
• Nash stability in fractional hedonic games with bounded size coalitions
• General factors of graphs
• Tackling the jump number of interval orders
• Ear-slicing for matchings in hypergraphs
• An extension of matching theory
• scientific article; zbMATH DE number 3150 (Why is no real title available?)
• On matroids induced by packing subgraphs
• Tractable cases of the extended global cardinality constraint
• The nonnegative node weight \(j\)-restricted \(k\)-matching problems
• Optimal general factor problem and jump system intersection
• Packings by cliques and by finite families of graphs
• An Edmonds-Gallai-type decomposition for the \(j\)-restricted \(k\)-matching problem
• Edge decompositions into two kinds of graphs
• Oriented star packings
• Graph factors and factorization: 1985--2003: a survey
• Gadget classification
• Chain packing in graphs
• Pareto optimality in coalition formation
• Packing triangles in low degree graphs and indifference graphs
• Packing $k$-Matchings and $k$-Critical Graphs
• Packing trees with constraints on the leaf degree
• Single-player and two-player buttons \& scissors games (extended abstract)
• Approximate triclique coloring for register allocation

This page was built for publication: Packing subgraphs in a graph

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