3 papers
math.CO2025
A Generalisation of Sperner's Theorem Using Weighted Chains
Yaël Dillies, Matthew Johnson, Aleksandra Kowalska
We find the (unique) largest subset of such that it contains no two elements, one of which is coordinatewise greater than the other, but strictly greater on at most…
cs.GT2023
Computing Balanced Solutions for Large International Kidney Exchange Schemes When Cycle Length Is Unbounded
Márton Benedek, Péter Biró, Gergely Csáji +3
In kidney exchange programmes (KEP) patients may swap their incompatible donors leading to cycles of kidney transplants. Nowadays, countries try to merge their national patient-don…
cs.CC2022
Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs
Matthew Johnson, Barnaby Martin, Siani Smith +3
We show that Edge Multiway Cut (also called Multiterminal Cut) and Node Multiway Cut are NP-complete on graphs of maximum degree (also known as subcubic graphs). This improves…