An NP-complete matching problem

DOI10.1016/0166-218X(80)90055-4MaRDI QIDQ1166935zbMATH OpenOpenAlexWikidataFDO

Authors David A. Plaisted, Shmuel Zaks

Publication date 1980

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218x(80)90055-4

zbMATH Keywords

polynomial time algorithmdegrees of the verticespartitions of the vertices of the graphrestricted form of the perfect matching problem for bipartite graphs

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)

Cites work

• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• Some Matching Problems for Bipartite Graphs
• The complexity of satisfiability problems
• The complexity of theorem-proving procedures

Cited in

(4)

• Acyclicity in edge-colored graphs
• An algebraic Monte-Carlo algorithm for the partition adjacency matrix realization problem
• Decomposition of university course timetabling. A systematic study of subproblems and their complexities
• On complexity of special maximum matchings constructing

This page was built for publication: An NP-complete matching problem

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