MAXIMUM WEIGHT CYCLE PACKING IN DIRECTED GRAPHS, WITH APPLICATION TO KIDNEY EXCHANGE PROGRAMS

DOI10.1142/S1793830909000373zbMath1194.05121OpenAlexW2026655915MaRDI QIDQ5189989

David F. Manlove, Romeo Rizzi, Péter Biró

Publication date: 11 March 2010

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s1793830909000373

zbMATH Keywords

approximation algorithmdirected graphexact algorithmtriangle packingAPX-completenesskidney paired donation

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Directed graphs (digraphs), tournaments (05C20) Medical epidemiology (92C60) Signed and weighted graphs (05C22)

Related Items (14)

House-swapping with divorcing and engaged pairs ⋮ Randomized parameterized algorithms for the kidney exchange problem ⋮ The core of housing markets from an agent's perspective: Is it worth sprucing up your home? ⋮ Maximising expectation of the number of transplants in kidney exchange programmes ⋮ A polyhedral study of the cardinality constrained multi-cycle and multi-chain problem on directed graphs ⋮ The kidney exchange problem: how hard is it to find a donor? ⋮ Adapting a kidney exchange algorithm to align with human values ⋮ On the kidney exchange problem: cardinality constrained cycle and chain problems on directed graphs: a survey of integer programming approaches ⋮ Computing the Deficiency of Housing Markets with Duplicate Houses ⋮ Branch-and-cut-and-price for the cardinality-constrained multi-cycle problem in kidney exchange ⋮ Hardness results for stable exchange problems ⋮ An improved 2-agent kidney exchange mechanism ⋮ Mix and match: a strategyproof mechanism for multi-hospital kidney exchange ⋮ New insights on integer-programming models for the kidney exchange problem

Uses Software

• LEDA

Cites Work

• Unnamed Item
• Pairwise kidney exchange
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• An improved randomized approximation algorithm for maximum triangle packing
• Optimization, approximation, and complexity classes
• Packing triangles in bounded degree graphs.
• Packing triangles in low degree graphs and indifference graphs
• An approximation algorithm for maximum triangle packing
• On Local Search for Weighted k-Set Packing
• Kidney Exchange
• On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
• Paths, Trees, and Flowers

This page was built for publication: MAXIMUM WEIGHT CYCLE PACKING IN DIRECTED GRAPHS, WITH APPLICATION TO KIDNEY EXCHANGE PROGRAMS