The complexity of matching with bonds

DOI10.1016/0020-0190(89)90021-5MaRDI QIDQ1123620zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 3522018 (Why is no real title available?)
• Matching, Euler tours and the Chinese postman
• Some Matching Problems for Bipartite Graphs
• Some simplified NP-complete graph problems
• 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)