【摘 要】
：
Kidney exchange programs have been established in several countries to organize kidney exchanges between incompatible patient-donor pairs.The core of these
【机 构】
：
School of Information Science and Engineering,Central South University,Changsha 410083,China
【出 处】
：
2015全国理论计算机科学学术年会
论文部分内容阅读
Kidney exchange programs have been established in several countries to organize kidney exchanges between incompatible patient-donor pairs.The core of these programs are algorithms to solve kidney exchange problem, which can be modeled as finding a maximum weight packing of vertex-disjoint cycles with length at most some small constant L (typically 2 ≤ L ≤ 5) in a directed graph.In generally, the objective function is maximizing the number of possible kidney transplants.In this paper, we study the random methods for the kidney exchange problem involving only 2-cycle and 3-cycle exchanges.First, we formal the kidney exchange problem as a parameterized model.And then we propose a randomized parameterized algorithm of running time O*(5.63k3 · 22k2) by randomly partitioning the vertices.Last, by using the random divide-and-conquer technique, another randomized algorithm of running time O* (k2[log k2/2.k3[logk3]/2.42k3.22k2) is given for the parameterized kidney problem.Moreover,our randomized algorithms can be extended to solve the general kidney exchange problem.
其他文献
The on-line load balancing is one of the most important problems in the field of algorithm design.Taking into account the practical application scenarios, t
The individual household electricity consumption is major part of the city in the electricity market.The accurate prediction of household power load is very
Text detection is the basis of Optical Character Recognition (OCR) and text information retrieval from natural images.The intrinsic variability of text rend
副本技术广泛应用于云计算及分布式系统中，合理的数据副本放置是降低网络运行成本的重要手段，也是副本技术的核心问题.副本更新是针对网络中数据访问请求的动态变化而进行
在现代基于虚拟化的数据中心上,虚拟机分配是实现云中资源有效调度的首要考虑.在云系统中,大数据被划分成多个数据存储在数据中心的数据结点上等待虚拟机处理.此时,不仅
A color image encryption algorithm based on modified RC4 and chaotic maps is proposed in this paper.The classic RC4 algorithm is modified in cryptography, a
Document databases are becoming popular, but how to present complex document query to obtain useful information from the document remains an important topic
片上网络作为一种将大量嵌入式内核集成到单个晶圆片上的可行性技术，与传统片上系统相比，更能应对未来需要更大规模集成内核的挑战，从而得到了更广泛的应用。然而，目前大多数
随着电子商务和金融软件应用日益广泛,提高这类软件系统的可靠性和安全性就显得特别重要。虽然能够提高这类软件可靠性的事务处理技术早在数据库管理系统中普遍使用,近几
为了降低图像轮廓检测中纹理对检测结果的影响，提出一种基于双尺度高斯核方向导数滤波器的图像轮廓检测算法。结合大小两个尺度高斯核方向导数滤波器构造图像的边缘强度映