Library

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
  • 1
    Electronic Resource
    Electronic Resource
    Monotone switching circuits and boolean matrix product (1976)
    Springer
    Computing 16 (1976), S. 99-111 
    Details
    ISSN: 1436-5057
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung Wir untersuchen den Effekt lokaler Änderungen auf das Eingabe/Ausgabe-Verhalten monotoner Netzwerke. Wir wenden die Ergebnisse auf die Multiplikation Boolescher Matrizen an und zeigen, daß die Schulmethode für die Matrizenmultiplikation den alleinigen optimalen Schaltkreis liefert.
    Notes: Abstract We explore the concept of local transformations of monotone switching circuits, i.e. what kind of local changes in a network leave the input/output behavior invariant. We obtain several general theorems in this direction. We apply these results to boolean matrix product and prove that the school-method for matrix multiplication yields the unique monotone circuit.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02241983
    Library Location Call Number Volume/Issue/Year 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
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    On the embedding phase of the Hopcroft and Tarjan planarity testing algorithm (1996)
    Springer
    Algorithmica 16 (1996), S. 233-242 
    Details
    ISSN: 1432-0541
    Keywords: Planarity testing ; Topological embedding ; Planar embedding ; Combinatorial embedding
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We give a detailed description of the embedding phase of the Hopcroft and Tarjan planarity testing algorithm. The embedding phase runs in linear time. An implementation based on this paper can be found in [MMN].
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01940648
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    A Strong and Easily Computable Separation Bound for Arithmetic Expressions Involving Radicals (2000)
    Springer
    Algorithmica 27 (2000), S. 87-99 
    Details
    ISSN: 1432-0541
    Keywords: Key words. Exact geometric computation, Separation bound.
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. We consider arithmetic expressions over operators + , - , * , / , and $\sqrt[k]$ , with integer operands. For an expression E having value ξ , a separation bound sep (E) is a positive real number with the property that ξ\neq 0 implies |ξ| \geq sep (E) . We propose a new separation bound that is easy to compute and stronger than previous bounds.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s004530010005
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    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
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    A method for obtaining randomized algorithms with small tail probabilities (1996)
    Springer
    Algorithmica 16 (1996), S. 543-547 
    Details
    ISSN: 1432-0541
    Keywords: Las Vegas algorithms ; Randomized algorithm ; Tail probability
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We study strategies for converting randomized algorithms of the Las Vegas type into randomized algorithms with small tail probabilities.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01940879
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    Algorithms for routing in planar graphs (1986)
    Springer
    Acta informatica 23 (1986), S. 163-176 
    Details
    ISSN: 1432-0525
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Summary A routing problem is given by a planar graph G= (V, E) with a given embedding into the plane and a set Ne of nets. A net is a pair of points on the boundary of the infinite face. The goal is to find a set of pairwise edge-disjoint paths connecting the terminals of the various nets. We assume that the degree of every vertex not on the boundary of the infinite face is even and call such routing problems half-even. We show that one can decide in time O(bn) whether a half-even problem is solvable and that a solution can be constructed in time O(n 2). Here n=¦V¦ and b is the number of vertices on the boundary of the infinite face. If the routing problem is even, i.e. every cut has even free capacity, and G is a subgraph of the planar grid then a solution can be found in time O(n 3/2).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00289496
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    Van wijngaarden grammars and space complexity class EXSPACE (1977)
    Springer
    Acta informatica 8 (1977), S. 193-199 
    Details
    ISSN: 1432-0525
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Summary Top-down and bottom-up decision strategies for van Wijngaarden grammars led to type R and type L van Wijngaarden grammars. The corresponding language families are now shown to be equal and, furthermore, to equal EXSPACE. Thus, EXSPACE is characterised syntactically, and the closure properties of type L and type R languages are those of EXSPACE.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00289249
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    Potentiometrische Verfolgung der Thiosulfatbildung aus Alkalisulfid und schwefliger Säure (1934)
    Weinheim : Wiley-Blackwell
    Zeitschrift für die chemische Industrie 47 (1934), S. 134-139 
    Details
    ISSN: 0044-8249
    Keywords: Chemistry ; General Chemistry
    Source: Wiley InterScience Backfile Collection 1832-2000
    Topics: Chemistry and Pharmacology
    Additional Material: 1 Ill.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1002/ange.19340470905
    Library Location Call Number Volume/Issue/Year 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...