Improved algorithms for path, matching, and packing problems
Improved algorithms for path, matching, and packing problems
复制标题
DOI：
--
复制
发表时间：
2007-01
期刊：
影响因子：
--
通讯作者：
Jianer Chen;Songjian Lu;S. Sze;Fenghui Zhang
中科院分区：
文献类型：
--
作者：
Jianer Chen;Songjian Lu;S. Sze;Fenghui Zhang
改进的随机和确定性算法的路径，匹配和包装问题。我们的随机化算法是基于分治技术，并改善以前的最好的算法，这些问题。例如，对于k-PATH问题，我们的随机化算法在时间O（4kk3.42m）和空间O（nklogk + m）上运行，改进了以前在时间O（5.44kkm）和空间O（2kkn + m）上运行的问题的最佳随机化算法。为了实现改进的确定性算法，我们研究了一些以前提出的去随机化方案，也开发了一个新的去随机化方案。这些研究产生了一些确定性算法：一个时间为O（4k+o（k）m）的k路径问题，一个时间为O（2.803kknlog2 n）的3-D匹配问题，和一个时间为O（43 k +o（k）n）的3-SET包装问题。所有这些都大大改善了以往的最佳算法的问题。
Improved randomized and deterministic algorithms are presented for PATH, MATCHING, and PACKING problems. Our randomized algorithms are based on the divide-and-conquer technique, and improve previous best algorithms for these problems. For example, for the k-PATH problem, our randomized algorithm runs in time O(4kk3.42m) and space O(nklogk + m), improving the previous best randomized algorithm for the problem that runs in time O(5.44kkm) and space O(2kkn + m). To achieve improved deterministic algorithms, we study a number of previously proposed de-randomization schemes, and also develop a new derandomization scheme. These studies result in a number of deterministic algorithms: one of time O(4k+o(k)m) for the k-PATH problem, one of time O(2.803kk nlog2 n) for the 3-D MATCHING problem, and one of time O(43k+o(k)n) for the 3-SET PACKING problem. All these significantly improve previous best algorithms for the problems.