On generalized matching problems

DOI10.1016/0020-0190(81)90073-9zbMath0454.68077OpenAlexW1975356722MaRDI QIDQ1149783

David G. Kirkpatrick, Pavol Hell

Publication date: 1981

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(81)90073-9

zbMATH Keywords

NP-complete problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (15)

Packings by Complete Bipartite Graphs ⋮ Graph factors and factorization: 1985--2003: a survey ⋮ Maximum tree-packing in time \(O(n^{5/2})\) ⋮ The complexity of generalized domino tilings ⋮ Maximum tree-packing in time O(n5/2) ⋮ On caterpillar factors in graphs ⋮ Maximum packing for biconnected outerplanar graphs ⋮ A parameter linked with \(G\)-factors and the binding number ⋮ On the tree packing problem ⋮ Maximum packing for \(k\)-connected partial \(k\)-trees in polynomial time ⋮ Oriented star packings ⋮ On the complexity of digraph packings ⋮ Generalized partitions of graphs ⋮ Chain packing in graphs ⋮ Packings by cliques and by finite families of graphs

Cites Work

• On certain classes of fractional matchings
• F-factors of graphs: A generalized matching problem
• TWO THEOREMS IN GRAPH THEORY
• On the Computational Complexity of Combinatorial Problems
• An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
• Paths, Trees, and Flowers
• On the completeness of a generalized matching problem
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• The Factorization of Linear Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On generalized matching problems