The complexity of matching with bonds

DOI10.1016/0020-0190(89)90021-5zbMATH Open0677.68053OpenAlexW2094880781MaRDI QIDQ1123620FDOQ1123620

Authors: Antonio Sassano, Manfred Padberg 

Publication date: 1989

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

Full work available at URL: https://doi.org/10.1016/0020-0190(89)90021-5

Recommendations

• On complexity of special maximum matchings constructing
• An unfeasible matching problem
• Maximum weight edge-constrained matchings
• Bottleneck subset-type restricted matching problems
• Maximum bounded \(H\)-matching is Max SNP-complete

zbMATH Keywords

computational complexityNP-hard problemmaximum-weight matchingrestricted matching problemsMatching with bonds

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) Complexity of computation (including implicit computational complexity) (03D15)

Cites Work

• Matching, Euler tours and the Chinese postman
• Title not available (Why is that?)
• Title not available (Why is that?)
• Some simplified NP-complete graph problems
• Some Matching Problems for Bipartite Graphs
• The complexity of restricted spanning tree problems

Cited In (4)

• The Complexity of Rationalizing Matchings
• Assignment problem with conflicts
• A constrained matching problem
• Computing Bond Types in Molecule Graphs

This page was built for publication: The complexity of matching with bonds

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