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
approximation algorithmdirected graphexact algorithmtriangle packingAPX-completenesskidney paired donation
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)
Uses Software
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