The problem of the edge coloring partial k ‐tree into two partial p ‐ and q ‐trees with p , q < k is considered. An algorithm is provided to construct such a coloring with p + q = k . Usefulness of this result i...
详细信息
The problem of the edge coloring partial k ‐tree into two partial p ‐ and q ‐trees with p , q < k is considered. An algorithm is provided to construct such a coloring with p + q = k . Usefulness of this result in a Lagrangian decomposition framework to solve certain combinatorial optimization problems is discussed. ® 1997 John Wiley & Sons, Inc.
For a given set S of nonnegative integers the partitioning problem asks for a partition of S into two disjoint subsets S 1 and S 2 such that the sum of elements in S 1 is equal to the sum of elements in S 2 . If addit...
详细信息
Since the invention of the pairing heap by Fredman, Sedgewick, Sleator, and Tarjan [8], it has been an open question whether this or any other simple “self-adjusting” heap supports decrease-key operations in \(\math...
详细信息
Since the invention of the pairing heap by Fredman, Sedgewick, Sleator, and Tarjan [8], it has been an open question whether this or any other simple “self-adjusting” heap supports decrease-key operations in \(\mathrm{O}(\log\log n)\) time, where \(n\) is the number of heap items. Using powerful new techniques, we answer this question in the affirmative. We prove that both slim and smooth heaps, recently introduced self-adjusting heaps, support heap operations in the following amortized time bounds: \(\mathrm{O}(\log n)\) for delete-min and delete, \(\mathrm{O}(\log\log n)\) for decrease-key, and \(\mathrm{O}(1)\) for all other heap operations, including insert and meld, where \(n\) is the number of heap items that are eventually deleted: Items inserted but never deleted do not count in the bounds. We also analyze the multipass pairing heap, a variant of pairing heaps. For this heap implementation, we obtain the same bounds except for decrease-key, for which our bound is \(\mathrm{O}(\log\log n\cdot\log\log\log n)\), where again items that are never deleted do not count in \(n\). Our bounds significantly improve the best previously known bounds for all three data structures. For slim and smooth heaps our bounds are tight, since they match lower bounds of Iacono and Özkan [13].
暂无评论