Matching with Multiple Bottlenecks: Parameterized Complexity and Approximation
This paper analyzes a matching problem in which the cost of each edge is a vector with $k$ components and provides various results including FPT-membership for parameters $k$ and $Z$ combined, as well as W[P]-membership and W[SAT]-hardness for each of the two parameters individually.
Jonas Friemel, Tilo Hoitz, Phillip Keldenich et al.
· 0 citations