ALBERT

All Library Books, journals and Electronic Records Telegrafenberg

X
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
Filter
  • Dense network  (1)
  • Intersection reporting  (1)
  • Lower bounds  (1)
  • 1
    Electronic Resource
    Electronic Resource
    Algorithms for dense graphs and networks on the random access computer (1996)
    Springer
    Algorithmica 15 (1996), S. 521-549 
    Details
    ISSN: 1432-0541
    Keywords: Graph ; Network ; Algorithm ; Dense graph ; Dense network
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We improve upon the running time of several graph and network algorithms when applied to dense graphs. In particular, we show how to compute on a machine with word size λ=Ω (logn) a maximal matching in ann-vertex bipartite graph in timeO(n 2+n 2.5/λ)=O(n 2.5/logn), how to compute the transitive closure of a digraph withn vertices andm edges in timeO(n 2+nm/λ), how to solve the uncapacitated transportation problem with integer costs in the range [O.C] and integer demands in the range [−U.U] in timeO ((n 3 (log log/logn)1/2+n2 logU) lognC), and how to solve the assignment problem with integer costs in the range [O.C] in timeO(n 2.5 lognC/(logn/loglogn)1/4). Assuming a suitably compressed input, we also show how to do depth-first and breadth-first search and how to compute strongly connected components and biconnected components in timeO(nλ+n 2/λ), and how to solve the single source shortest-path problem with integer costs in the range [O.C] in time0 (n 2(logC)/logn). For the transitive closure algorithm we also report on the experiences with an implementation.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01940880
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Lower bounds for set intersection queries (1995)
    Springer
    Algorithmica 14 (1995), S. 154-168 
    Details
    ISSN: 1432-0541
    Keywords: Algorithms ; Arithmetic model ; Data structures ; Intersection reporting ; Lower bounds ; Memory restriction ; Set handling ; Upper bounds
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We consider the followingset intersection reporting problem. We have a collection of initially empty sets and would like to process an intermixed sequence ofn updates (insertions into and deletions from individual sets) andq queries (reporting the intersection of two sets). We cast this problem in thearithmetic model of computation of Fredman [F1] and Yao [Ya2] and show that any algorithm that fits in this model must take time Ω(q+n√q) to process a sequence ofn updates andq queries, ignoring factors that are polynomial in logn. We also show that this bound is tight in this model of computation, again to within a polynomial in logn factor, improving upon a result of Yellin [Ye]. Furthermore, we consider the caseq=O(n) with an additional space restriction. We only allow the use ofm memory locations, wherem ≤n3/2. We show a tight bound of Θ(n2/m1/3) for a sequence ofn operations, again ignoring the polynomial in logn factors.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01293666
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...