Titlebook: Algorithms - ESA ‘95; Third Annual Europea Paul Spirakis Conference proceedings 1995 Springer-Verlag Berlin Heidelberg 1995 Algorithmenanal

高兴一回

Average circuit depth and average communication complexity,cuits. By average time, we mean the time needed on a self-timed circuit, a model introduced recently by Jakoby, Reischuk, and Schindelhauer, [JRS94] in which gates compute their output as soon as it is determined (possibly by a subset of the inputs to the gate)..More precisely, we show that the aver

结果

Packing trees,en a tree ., find a packing, an allocation of its nodes to pages, which optimizes the cache performance. We investigate a model for tree access in which a node is accessed only via the path leading to it from the root. Two cost functions are considered: the total number of different pages visited in

评论者

Sometimes travelling is easy: The master tour problem,s called the . conditions) then the TSP is solvable in polynomial time..We deal with the problem of deciding for a given instance of the TSP, whether there is a renumbering of the cities such that the corresponding renumbered distance matrix fulfills the Kalmanson conditions. Two results are derived

sclera

Maximum skew-symmetric flows, parallel to the classical flow theory. We use the newly developed theory to extend, in a natural way, the blocking flow method of Dinitz to the skew-symmetric flow case. In the special case of the skew-symmetric flow problem that corresponds to cardinality matching, our algorithm is simpler and mor

要求比…更好

FAWN

On the all-pairs shortest path algorithm of Moffat and Takaoka, is shown to hold with high probability for a wide class of probability distributions on non-negatively weighted digraphs. We also prove that for a large class of probability distributions Ω(. log .) time is necessary with high probability to compute shortest path distances with respect to a single

起草

腐烂

喊叫

设想

Linear size binary space partitions for fat objects,ey are not extremely long and skinny) then the BSP has linear size and it can be constructed in . log..) time, where . is the number of objects. In fact, the method produces a linear size BSP for a more general class of scenes, namely scenes that satisfy the . condition—a property that we suspect ma