On the complexity of a family of generalized matching problems
From MaRDI portal
Publication:1068535
DOI10.1016/0166-218X(85)90032-0zbMath0582.68014MaRDI QIDQ1068535
Alan P. Sprague, Ten-Hwang Lai
Publication date: 1985
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Unnamed Item
- Packings by cliques and by finite families of graphs
- NP-completeness of some generalizations of the maximum matching problem
- NP-complete scheduling problems
- The complexity of comparability graph recognition and coloring
- A decomposition theorem for partially ordered sets
- On the Complexity of General Graph Factor Problems
- A personnel assignment problem
- On Dynamic Programming Methods for Assembly Line Balancing
- Dynamic Programming Solution of Sequencing Problems with Precedence Constraints
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- Paths, Trees, and Flowers
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
