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
  • Articles  (127)
  • stability  (68)
  • Parallel algorithms  (59)
  • Drosophila
  • Springer  (127)
  • Computer Science  (127)
Collection
  • Articles  (127)
Source
Keywords
Publisher
Years
Topic
  • 1
    Electronic Resource
    Electronic Resource
    On the stability of multistep formulas for Volterra integral equations of the second kind (1980)
    Springer
    Computing 24 (1980), S. 341-347 
    Details
    ISSN: 1436-5057
    Keywords: Numerical analysis ; Volterra integral equations of the second kind ; stability
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung Ziel dieser Arbeit ist es, die Stabilitätseigenschaften einer Klasse Volterrascher Integralgleichungen zweiter Art zu untersuchen. Unsere Behandlung ist der üblichen Stabilitätsanalyse ähnlich, in der die Kernfunktionen zu einer im voraus beschränkten Klasse von Testfunktionen gehören. Wir haben die Klasse der “endlich zerlegbaren” Kerne betrachtet. Stabilitätsbedingungen werden abgeleitet und verglichen mit den Bedingungen für die einfache Testgleichung. Es zeigt sich, daß die neuen Kriteria einschränkender sind als die konventionellen Bedingungen. Der praktische Wert wird getestet durch numerische Experimente mit der Trapezregel.
    Notes: Abstract The purpose of this paper is to analyse the stability properties of a class of multistep methods for second kind Volterra integral equations. Our approach follows the usual analysis in which the kernel function is a priori restricted to a special class of test functions. We consider the class of finitely decomposable kernels. Stability conditions will be derived and compared with those obtained with the simple test equation. It turns out that the new criteria are more severe than the conventional conditions. The practical value is tested by numerical experiments with the trapezoidal rule.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02237819
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Box schemes on quadrilateral meshes (1993)
    Springer
    Computing 51 (1993), S. 271-292 
    Details
    ISSN: 1436-5057
    Keywords: 65N15 ; 65N99 ; 35A40 ; Box method ; boundary value problem ; finite volume method ; variational formulation ; stability ; error bounds
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung Box-Methoden (Finite-Volumen-Methoden) sind verbreitete Verfahren zur Lösung physikalischer Erhaltungsgleichungen, insbesondere in der Strömungsmechanik. In dieser Arbeit werden zwei Methoden für elliptische Differentialgleichungen untersucht, die Diagonal-Boxen und die Schwerpunkt-Boxen. Da die Box-Methoden im Sinne von Petrov-Galerkin-Verfahren interpretiert werden können, erhält man vergleichbar zur Finiten-Element-Methode eine variationsrechnerische Stabilitäts- und Fehleranalyse. Damit werdenO(h)- undO(h 2)-Fehlerabschätzungen hergeleitet. Lokale Eigenwertprobleme führen zu Stabilitätsaussagen. Allerdings ergibt sich eine Abhängigkeit von der Anzahl und Art gestörter Vierecke. Insbesondere die Diagonal-Boxen sind anfällig für lokale Störungen.
    Notes: Abstract Box schemes (finite volume methods) are widely used in fluiddynamics, especially for the solution of conservation laws. In this paper two box-schemes for elliptic equations are analysed with respect to quadrilateral meshes. Using a variational formulation, we gain stability theorems for two different box methods, namely the so-called diagonal boxes and the centre boxes. The analysis is based on an elementwise eigenvalue problem. Stability can only be guaranteed under additional assumptions on the geometry of the quadrilaterals. For the diagonal boxes unsuitable elements can lead to global instabilities. The centre boxes are more robust and differ not so much from the finite element approach. In the stable case, convergence results up to second order are proved with well-known techniques.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02238536
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    A note on stability investigations for Rosenbrock-type methods for quasilinear-implicit differential equations (1996)
    Springer
    Computing 56 (1996), S. 47-59 
    Details
    ISSN: 1436-5057
    Keywords: 65 L 05 ; Rosenbrock-type methods ; quasilinear-implicit differential equations ; stability
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung Bei der Lösung quasilinear-impliziter ODEs mittels Rosenbrock-Typ-Methoden können trotz guter Stabilitätseigenschaften (A- bzw. L-Stabilität) des Grundverfahrens Stabilitätsprobleme auftreten. Diese Schwierigkeiten sind auf Ungenauigkeiten bei der Berechnung künstlich eingeführter Komponenten (Überführung in DAEs) zurückzuführen. Die Arbeit untersucht die Ursachen für diese Effekte und zeigt Möglichkeiten, diese zu überwinden.
    Notes: Abstract The solution of quasilinear-implicit ODEs using Rosenbrock type methods may suffer from stability problems despite stability properties such as A-stability or L-stability, respectively. These problems are caused by inexact computation of artificial introduced components (transformation to DAE system). The paper investigates the source of the numerical difficulties and shows modifications to overcome them.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02238291
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    A bifurcation analysis of the nonlinear parametric programming problem (1990)
    Springer
    Mathematical programming 47 (1990), S. 117-141 
    Details
    ISSN: 1436-4646
    Keywords: Bifurcation ; singularity ; parametric programming ; stability
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The structure of solutions to the nonlinear parametric programming problem with a one dimensional parameter is analyzed in terms of the bifurcation behavior of the curves of critical points and the persistence of minima along these curves. Changes in the structure of the solution occur at singularities of a nonlinear system of equations motivated by the Fritz John first-order necessary conditions. It has been shown that these singularities may be completely partitioned into seven distinct classes based upon the violation of one or more of the following: a complementarity condition, a constraint qualification, and the nonsingularity of the Hessian of the Lagrangian on a tangent space. To apply classical bifurcation techniques to these singularities, a further subdivision of each case is necessary. The structure of curves of critical points near singularities of lowest (zero) codimension within each case is analyzed, as well as the persistence of minima along curves emanating from these singularities. Bifurcation behavior is also investigated or discussed for many of the subcases giving rise to a codimension one singularity.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580856
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Characterization of stable matchings as extreme points of a polytope (1992)
    Springer
    Mathematical programming 54 (1992), S. 57-67 
    Details
    ISSN: 1436-4646
    Keywords: Matchings ; stability ; extreme points ; polytope
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The purpose of this paper is to extend a modified version of a recent result of Vande Vate (1989) which characterizes stable matchings as the extreme points of a certain polytope. Our proofs are simpler and more transparent than those of Vande Vate.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01586041
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    Quantitative stability of variational systems: III.ε-approximate solutions (1993)
    Springer
    Mathematical programming 61 (1993), S. 197-214 
    Details
    ISSN: 1436-4646
    Keywords: Epi-convergence ; epi-distance ; stability ; convex optimization ; approximate solutions ; subgradients ; level sets
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We prove that theε-optimal solutions of convex optimization problems are Lipschitz continuous with respect to data perturbations when these are measured in terms of the epi-distance. A similar property is obtained for the distance between the level sets of extended real valued functions. We also show that these properties imply that theε-subgradient mapping is Lipschitz continuous.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582147
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    The spectral accuracy of a fully-discrete scheme for a nonlinear third order equation (1990)
    Springer
    Computing 44 (1990), S. 187-196 
    Details
    ISSN: 1436-5057
    Keywords: 65M10 ; Spectral method ; stability ; stability threshold
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung Zur numerischen Lösung einer nichtlinearen Differentialgleichung dritter Ordnung, herrührend aus einem Strömungsproblem bei Gasteilchen, wird ein zeitdiskreter Pseudo-spektral-Algorithmus vorgeschlagen. Stabilität und Konvergenz des neuen Differenzenverfahrens werden analysiert. Numerische Vergleiche mit bestehenden Differenzenschemata sprechen klar zugunsten des neuen Verfahrens.
    Notes: Abstract A time-discrete pseudospectral algorithm is suggested for the numerical solution of a nonlinear third order equation arising in fluidization. The nonlinear stability and convergence of the new scheme are analyzed. Numerical comparisons with available finite-difference methods are also reported which clearly indicate the superiority of the new scheme.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02262215
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    Second-order explicit characteristic difference schemes for quasilinear hyperbolic systems (1985)
    Springer
    Computing 35 (1985), S. 85-91 
    Details
    ISSN: 1436-5057
    Keywords: 65M05 ; 65M10 ; 65M25 ; Second order ; characteristic difference schemes ; quasilinear hyperbolic systems ; stability
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung Wir stellen ein Charakteristikenverfahren zweiter Ordnung für die numerische Lösung der Anfangswertaufgabe von quasilinearen hyperbolischen Systemen vor und beweisen die Stabilität des Verfahrens für Systeme mit konstanten Koeffizienten.
    Notes: Abstract We present two-step, second-order explicit characteristic difference schemes for the numerical solution of initialvalue problems for quasilinear hyperbolic system and show that the method is stable for systems with constant coefficients.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02240149
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    Nichtlineare Stabilität und Phasenuntersuchung adaptiver Nyström-Runge-Kutta-Methoden (1985)
    Springer
    Computing 35 (1985), S. 325-344 
    Details
    ISSN: 1436-5057
    Keywords: 65L05 ; Numerical analysis ; Nyström methods ; stiff problems ; stability
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Abstract The stability of adaptive Nyström-Runge-Kutta procedures is studied for a wide class of nonlinear stiff systems of second order differential equations. We show that for a large class of semi-discrete hyperbolic and parabolic problems the restriction of the stepsize is not due to the stiffness of the differential equation. Furthermore we use the scalar test equation $$y'' = - \omega ^2 y + q \cdot e^{iv(t - t_0 )} $$ to derive conditions which ensure that the numerical forced oscillation is in phase with the analytical forced oscillation. The order of adaptive Nyström-Runge-Kutta methods (with a stability-matrix based on a diagonal Padéapproximation) for which the forced oscillation is in phase with its analytical counterpart cannot be greater than two. This barrier of order is not true forr-stage implicit Nyström methods of orderp=2r.
    Notes: Zusammenfassung Für eine umfangreiche Klasse nichtlinearer steifer Differentialgleichungssysteme zweiter Ordnung wird die Stabilität adaptiver Nyström-Runge-Kutta-Verfahren untersucht. Wir zeigen, daß für eine große Klasse semidiskretisierter hyperbolischer und parabolischer Probleme die Restriktion der Schrittweite unabhängig von der Steifheit des Differentialgleichungssystems ist. Weiterhin verwenden wir die skalare Testgleichung $$y'' = - \omega ^2 y + q \cdot e^{iv(t - t_0 )} $$ und geben Bedingungen dafür an, daß die numerische erzwungene Schwingung mit der analytischen erzwungenen Schwingung in Phase ist. Die Konsistenzordnung adaptiver Nyström-Runge-Kutta-Verfahren (mit einer Stabilitätsmatrix, die auf einer diagnolen Padé-Approximation beruht), für die die erzwungene Schwingung mit ihrem analytischen Gegenstück in Phase ist, kann nicht größer als zwei sein. Diese Ordnungsbarriere gilt nicht fürr-stufige implizite Nyström-Methoden der Ordnungp=2r.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02240198
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 10
    Electronic Resource
    Electronic Resource
    Stationary waiting time derivatives (1992)
    Springer
    Queueing systems 12 (1992), S. 369-389 
    Details
    ISSN: 1572-9443
    Keywords: Perturbation analysis ; stability ; stochastic difference equations ; simulation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract We investigate the stability of waiting-time derivatives when inputs to a queueing system-service times and interarrival times-depend on a parameter. We give conditions under which the sequence of waiting-time derivatives admits a stationary distribution, and under which the derivatives converge to the stationary regime from all initial conditions. Further hypotheses ensure that the expectation of a stationary waiting-time derivative is, in fact, the derivative of the expected stationary waiting time. This validates the use of simulation-based infinitesimal perturbation analysis estimates with a variety of queueing processes. We examine waiting-time sequences satisfying recursive equations. Our basic assumption is that the input and its derivatives are stationary and ergodic. Under monotonicity conditions, the method of Loynes establishes the convergence of the derivatives. Even without such conditions, the derivatives obey a linear difference equation with random coefficients, and we exploit this fact to find stability conditions.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01158809
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 11
    Electronic Resource
    Electronic Resource
    Re-entrant lines (1993)
    Springer
    Queueing systems 13 (1993), S. 87-110 
    Details
    ISSN: 1572-9443
    Keywords: Manufacturing systems ; semiconductor manufacturing ; thin film lines ; re-entrant lines ; scheduling policies ; queueing networks ; buffer priority policies ; due date policies ; stability ; stochastic control ; mean delay ; variance of delay ; machine failures ; set-up times
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Traditionally, manufacturing systems have mainly been treated as either job shops or flow shops. In job shops, parts may arrive with random routes, with each route having a low volume. In flow shops, the routes are fixed and acyclic, as in assembly lines. With the advent of semiconductor manufacturing plants, and more recently, thin film lines, this dichotomy needs to be expanded to consider another class of systems, which we call “re-entrant lines”. The distinguishing feature of these manufacturing systems is that parts visit some machines more than once at different stages of processing. Scheduling problems arise because several parts at different stages of processing may be in contention with each other for service at the same machine. There may be uncertainties in the form of random service or set-up times, as well as random machine failures and repairs. The goal of scheduling is to improve performance measures such as mean sojourn time in the system, which is also known as the mean “cycle-time”, or the variance of the cycle-time. In this paper we provide a tutorial account of some recent results in this field. We describe several scheduling policies of interest, and provide some results concerning their stability and performance. Several open problems are suggested.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01158930
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 12
    Electronic Resource
    Electronic Resource
    On pathwise behavior of multiserver queues (1994)
    Springer
    Queueing systems 15 (1994), S. 279-288 
    Details
    ISSN: 1572-9443
    Keywords: Sample-path ; point processes ; workload ; stability
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract In this paper, by exploiting recent results on the pathwise behavior of the workload process in single server, work conserving queues of theG/G/1/∞ type, we show that the workload of multiserver, work conserving queues ofG/G/m/∞ (m〈∞) (andG/G/∞) queues satisfies an o(t) growth condition, provided that the time average of the work brought into the system is less thanm form 〈 ∞ (and finite form=∞).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01189241
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 13
    Electronic Resource
    Electronic Resource
    Stability of non-Markovian polling systems (1995)
    Springer
    Queueing systems 21 (1995), S. 67-95 
    Details
    ISSN: 1572-9443
    Keywords: Polling systems ; stability ; stationary regime
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract A stationary regime for polling systems with general ergodic (G/G) arrival processes at each station is constructed. Mutual independence of the arrival processes is not required. It is shown that the stationary workload so constructed is minimal in the stochastic ordering sense. In the model considered the server switches from station to station in a Markovian fashion, and a specific service policy is applied to each queue. Our hypotheses cover the purely gated, thea-limited, the binomial-gated and other policies. As a by-product we obtain sufficient conditions for the stationary regime of aG/G/1/∞ queue with multiple server vacations (see Doshi [11]) to be ergodic.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01158575
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 14
    Electronic Resource
    Electronic Resource
    Pathwise rate- stability for input-output processes (1996)
    Springer
    Queueing systems 22 (1996), S. 47-63 
    Details
    ISSN: 1572-9443
    Keywords: Sample-path analysis ; stability ; rate stability ; ω-rate stability ; input-output process ; queueing ; infinite-server queues
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract An input-output processZ = {Z(t), t ⩾ 0} is said to beω-rate stable ifZ(t) = o(ω(t)) for some non-negative functionω(t). We prove that the processZ is ω-rate stable under weak conditions that include the assumption that input satisfies a linear burstiness condition and Z is asymptotically average stable. In many cases of interest, the conditions forω-rate-stability can be verified from input data. For example, using input information, we establishω-rate stability of the workload for multiserver queues, an ATM multiplexer, andω-rate stability of queue-length processes for infinite server queues.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01159392
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 15
    Electronic Resource
    Electronic Resource
    On Whitt's conjecture for queues in which service times and interarrival times depend linearly and randomly upon waiting times (1996)
    Springer
    Queueing systems 22 (1996), S. 345-366 
    Details
    ISSN: 1572-9443
    Keywords: State-dependent service and interarrival times ; Lindley equation ; recursive stochastic equations ; stability ; normal approximations
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract We consider a modification of the standardG/G/1 queueing system with infinite waiting space and the first-in-first-out discipline in which the service times and interarrival times depend linearly and randomly on the waiting times. In this model the waiting times satisfy a modified version of the classical Lindley recursion. When the waiting-time distributions converge to a proper limit, Whitt [10] proposed a normal approximation for this steady-state limit. In this paper we prove a limit theorem for the steady-state limit of the system. Thus, our result provides a solid foundation for Whitt's normal approximation of the steady-state distribution of the system.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01149178
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 16
    Electronic Resource
    Electronic Resource
    On the stability of a partially accessible multi‐station queue with state‐dependent routing (1998)
    Springer
    Queueing systems 29 (1998), S. 55-73 
    Details
    ISSN: 1572-9443
    Keywords: multi‐server queue ; customer class ; state‐dependent routing ; stability ; Markov chain ; fluid limit
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract We consider a multi‐station queue with a multi‐class input process when any station is available for the service of only some (not all) customer classes. Upon arrival, any customer may choose one of its accessible stations according to some state‐dependent policy. We obtain simple stability criteria for this model in two particular cases when service rates are either station‐ or class‐independent. Then, we study a two‐station queue under general assumptions on service rates. Our proofs are based on the fluid approximation approach.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1019175812444
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 17
    Electronic Resource
    Electronic Resource
    A stability criterion via fluid limits and its application to a polling system (1999)
    Springer
    Queueing systems 32 (1999), S. 131-168 
    Details
    ISSN: 1572-9443
    Keywords: stability ; positive recurrence ; fluid limit ; polling system ; exhaustive service policy
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract We introduce a generalized criterion for the stability of Markovian queueing systems in terms of stochastic fluid limits. We consider an example in which this criterion may be applied: a polling system with two stations and two heterogeneous servers.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1019187004209
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 18
    Electronic Resource
    Electronic Resource
    Performance analysis of a slotted-ALOHA protocol on a capture channel with fading (2000)
    Springer
    Queueing systems 34 (2000), S. 1-35 
    Details
    ISSN: 1572-9443
    Keywords: multiple access ; CDMA ; rates of convergence ; stability ; functional limit theorems ; transient analysis ; Markov-modulated capture channel
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract We consider the slotted ALOHA protocol on a channel with a capture effect. There are M 〈 ∞ users each with an infinite buffer. If in a slot, i packets are transmitted, then the probability of a successful reception of a packet is q i. This model contains the CDMA protocols as special cases. We obtain sufficient rate conditions, which are close to necessary for stability of the system, when the arrival streams are stationary ergodic. Under the same rate conditions, for general regenerative arrival streams, we obtain the rates of convergence to stationarity, finiteness of stationary moments and various functional limit theorems. Our arrival streams contain all the traffic models suggested in the recent literature, including the ones which display long range dependence. We also obtain bounds on the stationary moments of waiting times which can be tight under realistic conditions. Finally, we obtain several results on the transient performance of the system, e.g., first time to overflow and the limits of the overflow process. We also extend the above results to the case of a capture channel exhibiting Markov modulated fading. Most of our results and proofs will be shown to hold also for the slotted ALOHA protocol without capture.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1019192600091
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 19
    Electronic Resource
    Electronic Resource
    Stability and continuity of polling systems (1994)
    Springer
    Queueing systems 16 (1994), S. 115-137 
    Details
    ISSN: 1572-9443
    Keywords: Polling systems ; stability ; stochastic continuity ; general arrival process ; functional limit theorems.
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract The stability of a polling system with exhaustive service and a finite number of users, each with infinite buffers is considered. The arrival process is more general than a Poisson process and the system is not slotted. Stochastic continuity of the stationary distributions, rates of convergence and functional limit theorems for the queue length and waiting time processes have also been proved. The results extend to the gated service discipline.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01158952
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 20
    Electronic Resource
    Electronic Resource
    Open queueing networks in discrete time-some limit theorems (1993)
    Springer
    Queueing systems 14 (1993), S. 159-175 
    Details
    ISSN: 1572-9443
    Keywords: Queueing networks ; nonproduct form networks ; stability ; stochastic continuity ; functional limit theorems
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract A finite number of nodes, each with a single server and infinite buffers, is considered in discrete time. The service may be FIFO and the service times are constant. The external arrivals and the routing decision variables form a general stationary sequence. Stability of the system is proved under these assumptions. Extension to multiple servers at a node and general stationary distributions holds. If the external input is i.i.d. and the routing is Markovian then stochastic ordering, continuity of stationary distributions, rates of convergence, a functional CLT and a functional LIL and various other limit theorems for the queue length process are also proved. Generalizations to multiple servers at nodes, customers with priority, multiple customer classes, general service length and Markov modulated external arrival cases are discussed.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01153532
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 21
    Electronic Resource
    Electronic Resource
    Monotonicity and stability of periodic polling models (1994)
    Springer
    Queueing systems 15 (1994), S. 211-238 
    Details
    ISSN: 1572-9443
    Keywords: polling system ; stability ; Markov chain ; stochastic monotonicity ; heavy traffic ; nonpreemptive local priority
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract This paper deals with the stability of periodic polling models with a mixture of service policies. Customers arrive according to independent Poisson processes. The service times and the switchover times are independent with general distributions. The necessary and sufficient condition for the stability of such polling systems is established. The proof is based on the stochastic monotonicity of the state process at the polling instants. The stability of only a subset of the queues is also analyzed and, in case of heavy traffic, the order of explosion of the queues is given. The results are valid for a model with set-up times, and also when there is a local priority rule at the queues.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01189238
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 22
    Electronic Resource
    Electronic Resource
    Single-server queues with spatially distributed arrivals (1994)
    Springer
    Queueing systems 17 (1994), S. 317-345 
    Details
    ISSN: 1572-9443
    Keywords: Single-server queue ; spatially distributed arrival points ; travelling server ; Brownian motion ; embedded Markov chain ; stability ; Tweedie's lemma ; regenerative processes ; stochastic decomposition ; equilibrium equations ; mean queue length
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Consider a queueing system where customers arrive at a circle according to a homogeneous Poisson process. After choosing their positions on the circle, according to a uniform distribution, they wait for a single server who travels on the circle. The server's movement is modelled by a Brownian motion with drift. Whenever the server encounters a customer, he stops and serves this customer. The service times are independent, but arbitrarily distributed. The model generalizes the continuous cyclic polling system (the diffusion coefficient of the Brownian motion is zero in this case) and can be interpreted as a continuous version of a Markov polling system. Using Tweedie's lemma for positive recurrence of Markov chains with general state space, we show that the system is stable if and only if the traffic intensity is less than one. Moreover, we derive a stochastic decomposition result which leads to equilibrium equations for the stationary configuration of customers on the circle. Steady-state performance characteristics are determined, in particular the expected number of customers in the system as seen by a travelling server and at an arbitrary point in time.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01158698
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 23
    Electronic Resource
    Electronic Resource
    Piecewise linear test functions for stability and instability of queueing networks (1997)
    Springer
    Queueing systems 27 (1997), S. 205-226 
    Details
    ISSN: 1572-9443
    Keywords: multiclass queueing networks ; ergodicity ; stability ; performance analysis
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract We develop the use of piecewise linear test functions for the analysis of stability of multiclass queueing networks and their associated fluid limit models. It is found that if an associated LP admits a positive solution, then a Lyapunov function exists. This implies that the fluid limit model is stable and hence that the network model is positive Harris recurrent with a finite polynomial moment. Also, it is found that if a particular LP admits a solution, then the network model is transient.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1019166115653
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 24
    Electronic Resource
    Electronic Resource
    On the guaranteed throughput and efficiency of closed re-entrant lines (1998)
    Springer
    Queueing systems 28 (1998), S. 33-54 
    Details
    ISSN: 1572-9443
    Keywords: queueing networks ; throughput ; closed networks ; efficiency ; stability
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract A closed network is said to be “guaranteed efficient” if the throughput converges under all non-idling policies to the capacity of the bottlenecks in the network, as the number of trapped customers increases to infinity. We obtain a necessary condition for guaranteed efficiency of closed re-entrant lines. For balanced two-station systems, this necessary condition is almost sufficient, differing from it only by the strictness of an inequality. This near characterization is obtained by studying a special type of virtual station called “alternating visit virtual station”. These special virtual stations allow us to relate the necessary condition to certain indices arising in heavy traffic studies using a Brownian network approximation, as well as to certain policies proposed as being extremal with respect to the asymptotic loss in the throughput. Using the near characterization of guaranteed efficiency we also answer the often pondered question of whether an open network or its closed counterpart has greater throughput - the answer is that neither can assure a greater guaranteed throughput.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1019199022922
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 25
    Electronic Resource
    Electronic Resource
    Stability of token passing rings (1992)
    Springer
    Queueing systems 11 (1992), S. 7-33 
    Details
    ISSN: 1572-9443
    Keywords: Token passing rings ; stability ; substability ; ergodicity ; Markov chains ; Loynes' scheme ; stochastically dominant ; Little's formula ; regenerative processes
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract A sufficient stability condition for the standard token passing ring has been “known” since the seminal paper by Kuehn in 1979. However, this condition was derived without formal proof, and the proof seems to be of considerable interest to the research community. In fact, Watson observed that in the performance evaluation of token passing rings, “it is convenient to derive stability conditions ... (without proof)”. Our intention is to fill this gap, and to provide a formal proof of thesufficient and necessary stability condition for the token passing ring. In this paper, we present the case when the arrival process to each queue is Poisson but service times and switchover times are generally distributed. We consider in depth a gatedl-limited (l≤ ∞) service discipline for each station. We also indicate that the basic steps of our technique can be used to study the stability of some other multiqueue systems.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01159285
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 26
    Electronic Resource
    Electronic Resource
    Stability of a three‐station fluid network (1999)
    Springer
    Queueing systems 33 (1999), S. 293-325 
    Details
    ISSN: 1572-9443
    Keywords: stability ; fluid models ; multiclass queueing networks ; piecewise linear Lyapunov functions ; linear Lyapunov functions ; monotone global stability ; static buffer priority disciplines
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract This paper studies the stability of a three‐station fluid network. We show that, unlike the two‐station networks in Dai and Vande Vate [18], the global stability region of our three‐station network is not the intersection of its stability regions under static buffer priority disciplines. Thus, the “worst” or extremal disciplines are not static buffer priority disciplines. We also prove that the global stability region of our three‐station network is not monotone in the service times and so, we may move a service time vector out of the global stability region by reducing the service time for a class. We introduce the monotone global stability region and show that a linear program (LP) related to a piecewise linear Lyapunov function characterizes this largest monotone subset of the global stability region for our three‐station network. We also show that the LP proposed by Bertsimas et al. [1] does not characterize either the global stability region or even the monotone global stability region of our three‐station network. Further, we demonstrate that the LP related to the linear Lyapunov function proposed by Chen and Zhang [11] does not characterize the stability region of our three‐station network under a static buffer priority discipline.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1019184331042
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 27
    Electronic Resource
    Electronic Resource
    A Multiclass Feedback Queueing Network with a Regular Skorokhod Problem (2000)
    Springer
    Queueing systems 36 (2000), S. 327-349 
    Details
    ISSN: 1572-9443
    Keywords: multiclass networks ; networks with feedback ; Skorokhod Problem ; Skorokhod Mapping ; Lipschitz continuity ; stability ; load conditions
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract We consider a four-class two-station network with feedback, with fluid inputs and a head-of-the-line generalized processor sharing discipline at each station. We derive the Skorokhod Problem associated with the network and obtain algebraic sufficient conditions for Lipschitz continuity of the associated Skorokhod Map. This provides the first example of a multiclass network with feedback for which the associated Skorokhod Problem has been proved to be regular. As an elementary application, we show that under the conditions which guarantee Lipschitz continuity the network is stable if and only if the usual load conditions apply.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1011037419624
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 28
    Electronic Resource
    Electronic Resource
    Stability and performance analysis of rate-based feedback flow controlled ATM networks (1998)
    Springer
    Queueing systems 29 (1998), S. 129-159 
    Details
    ISSN: 1572-9443
    Keywords: rate-based feedback control ; ATM networks ; stability ; optimal algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Motivated by ABR class of service in ATM networks, we study a continuous time queueing system with a feedback control of the arrival rate of some of the sources. The feedback about the queue length or the total workload is provided at regular intervals (variations on it, especially the traffic management specification TM 4.0, are also considered). The propagation delays can be nonnegligible. For a general class of feedback algorithms, we obtain the stability of the system in the presence of one or more bottleneck nodes in the virtual circuit. Our system is general enough that it can be useful to study feedback control in other network protocols. We also obtain rates of convergence to the stationary distributions and finiteness of moments. For the single botterneck case, we provide algorithms to compute the stationary distributions and the moments of the sojourn times in different sets of states. We also show analytically (by showing continuity of stationary distributions and moments) that for small propagation delays, we can provide feedback algorithms which have higher mean throughput, lower probability of overflow and lower delay jitter than any open loop policy. Finally these results are supplemented by some computational results.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1019127929282
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 29
    Electronic Resource
    Electronic Resource
    Dynamic scheduling in multiclass queueing networks: Stability under discrete-review policies (1999)
    Springer
    Queueing systems 31 (1999), S. 171-206 
    Details
    ISSN: 1572-9443
    Keywords: scheduling ; open multiclass queueing networks ; discrete-review policies ; fluid models ; stability
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract This paper describes a family of discrete-review policies for scheduling open multiclass queueing networks. Each of the policies in the family is derived from what we call a dynamic reward function: such a function associates with each queue length vector q and each job class k a positive value r k (q), which is treated as a reward rate for time devoted to processing class k jobs. Assuming that each station has a traffic intensity parameter less than one, all policies in the family considered are shown to be stable. In such a policy, system status is reviewed at discrete points in time, and at each such point the controller formulates a processing plan for the next review period, based on the queue length vector observed. Stability is proved by combining elementary large deviations theory with an analysis of an associated fluid control problem. These results are extended to systems with class dependent setup times as well as systems with alternate routing and admission control capabilities.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1019106213778
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 30
    Electronic Resource
    Electronic Resource
    Queues with service times and interarrival times depending linearly and randomly upon waiting times (1990)
    Springer
    Queueing systems 6 (1990), S. 335-351 
    Details
    ISSN: 1572-9443
    Keywords: State-dependent service and interarrival times ; Lindley equation ; recursive stochastic equations ; stability ; stochastic comparisons ; normal approximations ; scheduling arrivals
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract We consider a modification of the standardG/G/1 queue with unlimited waiting space and the first-in first-out discipline in which the service times and interarrival times depend linearly and randomly on the waiting times. In this model the waiting times satisfy a modified version of the classical Lindley recursion. We determine when the waiting-time distributions converge to a proper limit and we develop approximations for this steady-state limit, primarily by applying previous results of Vervaat [21] and Brandt [4] for the unrestricted recursionY n+1=C n Y n +X n . Particularly appealing for applications is a normal approximation for the stationary waiting time distribution in the case when the queue only rarely becomes empty. We also consider the problem of scheduling successive interarrival times at arrival epochs, with the objective of achieving nearly maximal throughput with nearly bounded waiting times, while making the interarrival time sequence relatively smooth. We identify policies depending linearly and deterministically upon the work in the system which meet these objectives reasonably well; with these policies the waiting times are approximately contained in a specified interval a specified fraction of time.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02411482
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 31
    Electronic Resource
    Electronic Resource
    Dam processes with state dependent batch sizes and intermittent production processes with state dependent rates (1996)
    Springer
    Queueing systems 24 (1996), S. 37-57 
    Details
    ISSN: 1572-9443
    Keywords: dam ; storage process ; saturation rule ; intermittent production ; state dependent rates ; state dependent jumps ; stability ; positive Harris recurrence
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract We consider a dam process with a general (state dependent) release rule and a pure jump input process, where the jump sizes are state dependent. We give sufficient conditions under which the process has a stationary version in the case where the jump times and sizes are governed by a marked point process which is point (Palm) stationary and ergodic. We give special attention to the Markov and Markov regenerative cases for which the main stability condition is weakened. We then study an intermittent production process with state dependent rates. We provide sufficient conditions for stability for this process and show that if these conditions are satisfied, then an interesting new relationship exists between the stationary distribution of this process and a dam process of the type we explore here.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01149079
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 32
    Electronic Resource
    Electronic Resource
    On the stability of retrial queues (1997)
    Springer
    Queueing systems 26 (1997), S. 343-363 
    Details
    ISSN: 1572-9443
    Keywords: retrial queues ; stability ; ergodicity ; renovation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract We consider the following Type of problems. Calls arrive at a queue of capacity K (which is called the primary queue), and attempt to get served by a single server. If upon arrival, the queue is full and the server is busy, the new arriving call moves into an infinite capacity orbit, from which it makes new attempts to reach the primary queue, until it finds it non-full (or it finds the server idle). If the queue is not full upon arrival, then the call (customer) waits in line, and will be served according to the FIFO order. If λ is the arrival rate (average number per time unit) of calls and μ is one over the expected service time in the facility, it is well known that μ 〉 λ is not always sufficient for stability. The aim of this paper is to provide general conditions under which it is a sufficient condition. In particular, (i) we derive conditions for Harris ergodicity and obtain bounds for the rate of convergence to the steady state and large deviations results, in the case that the inter-arrival times, retrial times and service times are independent i.i.d. sequences and the retrial times are exponentially distributed; (ii) we establish conditions for strong coupling convergence to a stationary regime when either service times are general stationary ergodic (no independence assumption), and inter-arrival and retrial times are i.i.d. exponentially distributed; or when inter-arrival times are general stationary ergodic, and service and retrial times are i.i.d. exponentially distributed; (iii) we obtain conditions for the existence of uniform exponential bounds of the queue length process under some rather broad conditions on the retrial process. We finally present conditions for boundedness in distribution for the case of nonpatient (or non persistent) customers.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1019193527040
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 33
    Electronic Resource
    Electronic Resource
    Recurrence and transience properties of some neural networks: an approach via fluid limit models (1999)
    Springer
    Queueing systems 32 (1999), S. 99-130 
    Details
    ISSN: 1572-9443
    Keywords: neural network ; inhibition ; stability ; Markov process ; fluid limit ; Harris-recurrence ; transience
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract The subject of the paper is the stability analysis of some neural networks consisting of a finite number of interacting neurons. Following the approach of Dai [5] we use the fluid limit model of the network to derive a sufficient condition for positive Harris-recurrence of the associated Markov process. This improves the main result in Karpelevich et al. [11] and, at the same time, sheds some new light on it. We further derive two different conditions that are sufficient for transience of the state process and illustrate our results by classifying some examples according to positive recurrence or transience.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1019135020138
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 34
    Electronic Resource
    Electronic Resource
    Window flow control in FIFO networks with cross traffic (1999)
    Springer
    Queueing systems 32 (1999), S. 195-231 
    Details
    ISSN: 1572-9443
    Keywords: window flow control ; TCP ; stability ; multiclass networks ; stationary ergodic point processes ; (max,+)-linear system
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract We focus on window flow control as used in packet-switched communication networks. The approach consists in studying the stability of a system where each node on the path followed by the packets of the controlled connection is modeled by a FIFO (First-In-First-Out) queue of infinite capacity which receives in addition some cross traffic represented by an exogenous flow. Under general stochastic assumptions, namely for stationary and ergodic input processes, we show the existence of a maximum throughput allowed by the flow control. Then we establish bounds on the value of this maximum throughput. These bounds, which do not coincide in general, are reached by time-space scalings of the exogenous flows. Therefore, the performance of the window flow control depends not only on the traffic intensity of the cross flows, but also on fine statistical characteristics such as the burstiness of these flows. These results are illustrated by several examples, including the case of a nonmonotone, nonconvex and fractal stability region.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1019191105117
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 35
    Electronic Resource
    Electronic Resource
    The finite volume element method with quadratic basis functions (1996)
    Springer
    Computing 57 (1996), S. 281-299 
    Details
    ISSN: 1436-5057
    Keywords: 65N15 ; 65N99 ; 35A40 ; Finite volume method ; box scheme ; stability ; error estimates
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung Es wird eine Box-Methode mit quadratischen Ansatzfunktionen zur Diskretisierung elliptischer Randwertaufgaben vorgestellt. Die entstehende Diskretisierungsmatrix ist nichsymmetrisch. Die Stabilitätsanalyse basiert auf einer elementweisen Abschätzung des Skalarproduktes 〈A h u h ,u h 〉. Hinreichende Bedingungen an die Geometrie der Dreiecke der Triangulierung führen zur diskreten Elliptizität. Unter diesen Voraussetzungen wird eineO(h 2)-Fehlerabschätzung bewiesen.
    Notes: Abstract The paper presents a box scheme with quadratic basis functions for the discretisation of elliptic boundary value problems. The resulting discretisation matrix is non-symmetrical (and also not an M-matrix). The stability analysis is based on an elementwise estimation of the scalar product 〈A h u h ,u h 〉. Sufficient conditions placed on the triangles of the triangulation lead to discrete ellipticity. Proof of anO(h 2) error estimate is given for these conditions.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02252250
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 36
    Electronic Resource
    Electronic Resource
    Fast massively parallel algorithms for shortest path within planar figures (1996)
    Springer
    The visual computer 12 (1996), S. 484-502 
    Details
    ISSN: 1432-2315
    Keywords: Key words: Shortest path ; Depth search machines ; Parallel algorithms ; Distributed algorithms ; n-CCS ; Near edge
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: s and t within a given planar figure F is considered. The approach contains basic methodology developed for any parallel or distributed system. The 2D scene or the edge of F are represented in the n Cartesian coordinate system (n-CCS). Several algorithms for the shortest path are given, each one to be applied in specified circumstances depending on the exact machine model or on additional information concerning geometrical properties of the figure. If these algorithms are implemented in a parallel depth search machine (PDSM), then the shortest path can be computed in time O(1). The maximum number of processors used is 0(n). The given methodology can also be adapted for producing an approximate solution when the shortest path is approximated by polygonal lines.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s003710050081
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 37
    Electronic Resource
    Electronic Resource
    Parallel algorithms for shortest path problems in polygons (1988)
    Springer
    The visual computer 3 (1988), S. 371-378 
    Details
    ISSN: 1432-2315
    Keywords: Computational Geometry ; Parallel algorithms ; Simple polygon ; Shortest path
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Given ann-vertex simple polygon we address the following problems: (i) find the shortest path between two pointss andd insideP, and (ii) compute the shortestpath tree between a single points and each vertex ofP (which implicitly represents all the shortest paths). We show how to solve the first problem inO(logn) time usingO(n) processors, and the more general second problem inO(log2 n) time usingO(n) processors, and the more general second problem inO(log2 n) time usingO(n) processors for any simple polygonP. We assume the CREW RAM shared memory model of computation in which concurrent reads are allowed, but no two processors should attempt to simultaneously write in the same memory location. The algorithms are based on the divide-and-conquer paradigm and are quite different from the known sequential algorithms
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01901194
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 38
    Electronic Resource
    Electronic Resource
    Performance of scanline algorithms for direct display of CSG (1994)
    Springer
    The visual computer 10 (1994), S. 317-329 
    Details
    ISSN: 1432-2315
    Keywords: Graphics performance ; Display algorithms ; Scanline algorithms ; Parallel algorithms ; Solid modelling ; CSG models ; Polygonal and exact models
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Direct display algorithms display a CSG model without first converting the model into a boundary representation. Three such algorithms are described. All three are based on the scanline display algorithm, and are able to handle both polygonal and quadratic faces. The first algorithm is based on Atherton's recursive subdivision scanline algorithm, the second is a combination of a scanline and a ray casting algorithm, and the third is a scanline version of the Trickle algorithm. A multiprocessor system in which these algorithms can be incorporated is also described. The performances of the algorithms are compared. It turns out that the algorithms efficiently display CSG models on general-purpose architectures. A comparison is also made between the performances for polygon-approximated models and exact models for objects bounded by quadratic faces, such as spherical, cylindrical and conical faces, to get an indication of how many polygons can at most be used to approximate quadratic faces and still have better performance.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01900826
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 39
    Electronic Resource
    Electronic Resource
    Animation with fractals from variations on the Mandelbrot set (1987)
    Springer
    The visual computer 3 (1987), S. 23-26 
    Details
    ISSN: 1432-2315
    Keywords: Animation ; Fractals ; Parallel algorithms ; Graphics
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract The results of experimenting with a most interesting variation on the iteration formula which generates the Mandelbrot set are presented. Varying the powerm of the generating function results in fractal surfaces exhibiting self-similarity and suggesting smooth evolution under animation. One such sequence led to a mathematical conjecture, which has since been mathematically proven (Hubbard et al. 1986), illustrating the interaction between computer graphics and fractal geometry. Finally, we offer an extension of adapting fractal graphics algorithms to massively parallel computers.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02153648
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 40
    Electronic Resource
    Electronic Resource
    Solving visibility and separability problems on a mesh-of-processors (1988)
    Springer
    The visual computer 3 (1988), S. 356-370 
    Details
    ISSN: 1432-2315
    Keywords: Computational geometry ; Mesh-of-Processors ; Parallel algorithms ; Separability-Visibility
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract In this paper we study parallel algorithms for the Mesh-of-Processors architecture to solve visibility and related separability problems for sets of simple polygons in the plane. In particular, we present the following algorithms: - AnO( $$\sqrt N$$ time algorithm for computing on a Mesh-of-Processors of size N the visibility polygon from a point located in anN-vertex polygon, possibly with holes. -O( $$\sqrt N$$ ) time algorithms for computing on a Mesh-of-Processors of sizeN the set of all points on the boundary of anN-vertex polygonP which are visible in a given directiond as well as the visibility hull ofP for a given directiond. - AnO( $$\sqrt N$$ ) time algorithm for detecting on a Mesh-of-Processors of size 2N whether twoN-vertex polygons are separable in a given direction and anO( $$\sqrt {MN}$$ ) time algorithm for detecting on a Mesh-of-Processors of sizeMN whetherM N-vertex polygons are sequentially separable in a given direction. All proposed algorithms are asymptotically optimal (for the Mesh-of-Processors) with respect to time and number of processors.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01901193
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 41
    Electronic Resource
    Electronic Resource
    Load balancing strategies for a parallel ray-tracing system based on constant subdivision (1988)
    Springer
    The visual computer 4 (1988), S. 197-209 
    Details
    ISSN: 1432-2315
    Keywords: Multiprocessor system ; Load balancing ; Performance evaluation ; Ray tracing ; Parallel algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Static and dynamic load balancing strategies for a multiprocessor system for a ray tracing algorithm based on constant subdivision are presented. An object space is divided into regular cubes (subspaces), whose boundary planes are perpendicular to the coordinate axes, and these are allocated to the processors in the system. Here, load balancing among the processors is the most important problem. Firstly, in a category of static load balancing, strategies for mapping the subspaces into the processors are evaluated by simulation. Moreover, we propose a hierarchical multiprocessor system in order to realize dynamic load balancing with the static one. Its architecture can overcome the limitation of the static load balancing in a large scale multiprocessor system.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01887592
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 42
    Electronic Resource
    Electronic Resource
    Line diffusion: a parallel error diffusion algorithm for digital halftoning (1996)
    Springer
    The visual computer 12 (1996), S. 40-46 
    Details
    ISSN: 1432-2315
    Keywords: Error diffusion ; Halftoning ; Neural network ; Parallel algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Floyd and Steinberg's (1976) error diffusion technique is a well-known approach to digital halftoning. The main drawback of this technique is that it is inherently serial. This paper presents a new parallelizable error-diffusion algorithm, calledline diffusion. In this method, the pixels of the original image are divided into classes line by line, and all the pixels on a line are halftoned simultaneously. Errors are distributed randomly. Experimental results show that line diffusion is comparable to error diffusion in image quality. A sequential line diffusion algorithm is also provided.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01782218
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 43
    Electronic Resource
    Electronic Resource
    A parallel scaled conjugate-gradient algorithm for the solution phase of gathering radiosity on hypercubes (1997)
    Springer
    The visual computer 13 (1997), S. 1-19 
    Details
    ISSN: 1432-2315
    Keywords: Key words: Gathering radiosity ; Scaled conjugate-gradient method ; Parallel algorithms ; Hypercube multicomputer ; Data redistribution
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s003710050085
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 44
    Electronic Resource
    Electronic Resource
    Difference schemes for the dispersive equation (1983)
    Springer
    Computing 31 (1983), S. 261-267 
    Details
    ISSN: 1436-5057
    Keywords: 65M10 ; Dispersive equation ; finite difference ; stability
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung Dieser Artikel beinhaltet eine Zusammenstellung von Differenzenverfahren für die Dispersionsgleichungu 1=au xxx. Es werden Kriterien zur Herleitung von Stabilitätsbedingungen für Differenzenverfahren angegeben und auf die angegebenen Differenzenverfahren angewendet.
    Notes: Abstract In this paper a table of difference schemes for the dispersive equationu i=au xxx is presented. A collection of criterions for deriving stability conditions of difference schemes is given and applied to these difference schemes.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02263436
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 45
    Electronic Resource
    Electronic Resource
    D-stability and Kaps-Rentrop-methods (1984)
    Springer
    Computing 32 (1984), S. 229-237 
    Details
    ISSN: 1436-5057
    Keywords: 65L05 ; 65L07 ; Stiff system ; Rosenbroek method ; stability
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung In dieser Arbeit wird die Stabilität des Kaps-Rentrop-Verfahrens in die Anwesenheit nichtlinearer Steifheit (Stiffness) analysiert. Dazu werden mittels eines einfachen Modells zwei Größen introduziert. Die Werte dieser Größen reflektieren gewissermaßen das Verhalten eines Kaps-Rentrop-Verfahrens in die Anwesenheit einer bestimmten Kopplung zwischen die beiden Komponenten in das steife System gewöhnlicher Differentialgleichungen. Einige numerische Beispiele veranschaulichen die Analyse.
    Notes: Abstract In this paper we give an analysis of the effect of stiff nonlinearities on the behavior of a Kaps-Rentrop method. To that end we introduce two quantities related to a simple model. The values of these quantities determine to some extent the behavior of a Kaps-Rentrop method in case of a strong coupling between the smooth component and the transient one. Numerical examples illustrate the theoretical results.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02243574
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 46
    Electronic Resource
    Electronic Resource
    Parallel algorithms for the rounding exact summation of floating point numbers (1982)
    Springer
    Computing 28 (1982), S. 89-104 
    Details
    ISSN: 1436-5057
    Keywords: 68B ; 65G05 ; Parallel algorithms ; computer arithmetic
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung Pichat und Bohlender untersuchten einen Algorithmus für die rundungsexakte Summation von Gleitpunktzahlen, der keiner Erweiterung der üblichen Gleitpunktarithmetik-Einheiten bedarf. Wir schlagen parallele Versionen dieses Algorithmus vor, nämlich eine Pipeline-Version, einen Algorithmus, der ähnlich den Algorithmen für Sortieren durch Vertauschen ist, und einen Baum-Algorithmus, der von der Zuordnung zwischen einer Summe und einem binären Baum abgeleitet wird. Es werden für alle Algorithmen die Voraussetzungen an eine Mehrprozessor-Architektur diskutiert, ohne Beschränkung auf eine spezielle Architektur.
    Notes: Abstract Pichat and Bohlender studied an algorithm for the rounding exact summation of floating point numbers which can be executed on any floating point arithmetic unit. We propose parallel versions of this algorithm, namely a pipeline version, an algorithm similar to the exchange methods for sorting and a tree-like algorithm, associating a tree to the sum. For all these algorithms we discuss the properties, a multiprocessor architecture should have for an efficient implementation of an algorithm without restricting us to a special architecture.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02241816
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 47
    Electronic Resource
    Electronic Resource
    Concerning a Technique for Increasing Stability of Climbing Robots (2000)
    Springer
    Journal of intelligent and robotic systems 27 (2000), S. 195-209 
    Details
    ISSN: 1573-0409
    Keywords: wall-climbing robot ; electromagnetic grippers ; stability ; additional support element ; sliding and turning over conditions
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mechanical Engineering, Materials Science, Production Engineering, Mining and Metallurgy, Traffic Engineering, Precision Mechanics
    Notes: Abstract Legged-climbing robot is considered. Each foot of the robot has an electromagnet system for robot"s holding on a metal surface. This surface can be both vertical and inclined, including negative slope. Analytical calculation of robot stability under turn over or sliding conditions has been made. Critical slopes have been determined. One of these slopes corresponds to minimal reserve of robot stability towards sliding and another to minimal reserve of robot stability towards turning-over. As total reserve of stability of a robot is always equal to the minimal one of these reserves. Additional support elements of elastic material with high coefficient of friction, along with electromagnet, allows to increase minimal reserve of robot stability towards sliding. The use of such support elements leads to redistributing force of normal support reaction between electromagnet (which surface has low coefficient of friction) and additional support element (which surface has high coefficient of friction). It is just what leads to increasing the total friction force and as a consequence to increasing of minimal reserve of robot stability towards sliding.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1008158332368
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 48
    Electronic Resource
    Electronic Resource
    Robust pole assignment for incomplete nonlinear decoupling applied to robots (1990)
    Springer
    Journal of intelligent and robotic systems 3 (1990), S. 259-289 
    Details
    ISSN: 1573-0409
    Keywords: Nonlinear decoupling ; feedback linearization ; functional analysis ; elastic robots ; robustness ; stability ; pole assignment ; nonlinear systems ; robot control
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mechanical Engineering, Materials Science, Production Engineering, Mining and Metallurgy, Traffic Engineering, Precision Mechanics
    Notes: Abstract A robustness analysis and synthesis for incomplete nonlinear decoupling for a class of nonlinear systems is discussed. Rigid and elastic-joint robot models belong to this class. For the elastic case, a transformation facilitates the robustness analysis under a weak assumption. Charts with H 1- and H ∞- norms of closed-loop disturbance transfer functions of the nonlinear-decoupled system are presented for a robust pole assignment.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00126073
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 49
    Electronic Resource
    Electronic Resource
    Real-time feedback scheduling of flexible manufacturing systems (1992)
    Springer
    Journal of intelligent and robotic systems 6 (1992), S. 51-63 
    Details
    ISSN: 1573-0409
    Keywords: Scheduling ; flexible manufacturing systems ; stability ; feedback
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mechanical Engineering, Materials Science, Production Engineering, Mining and Metallurgy, Traffic Engineering, Precision Mechanics
    Notes: Abstract A genetic manufacturing environment is considered. The emphasis is on small-lot, discrete, and asynchronous type of manufacturing systems rather than high volume and continuous type. Two classes of scheduling policies are proposed to render the machine stable. The policies are of feedback type. The decision is made in real-time and on-line.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00314697
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 50
    Electronic Resource
    Electronic Resource
    Force control of robots with nonlinearities (1992)
    Springer
    Journal of intelligent and robotic systems 6 (1992), S. 219-240 
    Details
    ISSN: 1573-0409
    Keywords: Force control ; slip-stick friction ; stability
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mechanical Engineering, Materials Science, Production Engineering, Mining and Metallurgy, Traffic Engineering, Precision Mechanics
    Notes: Abstract This paper explores two practical issues related to the force control of manipulators. The first issue examined is how system stability is effected by commonly occurring manipulator nonlinearities, such as sampled-data, control signal saturation and slip-stick friction. It is shown that discretely implemented force control algorithms can drive the feedback force controlled manipulator into a limit cycle, even for a very small sampling period that by far satisfies Shannon's sampling theorem. The bounds of stability are enhanced by the presence of control signal saturation and slip stick friction. The second issue investigated is the inclusion of a high gain inner position loop as a means to minimize the unpredictability in the steady state error due to slip-stick friction. In order to support the theoretical conclusions, experiments were performed with the PUMP 560 industrial robot testbed facility developed at Colorado State University.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00248017
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 51
    Electronic Resource
    Electronic Resource
    A parallel Navier-Stokes solver: The Meiko implementation (1995)
    Springer
    The journal of supercomputing 9 (1995), S. 347-364 
    Details
    ISSN: 1573-0484
    Keywords: Parallel algorithms ; Meiko ; i860 ; fluid mechanics ; turbulence ; jet ; spectral elements ; spectral methods ; ALPHA FARM
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract A mixed spectral element, pseudospectral, and finite-difference scheme for solving the Navier-Stokes equations is implemented on a Meiko parallel supercomputer. The code for the solution of Navier-Stokes equations for jetlike flows is implemented with a spectral scheme in cross-flow directions, a spectral element scheme in the stream-wise direction, and finite-difference marching in time. Several strategies for distributing the workload onto the processors are discussed. Special attention is paid to using the flexible topology of the Meiko.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01206272
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 52
    Electronic Resource
    Electronic Resource
    Autonomous Intelligent Cruise Control with Actuator Delays (1998)
    Springer
    Journal of intelligent and robotic systems 23 (1998), S. 27-43 
    Details
    ISSN: 1573-0409
    Keywords: autonomous control ; actuator delays ; stability
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mechanical Engineering, Materials Science, Production Engineering, Mining and Metallurgy, Traffic Engineering, Precision Mechanics
    Notes: Abstract In this paper, we consider the control design problem of vehicle following systems with actuator delays. An upper bound for the time delays is first constructed to guarantee the vehicle stability. Second, sufficient conditions are presented to avoid slinky-effects in the vehicle following. Next, zero steady state achieved by the proposed controller is proven. Finally, simulations are given to examine our claims.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1007946007601
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 53
    Electronic Resource
    Electronic Resource
    Parallel algorithms for image enhancement and segmentation by region growing, with an experimental study (1996)
    Springer
    The journal of supercomputing 10 (1996), S. 141-168 
    Details
    ISSN: 1573-0484
    Keywords: Parallel algorithms ; image processing ; region growing ; image enhancement ; image segmentation ; Symmetric Neighborhood Filter ; connected components ; parallel performance
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract This paper presents efficient and portable implementations of a powerful image enhancement process, the Symmetric Neighborhood Filter (SNF), and an image segmentation technique that makes use of the SNF and a variant of the conventional connected components algorithm which we call δ-Connected Components. We use efficient techniques for distributing and coalescing data as well as efficient combinations of task and data parallelism. The image segmentation algorithm makes use of an efficient connected components algorithm based on a novel approach for parallel merging. The algorithms have been coded in Split-C and run on a variety of platforms, including the Thinking Machines CM-5, IBM SP-1 and SP-2, Cray Research T3D, Meiko Scientific CS-2, Intel Paragon, and workstation clusters. Our experimental results are consistent with the theoretical analysis (and provide the best known execution times for segmentation, even when compared with machine-specific implementations). Our test data include difficult images from the Landsat Thematic Mapper (TM) satellite data.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00130707
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 54
    Electronic Resource
    Electronic Resource
    Efficient decomposition and performance of parallel PDE, FFT, Monte Carlo simulations, simplex, and Sparse solvers (1991)
    Springer
    The journal of supercomputing 5 (1991), S. 219-238 
    Details
    ISSN: 1573-0484
    Keywords: Parallel algorithms ; decomposition ; multiprocessor performance ; shared-memory multiprocessors ; cache coherency ; scientific applications
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract In this paper, we describe the decomposition of six algorithms: two partial differential equations (PDE) solvers (successive over-relaxation [SOR] and alternating direction implicit [ADI]), fast Fourier transform (FFT), Monte Carlo simulations, Simplex linear programming, and Sparse solvers. The algorithms were selected not only because of their importance in scientific applications, but also because they represent a variety of computational (structured to irregular) and communication (low to high) requirements. We present the performance results of these algorithms on two shared-memory VAX/VMSTM1 multiprocessor prototypes: the VAX 6300 series with up to 8 processors and the M31 with up to 22 processors. We demonstrate that by efficient decomposition it is possible to achieve high performance for all algorithms on both prototypes. We describe the efficient decomposition techniques applied to optimize the performance of parallel algorithms. Also, we discuss the performance implications due to different cache designs on two multiprocessors.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00127844
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 55
    Electronic Resource
    Electronic Resource
    Stable Sampled-data Adaptive Control of Robot Arms Using Neural Networks (1997)
    Springer
    Journal of intelligent and robotic systems 20 (1997), S. 131-155 
    Details
    ISSN: 1573-0409
    Keywords: robot adaptive control ; basis function-like networks ; stability ; discrete variable structure
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mechanical Engineering, Materials Science, Production Engineering, Mining and Metallurgy, Traffic Engineering, Precision Mechanics
    Notes: Abstract Stable neural network-based sampled-data indirect and direct adaptivecontrol approaches, which are the integration of a neural network (NN)approach and the adaptive implementation of the discrete variable structurecontrol, are developed in this paper for the trajectory tracking control ofa robot arm with unknown nonlinear dynamics. The robot arm is assumed tohave an upper and lower bound of its inertia matrix norm and its states areavailable for measurement. The discrete variable structure control servestwo purposes, i.e., one is to force the system states to be within the stateregion in which neural networks are used when the system goes out of neuralcontrol; and the other is to improve the tracking performance within the NNapproximation region. Main theory results for designing stable neuralnetwork-based sampled data indirect and direct adaptive controllers aregiven, and the extension of the proposed control approaches to the compositeadaptive control of a flexible-link robot is discussed. Finally, theeffectiveness of the proposed control approaches is illustrated throughsimulation studies.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1007900125801
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 56
    Electronic Resource
    Electronic Resource
    Robust Regulator for Flexible-Joint Robots Using Integrator Backstepping (1998)
    Springer
    Journal of intelligent and robotic systems 22 (1998), S. 23-38 
    Details
    ISSN: 1573-0409
    Keywords: robot dynamic model ; stiffness matrix ; constant disturbance ; integrator backstepping ; Liapunov functions ; Barbalat lemma ; stability
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mechanical Engineering, Materials Science, Production Engineering, Mining and Metallurgy, Traffic Engineering, Precision Mechanics
    Notes: Abstract A robust regulator for flexible-joint robots is proposed, which yields constant torque disturbance rejection acting on the links. The design uses the integrator backstepping technique [4,5] to cancel nonlinearities and disturbance not in the range space of the control. Stability of the closed loop system is shown using iterative Liapunov functions.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1007947416837
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 57
    Electronic Resource
    Electronic Resource
    Forward Assembly Planning Based on Stability (1997)
    Springer
    Journal of intelligent and robotic systems 19 (1997), S. 411-436 
    Details
    ISSN: 1573-0409
    Keywords: assembly planning ; stability ; robot ; forward ; operations
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mechanical Engineering, Materials Science, Production Engineering, Mining and Metallurgy, Traffic Engineering, Precision Mechanics
    Notes: Abstract The paper presents an approach to sequence planning consisting in determining assembly sequences defined in terms of mating and non-mating operations and based on a dynamic expansion of the assembly tree obtained using a knowledge base management system. The planner considers the case of a single-robot assembly workcell. The use of stability and the detailed definition of sequences also by means of several non-mating operations are shown to be powerful instruments in the control of the tree expansion. Forward assembly planning has been chosen, in order to minimize the number of stability checks. Backtracking is avoided by combining precedence relations and stability analysis. Hard and soft constrains are introduced to drive the tree expansion. Hard constraints are precedence relations and stability analysis. All operations are associated to costs, which are used as soft constraints. The operation based approach enables one to manage even non-mating operations and to easily overcome the linearity constraint. Costs enable the planner to manage the association among tools and components. The first section of the paper concerns Stability Analysis that is subdivided into Static and Dynamic Stability Analysis. The former is mainly involved in analyzing gravity effects; the latter is mainly involved in evaluate inertia effects due to manipulation. Stability Analysis is implemented in a simplified form. Fundamental assumptions are: no rotational equilibrium condition is considered; for each reaction force only direction and versus, but not magnitude, are considered; friction is neglected. The second section discusses the structure of the planner and its implementation. The planner is a rule based system. Forward chaining and hypothetical reasoning are the inference strategies used. The knowledge base and the data base of the system are presented and the advantages obtained using a rule based system are discussed. The third section shows two planning examples, showing the performance of the system in a simple case and in an industrial test case, the assembly of a microwave branching filter composed of 26 components.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1007928631050
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 58
    Electronic Resource
    Electronic Resource
    Stable Neuro-Adaptive Control for Robots with the Upper Bound Estimation on the Neural Approximation Errors (1999)
    Springer
    Journal of intelligent and robotic systems 26 (1999), S. 91-100 
    Details
    ISSN: 1573-0409
    Keywords: robots ; neural networks ; adaptiveness ; stability ; approximation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mechanical Engineering, Materials Science, Production Engineering, Mining and Metallurgy, Traffic Engineering, Precision Mechanics
    Notes: Abstract An indirect adaptive control approach is developed in this paper for robots with unknown nonlinear dynamics using neural networks (NNs). A key property of the proposed approach is that the actual joint angle values in the control law are replaced by the desired joint angles, angle velocities and accelerators, and the bound on the NN reconstruction errors is assumed to be unknown. Main theoretical results for designing such a neuro-controller are given, and the control performance of the proposed controller is verified with simulation studies.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1008195720685
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 59
    Electronic Resource
    Electronic Resource
    The optimal control approach to generalized multiprocessor scheduling (1996)
    Springer
    Algorithmica 15 (1996), S. 17-49 
    Details
    ISSN: 1432-0541
    Keywords: Scheduling ; Multiprocessor scheduling ; Parallel algorithms ; NP-completeness ; Theoretical computer science ; Operations research ; Optimal control
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we present several new results in the theory of homogeneous multiprocessor scheduling. We start with some assumptions about the behavior of tasks, with associated precedence constraints, as processor power is applied. We assume that as more processors are applied to a task, the time taken to compute it decreases, yielding some speedup. Because of communication, synchronization, and task scheduling overhead, this speedup increases less than linearly with the number of processors applied. We also assume that the number of processors which can be assigned to a task is a continuous variable, with a view to exploiting continuous mathematics. The optimal scheduling problem is to determine the number of processors assigned to each task, and task sequencing, to minimize the finishing time. These assumptions allow us to recast the optimal scheduling problem in a form which can be addressed by optimal control theory. Various theorems can be proven which characterize the optimal scheduling solution. Most importantly, for the special case where the speedup function of each task isp α , wherep is the amount of processing power applied to the task, we can directly solve our equations for the optimal solution. In this case, for task graphs formed from parallel and series connections, the solution can be derived by inspection. The solution can also be shown to be shortest path from the initial to the final state, as measured by anl 1/α distance metric, subject to obstacle constraints imposed by the precedence constraints.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01942605
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 60
    Electronic Resource
    Electronic Resource
    Strongly adaptive token distribution (1996)
    Springer
    Algorithmica 15 (1996), S. 413-427 
    Details
    ISSN: 1432-0541
    Keywords: Parallel algorithms ; Token distribution
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The token distribution (TD) problem, an abstract static variant of load balancing, is defined as follows: letM be a (parallel processor) network with setP of processors. Initially, each processorP ∈P has a certain amountl(P) of tokens. The goal of a TD algorithm, run onM, is to distribute the tokens evenly among the processors. In this paper we introduce the notion of strongly adaptive TD algorithms, i.e., algorithms whose running times come close to the best possible runtime, the off-line complexity of the TD problem, for each individual initial token distributionl. Until now, only weakly adaptive algorithms have been considered, where the running time is measured in terms of the maximum initial load max{l(P)∥P ∈P}. We design an almost optimal, strongly adaptive algorithm on mesh-connected networks of arbitrary dimension extended by a single 1-bit bus. This result shows that an on-line TD algorithm can come close to the optimal (off-line) bound for each individual initial load. Furthermore, we exactly characterize the off-line complexity of arbitrary initial token distributions on arbitrary networks. As an intermediate result, we design almost optimal weakly adaptive algorithms for TD on mesh-connected networks of arbitrary dimension.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01955042
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 61
    Electronic Resource
    Electronic Resource
    An efficient parallel algorithm for finding rectangular duals of plane triangular graphs (1995)
    Springer
    Algorithmica 13 (1995), S. 553-572 
    Details
    ISSN: 1432-0541
    Keywords: Parallel algorithms ; Plane graphs ; Rectangular duals
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present an efficient parallel algorithm for constructing rectangular duals of plane triangular graphs. This problem finds applications in VLSI design and floor-planning problems. No NC algorithm for solving this problem was previously known. The algorithm takesO(log2 n) time withO(n) processors on a CRCW PRAM, wheren is the number of vertices of the graph.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01189069
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 62
    Electronic Resource
    Electronic Resource
    Designing checkers for programs that run in parallel (1996)
    Springer
    Algorithmica 15 (1996), S. 287-301 
    Details
    ISSN: 1432-0541
    Keywords: Parallel algorithms ; Program result checking
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Program correctness for parallel programs is an even more problematic issue than for serial programs. We extend the theory of program result checking to parallel programs, and find general techniques for designing such result checkers that work for many basic problems in parallel computation. These result checkers are simple to program and are more efficient than the actual computation of the result. For example, sorting, multiplication, parity, the all-pairs shortest-path problem and majority all have constant depth result checkers, and the result checkers for all but the last problem use a linear number of processors. We show that there are P-complete problems (evaluating straight-line programs, linear programming) that have very fast, even constant depth, result checkers.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01961540
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 63
    Electronic Resource
    Electronic Resource
    Fast deterministic selection on mesh-connected processor arrays (1996)
    Springer
    Algorithmica 15 (1996), S. 319-331 
    Details
    ISSN: 1432-0541
    Keywords: Parallel algorithms ; Mesh-connected computer ; Selection ; Deterministic
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present a deterministic algorithm for selecting the element of rankk amongN=n 2 elements, 1≤k≤N, on ann×n mesh-connected processor array in 1.45n parallel computation steps, using constant-sized queues (for large enoughn). This is a considerable improvement over the best previous deterministic algorithm, which was based upon sorting and requires2n+o(n) steps. Our algorithm can be generalized to solve the problem of selection on higher-dimensional meshes. In particular, we present an algorithm for the three-dimensional mesh which achieves a time bound better than any of the previously known deterministic results.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01961542
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 64
    Electronic Resource
    Electronic Resource
    Parallel algorithms for arrangements (1996)
    Springer
    Algorithmica 15 (1996), S. 104-125 
    Details
    ISSN: 1432-0541
    Keywords: Parallel algorithms ; Computational geometry ; Arrangement problem ; Incremental algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We give the first efficient parallel algorithms for solving the arrangement problem. We give a deterministic algorithm for the CREW PRAM which runs in nearly optimal bounds ofO (logn log* n) time andn 2/logn processors. We generalize this to obtain anO (logn log* n)-time algorithm usingn d /logn processors for solving the problem ind dimensions. We also give a randomized algorithm for the EREW PRAM that constructs an arrangement ofn lines on-line, in which each insertion is done in optimalO (logn) time usingn/logn processors. Our algorithms develop new parallel data structures and new methods for traversing an arrangement.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01941684
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 65
    Electronic Resource
    Electronic Resource
    Sweep methods for parallel computational geometry (1996)
    Springer
    Algorithmica 15 (1996), S. 126-153 
    Details
    ISSN: 1432-0541
    Keywords: Parallel algorithms ; Computational geometry ; Constructive solid geometry ; Hidden-line elimination ; Plane sweeping
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we give efficient parallel algorithms for a number of problems from computational geometry by using versions of parallel plane sweeping. We illustrate our approach with a number of applications, which include: General hidden-surface elimination (even if the overlap relation contains cycles). CSG boundary evaluation. Computing the contour of a collection of rectangles. Hidden-surface elimination for rectangles. There are interesting subproblems that we solve as a part of each parallelization. For example, we give an optimal parallel method for building a data structure for line-stabbing queries (which, incidentally, improves the sequential complexity of this problem). Our algorithms are for the CREW PRAM, unless otherwise noted.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01941685
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 66
    Electronic Resource
    Electronic Resource
    Parallel construction of binary trees with near optimal weighted path length (1996)
    Springer
    Algorithmica 15 (1996), S. 172-192 
    Details
    ISSN: 1432-0541
    Keywords: Huffman trees ; Near optimal trees ; Optimal trees ; Parallel algorithms ; PRAM ; Prefix codes
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present parallel algorithms to construct binary trees with almost optimal weighted path length. Specifically, assuming that weights are normalized (to sum up to one) and error refers to the (absolute) difference between the weighted path length of a given tree and the optimal tree with the same weights, we present anO (logn)-time andn(log lognl logn)-EREW-processor algorithm which constructs a tree with error less than 0.18, andO (k logn log* n)-time andn-CREW-processor algorithm which produces a tree with error at most l/n k , and anO (k 2 logn)-time andn 2-CREW-processor algorithm which produces a tree with error at most l/n k . As well, we describe two sequential algorithms, anO(kn)-time algorithm which produces a tree with error at most l/n k , and anO(kn)-time algorithm which produces a tree with error at most $$1/2^{n2^k }$$ . The last two algorithms use different computation models.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01941687
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 67
    Electronic Resource
    Electronic Resource
    Balancing minimum spanning trees and shortest-path trees (1995)
    Springer
    Algorithmica 14 (1995), S. 305-321 
    Details
    ISSN: 1432-0541
    Keywords: Minimum spanning trees ; Graph algorithms ; Parallel algorithms ; Shortest paths
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We give a simple algorithm to find a spanning tree that simultaneously approximates a shortest-path tree and a minimum spanning tree. The algorithm provides a continuous tradeoff: given the two trees and aγ〉0, the algorithm returns a spanning tree in which the distance between any vertex and the root of the shortest-path tree is at most 1+√2γ times the shortest-path distance, and yet the total weight of the tree is at most 1+√2/γ times the weight of a minimum spanning tree. Our algorithm runs in linear time and obtains the best-possible tradeoff. It can be implemented on a CREW PRAM to run a logarithmic time using one processor per vertex.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01294129
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 68
    Electronic Resource
    Electronic Resource
    An efficient parallel algorithm for shortest paths in planar layered digraphs (1995)
    Springer
    Algorithmica 14 (1995), S. 322-339 
    Details
    ISSN: 1432-0541
    Keywords: Parallel algorithms ; Shortest paths ; Planar separators
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Computing shortest paths in a directed graph has received considerable attention in the sequential RAM model of computation. However, developing a polylog-time parallel algorithm that is close to the sequential optimal in terms of the total work done remains an elusive goal. We present a first step in this direction by giving efficient parallel algorithms for shortest paths in planar layered digraphs. We show that these graphs admit special kinds of separators calledone- way separators which allow the paths in the graph to cross it only once. We use these separators to give divide- and -conquer solutions to the problem of finding the shortest paths between any two vertices. We first give a simple algorithm that works in the CREW model and computes the shortest path between any two vertices in ann-node planar layered digraph in timeO(log2 n) usingn/logn processors. We then use results of Aggarwal and Park [1] and Atallah [4] to improve the time bound toO(log2 n) in the CREW model andO(logn log logn) in the CREW model. The processor bounds still remain asn/logn for the CREW model andn/log logn for the CRCW model.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01294130
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 69
    Electronic Resource
    Electronic Resource
    Finding all periods and initial palindromes of a string in parallel (1995)
    Springer
    Algorithmica 14 (1995), S. 355-366 
    Details
    ISSN: 1432-0541
    Keywords: Parallel algorithms ; Lower bounds ; Comparison model ; Strings ; Periods ; Palindromes
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract An optimalO(log logn)-time CRCW-PRAM algorithm for computing all period lengths of a string is presented. Previous parallel algorithms compute the period only if it is shorter than half of the length of the string. The algorithm can be used to find all initial palindromes of a string in the same time and processor bounds. Both algorithms are the fastest possible over a general alphabet. We derive a lower bound for finding initial palindromes by modifying a known lower bound for finding the period length of a string [9]. Whenp processors are available the bounds become Θ(⌈n/p⌉+log⌈1+p/n⌉2p).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01294132
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 70
    Electronic Resource
    Electronic Resource
    An optimal parallel algorithm for planar cycle separators (1995)
    Springer
    Algorithmica 14 (1995), S. 398-408 
    Details
    ISSN: 1432-0541
    Keywords: Cycle separators ; Depth-first search ; Planar graphs ; Parallel algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present an optimal parallel algorithm for computing a cycle separator of ann-vertex embedded planar undirected graph inO(logn) time onn/logn processors. As a consequence, we also obtain an improved parallel algorithm for constructing a depth-first search tree rooted at any given vertex in a connected planar undirected graph in O(log2 n) time on n/logn processors. The best previous algorithms for computing depth-first search trees and cycle separators achieved the same time complexities, but withn processors. Our algorithms run on a parallel random access machine that permits concurrent reads and concurrent writes in its shared memory and allows an arbitrary processor to succeed in case of a write conflict.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01192047
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 71
    Electronic Resource
    Electronic Resource
    Squares, cubes, and time-space efficient string searching (1995)
    Springer
    Algorithmica 13 (1995), S. 405-425 
    Details
    ISSN: 1432-0541
    Keywords: Analysis of algorithms ; Algorithms on strings ; Pattern matching ; String matching ; Periods of words ; Parallel algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We address several technical problems related to the time-space optimal string-matching algorithm of Galil and Seiferas (called the GS algorithm). This algorithm contains a parameterk on which the complexity depends and that originally satisfiesk ≥ 4. We show thatk=3 is the least integer for which the GS algorithm works. This value of the parameterk also minimizes the time of the search phase of the string-searching algorithm. With the parameterk=2 we consider a simpler version of the algorithm working in linear time and logarithmic space. This algorithm is based on the following fact: any word of lengthn starts by less than logΦ n squares of primitive prefixes. Fibonacci words have a logarithmic number of square prefixes. Hence, the combinatorics of prefix squares and cubes is essential for string-matching with small memory. We give a time-space optimal sequential computation of the period of a word based on the GS algorithm. The latter corrects the algorithm given in [GS2] for the computation of periods. We present an optimal parallel algorithm for pattern preprocessing. This paper also provides a cleaner version and a simpler analysis of the GS algorithm.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01190846
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 72
    Electronic Resource
    Electronic Resource
    Communication-efficient parallel algorithms for distributed random-access machines (1988)
    Springer
    Algorithmica 3 (1988), S. 53-77 
    Details
    ISSN: 1432-0541
    Keywords: Conservative algorithm ; Distributed random-access machine ; Fat-trees ; Load factor ; Parallel algorithms ; PRAM ; Tree contraction ; Treefix computation ; Volume-universal networks
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper introduces a model for parallel computation, called thedistributed randomaccess machine (DRAM), in which the communication requirements of parallel algorithms can be evaluated. A DRAM is an abstraction of a parallel computer in which memory accesses are implemented by routing messages through a communication network. A DRAM explicitly models the congestion of messages across cuts of the network. We introduce the notion of aconservative algorithm as one whose communication requirements at each step can be bounded by the congestion of pointers of the input data structure across cuts of a DRAM. We give a simple lemma that shows how to “shortcut” pointers in a data structure so that remote processors can communicate without causing undue congestion. We giveO(lgn)-step, linear-processor, linear-space, conservative algorithms for a variety of problems onn-node trees, such as computing treewalk numberings, finding the separator of a tree, and evaluating all subexpressions in an expression tree. We giveO(lg2 n)-step, linear-processor, linear-space, conservative algorithms for problems on graphs of sizen, including finding a minimum-cost spanning forest, computing biconnected components, and constructing an Eulerian cycle. Most of these algorithms use as a subroutine a generalization of the prefix computation to trees. We show that any suchtreefix computation can be performed inO(lgn) steps using a conservative variant of Miller and Reif's tree-contraction technique.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01762110
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 73
    Electronic Resource
    Electronic Resource
    Parallel computational geometry (1988)
    Springer
    Algorithmica 3 (1988), S. 293-327 
    Details
    ISSN: 1432-0541
    Keywords: Parallel algorithms ; Computational geometry ; Data structures
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present efficient parallel algorithms for several basic problems in computational geometry: convex hulls, Voronoi diagrams, detecting line segment intersections, triangulating simple polygons, minimizing a circumscribing triangle, and recursive data-structures for three-dimensional queries.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01762120
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 74
    Electronic Resource
    Electronic Resource
    Parallel construction of a suffix tree with applications (1988)
    Springer
    Algorithmica 3 (1988), S. 347-365 
    Details
    ISSN: 1432-0541
    Keywords: Parallel algorithms ; CRCW RAM ; Suffix trees ; On-line string matching ; Longest repeated substring in a string ; Approximate string matching ; Skeleton trees ; Processor allocation techniques
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Many string manipulations can be performed efficiently on suffix trees. In this paper a CRCW parallel RAM algorithm is presented that constructs the suffix tree associated with a string ofn symbols inO(logn) time withn processors. The algorithm requires Θ(n 2) space. However, the space needed can be reduced toO(n 1+ɛ) for any 0〈 ɛ ≤1, with a corresponding slow-down proportional to 1/ɛ. Efficient parallel procedures are also given for some string problems that can be solved with suffix trees.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01762122
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 75
    Electronic Resource
    Electronic Resource
    Parallel algorithms for some functions of two convex polygons (1988)
    Springer
    Algorithmica 3 (1988), S. 535-548 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Convex polygons ; Parallel algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Let P andQ be two convex,n-vertex polygons. We consider the problem of computing, in parallel, some functions ofP andQ whenP andQ are disjoint. The model of parallel computation we consider is the CREW-PRAM, i.e., it is the synchronous shared-memory model where concurrent reads are allowed but no two processors can simultaneously attempt to write in the same memory location (even if they are trying to write the same thing). We show that a CREW-PRAM havingn 1/k processors can compute the following functions in O(k1+ɛ) time: (i) the common tangents betweenP andQ, and (ii) the distance betweenP andQ (and hence a straight line separating them). The positive constant ɛ can be made arbitrarily close to zero. Even with a linear number of processors, it was not previously known how to achieve constant time performance for computing these functions. The algorithm for problem (ii) is easily modified to detect the case of zero distance as well.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01762130
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 76
    Electronic Resource
    Electronic Resource
    An improved parallel algorithm for integer GCD (1990)
    Springer
    Algorithmica 5 (1990), S. 1-10 
    Details
    ISSN: 1432-0541
    Keywords: Greatest common divisor ; Parallel algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present a simple parallel algorithm for computing the greatest common divisor (gcd) of twon-bit integers in the Common version of the CRCW model of computation. The run-time of the algorithm in terms of bit operations isO(n/logn), usingn 1+ɛ processors, where ɛ is any positive constant. This improves on the algorithm of Kannan, Miller, and Rudolph, the only sublinear algorithm known previously, both in run time and in number of processors; they requireO(n log logn/logn),n 2 log2 n, respectively, in the same CRCW model. We give an alternative implementation of our algorithm in the CREW model. Its run-time isO(n log logn/logn), usingn 1+ɛ processors. Both implementations can be modified to yield the extended gcd, within the same complexity bounds.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840374
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 77
    Electronic Resource
    Electronic Resource
    Efficient parallel algorithms for graph problems (1990)
    Springer
    Algorithmica 5 (1990), S. 43-64 
    Details
    ISSN: 1432-0541
    Keywords: Biconnected components ; Connected components ; Minimum spanning trees ; Parallel algorithms ; Parallel processing ; PRAM ; Radix sort ; Spanning trees ; Tree computations
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present an efficient technique for parallel manipulation of data structures that avoids memory access conflicts. That is, this technique works on the Exclusive Read/Exclusive Write (EREW) model of computation, which is the weakest shared memory, MIMD machine model. It is used in a new parallel radix sort algorithm that is optimal for keys whose values are over a small range. Using the radix sort and known results for parallel prefix on linked lists, we develop parallel algorithms that efficiently solve various computations on trees and “unicycular graphs.” Finally, we develop parallel algorithms for connected components, spanning trees, minimum spanning trees, and other graph problems. All of the graph algorithms achieve linear speedup for all but the sparsest graphs.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840376
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 78
    Electronic Resource
    Electronic Resource
    Efficient parallel algorithms forr-dominating set andp-center problems on trees (1990)
    Springer
    Algorithmica 5 (1990), S. 129-145 
    Details
    ISSN: 1432-0541
    Keywords: Parallel algorithms ; Trees ; Optimization problems ; r-Dominating set ; p-Center
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We develop efficient parallel algorithms for ther-dominating set and thep-center problems on trees. On a concurrent-read exclusive-write PRAM, our algorithm for ther-dominating set problem runs inO(logn log logn) time withn processors. The algorithm for thep-center problem runs inO(log2 n log logn) time withn processors.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840381
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 79
    Electronic Resource
    Electronic Resource
    Parallel geometric algorithms on a mesh-connected computer (1990)
    Springer
    Algorithmica 5 (1990), S. 155-177 
    Details
    ISSN: 1432-0541
    Keywords: Parallel algorithms ; Computational geometry ; Mesh-connected computer ; Multipoint location ; Voronoi diagrams
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We show that a number of geometric problems can be solved on a √n × √n mesh-connected computer (MCC) inO(√n) time, which is optimal to within a constant factor, since a nontrivial data movement on an MCC requires Ω(√n) time. The problems studied here include multipoint location, planar point location, trapezoidal decomposition, intersection detection, intersection of two convex polygons, Voronoi diagram, the largest empty circle, the smallest enclosing circle, etc. TheO(√n) algorithms for all of the above problems are based on the classical divide-and-conquer problem-solving strategy.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840383
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 80
    Electronic Resource
    Electronic Resource
    Finding a minimal cover for binary images: An optimal parallel algorithm (1991)
    Springer
    Algorithmica 6 (1991), S. 624-657 
    Details
    ISSN: 1432-0541
    Keywords: Parallel algorithms ; Computational geometry ; Image compression ; Minimal square covers ; Orthogonal polygons ; Parallel prefix computations ; Minimal vertex covers ; Bipartite graphs
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a black-and-white image, represented by an array of √n × √n binary-valued pixels, we wish to cover the black pixels with aminimal set of (possibly overlapping) maximal squares. It was recently shown that obtaining aminimum square cover for a polygonal binary image with holes is NP-hard. We derive an optimal parallel algorithm for theminimal square cover problem, which for any desired computation timeT in [logn,n] runs on an EREW-PRAM with (n/T) processors. The cornerstone of our algorithm is a novel data structure, the cover graph, which compactly represents the covering relationships between the maximal squares of the image. The size of the cover graph is linear in the number of pixels. This algorithm has applications to problems in VLSI mask generation, incremental update of raster displays, and image compression.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01759065
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 81
    Electronic Resource
    Electronic Resource
    Computing convexity properties of images on a pyramid computer (1991)
    Springer
    Algorithmica 6 (1991), S. 658-684 
    Details
    ISSN: 1432-0541
    Keywords: Pyramid computer ; Convexity ; Digitized pictures ; Digital geometry ; Image processing ; Parallel computing ; Parallel algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present efficient parallel algorithms for using a pyramid computer to determine convexity properties of digitized black/white pictures and labeled figures. Algorithms are presented for deciding convexity, identifying extreme points of convex hulls, and using extreme points in a variety of fashions. For a pyramid computer with a base ofn simple processing elements arranged in ann 1/2 ×n 1/2 square, the running times of the algorithms range from Θ(logn) to find the extreme points of a convex figure in a digitized picture, to Θ(n 1/6) to find the diameter of a labeled figure, Θ(n 1/4 logn) to find the extreme points of every figure in a digitized picture, to Θ(n 1/2) to find the extreme points of every labeled set of processing elements. Our results show that the pyramid computer can be used to obtain efficient solutions to nontrivial problems in image analysis. We also show the sensitivity of efficient pyramid-computer algorithms to the rate at which essential data can be compressed. Finally, we show that a wide variety of techniques are needed to make full and efficient use of the pyramid architecture.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01759066
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 82
    Electronic Resource
    Electronic Resource
    Processor-time optimal parallel algorithms for digitized images on mesh-connected processor arrays (1991)
    Springer
    Algorithmica 6 (1991), S. 698-733 
    Details
    ISSN: 1432-0541
    Keywords: Digitized image problems ; Parallel algorithms ; Processor-time tradeoffs ; Mesh arrays
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present processor-time optimal parallel algorithms for several problems onn ×n digitized image arrays, on a mesh-connected array havingp processors and a memory of sizeO(n 2) words. The number of processorsp can vary over the range [1,n 3/2] while providing optimal speedup for these problems. The class of image problems considered here includes labeling the connected components of an image; computing the convex hull, the diameter, and a smallest enclosing box of each component; and computing all closest neighbors. Such problems arise in medium-level vision and require global operations on image pixels. To achieve optimal performance, several efficient data-movement and reduction techniques are developed for the proposed organization.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01759068
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 83
    Electronic Resource
    Electronic Resource
    An efficient parallel algorithm for computing a large independent set in a planar graph (1991)
    Springer
    Algorithmica 6 (1991), S. 801-815 
    Details
    ISSN: 1432-0541
    Keywords: Planar graphs ; Independent set ; Parallel algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Let α(G) denote the independence number of a graphG, that is the maximum number of pairwise independent vertices inG. We present a parallel algorithm that computes in a planar graphG = (V, E), an independent set $$I \subseteq V$$ such that ¦I¦≥ α (G)/2. The algorithm runs in timeOlog2 n) and requires a linear number of processors. This is achieved by denning a new set of reductions that can be executed “locally” and simultaneously; furthermore, it is shown that a constant fraction of the vertices in the graph are reducible. This is the best known approximation scheme when the number of processors available is linear; parallel implementation of known sequential algorithms requires many more processors.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01759072
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 84
    Electronic Resource
    Electronic Resource
    Deterministic parallel list ranking (1991)
    Springer
    Algorithmica 6 (1991), S. 859-868 
    Details
    ISSN: 1432-0541
    Keywords: List ranking ; Parallel algorithms ; List traversal
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we describe a simple parallel algorithm for list ranking. The algorithm is deterministic and runs inO(logn) time on an EREW PRAM withn/logn processors. The algorithm matches the performance of the Cole-Vishkin [CV3] algorithm but is simple and has reasonable constant factors.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01759076
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 85
    Electronic Resource
    Electronic Resource
    Optimal parallel algorithms for point-set and polygon problems (1992)
    Springer
    Algorithmica 7 (1992), S. 3-23 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Parallel algorithms ; Polygon ; All nearest-neighbor problem ; Kernel problem ; Convex hull
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we give parallel algorithms for a number of problems defined on point sets and polygons. All our algorithms have optimalT(n) * P(n) products, whereT(n) is the time complexity andP(n) is the number of processors used, and are for the EREW PRAM or CREW PRAM models. Our algorithms provide parallel analogues to well-known phenomena from sequential computational geometry, such as the fact that problems for polygons can oftentimes be solved more efficiently than point-set problems, and that nearest-neighbor problems can be solved without explicitly constructing a Voronoi diagram.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758749
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 86
    Electronic Resource
    Electronic Resource
    Efficient convexity and domination algorithms for fine- and medium-grain hypercube computers (1992)
    Springer
    Algorithmica 7 (1992), S. 51-75 
    Details
    ISSN: 1432-0541
    Keywords: Hypercube ; Parallel algorithms ; Convex hull ; Domination ; Computational geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper gives hypercube algorithms for some simple problems involving geometric properties of sets of points. The properties considered emphasize aspects of convexity and domination. Efficient algorithms are given for both fine- and medium-grain hypercube computers, including a discussion of implementation, running times and results on an Intel iPSC hypercube, as well as theoretical results. For both serial and parallel computers, sorting plays an important role in geometric algorithms for determining simple properties, often being the dominant component of the running time. Since the time required to sort data on a hypercube computer is still not fully understood, the running times of some of our algorithms for unsorted data are not completely determined. For both the fine- and medium-grain models, we show that faster expected-case running time algorithms are possible for point sets generated randomly. Our algorithms are developed for sets of planar points, with several of them extending to sets of points in spaces of higher dimension.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758751
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 87
    Electronic Resource
    Electronic Resource
    Data reduction and fast routing: A strategy for efficient algorithms for message-passing parallel computers (1992)
    Springer
    Algorithmica 7 (1992), S. 77-89 
    Details
    ISSN: 1432-0541
    Keywords: Parallel algorithms ; SIMD computers ; Hypercubes ; Routing
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper presents several algorithms for solving problems using massively parallel SIMD hypercube and shuffle-exchange computers. The algorithms solve a wide variety of problems, but they are related because they all use a common strategy. Specifically, all of the algorithms use a divide-and-conquer approach to solve a problem withN inputs using a parallel computer withP processors. The structural properties of the problem are exploited to assure that fewer thanN data items are communicated during the division and combination steps of the divide-and-conquer algorithm. This reduction in the amount of data that must be communicated is central to the efficiency of the algorithm. This paper addresses four problems, namely the multiple-prefix, data-dependent parallel-prefix, image-component-labeling, and closest-pair problems. The algorithms presented for the data-dependent parallel-prefix and closest-pair problems are the fastest known whenN ≥P and the algorithms for the multiple-prefix and image-component-labeling problems are the fastest known whenN is sufficiently large with respect toP.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758752
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 88
    Electronic Resource
    Electronic Resource
    Efficient parallel algorithms for path problems in directed graphs (1992)
    Springer
    Algorithmica 7 (1992), S. 631-648 
    Details
    ISSN: 1432-0541
    Keywords: Dominators ; Parallel algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we describe a technique for finding efficient parallel algorithms for problems on directed graphs that involve checking the existence of certain kinds of paths in the graph. This technique provides efficient algorithms for finding dominators in flow graphs, performing interval and loop analysis on reducible flow graphs, and finding the feedback vertices of a digraph. Each of these algorithms takesO(log2 n) time using the same number of processors needed for fast matrix multiplication. All of these bounds are for an EREW PRAM.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758780
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 89
    Electronic Resource
    Electronic Resource
    Line-segment intersection reporting in parallel (1992)
    Springer
    Algorithmica 8 (1992), S. 119-144 
    Details
    ISSN: 1432-0541
    Keywords: Parallel algorithms ; Computational geometry ; Line-segment intersection reporting ; Segment tree ; PRAM
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we give a parallel algorithm for line-segment intersection reporting in the plane. It runs in timeO(((n +k) logn log logn)/p) usingp processors on a concurrent-read-exclusive-write (CREW)-PRAM, wheren is the number of line segments,k is the number of intersections, andp ≤n +k.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758839
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 90
    Electronic Resource
    Electronic Resource
    On the parallel-decomposability of geometric problems (1992)
    Springer
    Algorithmica 8 (1992), S. 209-231 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Mesh-connected arrays of processors ; Parallel algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract There is a large and growing body of literature concerning the solutions of geometric problems on mesh-connected arrays of processors. Most of these algorithms are optimal (i.e., run in timeO(n 1/d ) on ad-dimensionaln-processor array), and they all assume that the parallel machine is trying to solve a problem of sizen on ann-processor array. Here we investigate the situation where we have a mesh of sizep and we are interested in using it to solve a problem of sizen 〉p. The goal we seek is to achieve, when solving a problem of sizen 〉p, the same speed up as when solving a problem of sizep. We show that for many geometric problems, the same speedup can be achieved when solving a problem of sizen 〉p as when solving a problem of sizep.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758844
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 91
    Electronic Resource
    Electronic Resource
    A parallel algorithm for approximating the minimum cycle cover (1993)
    Springer
    Algorithmica 9 (1993), S. 23-31 
    Details
    ISSN: 1432-0541
    Keywords: Parallel algorithms ; Cycles ; Cycle cover
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We address the problem of approximating aminimum cycle cover in parallel. We give the first efficient parallel algorithm for finding an approximation to aminimum cycle cover. Our algorithm finds a cycle cover whose size is within a factor of 0(1 +n logn/(m + n) of the minimum-sized cover usingO(log2 n) time on (m + n)/logn processors.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01185336
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 92
    Electronic Resource
    Electronic Resource
    Parallel methods for visibility and shortest-path problems in simple polygons (1992)
    Springer
    Algorithmica 8 (1992), S. 461-486 
    Details
    ISSN: 1432-0541
    Keywords: Parallel algorithms ; Computational geometry ; Data structures ; Visibility ; Polygons ; CREW PRAM
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we give efficient parallel algorithms for solving a number of visibility and shortest-path problems for simple polygons. Our algorithms all run inO(logn) time and are based on the use of a new data structure for implicitly representing all shortest paths in a simple polygonP, which we call thestratified decomposition tree. We use this approach to derive efficient parallel methods for computing the visibility ofP from an edge, constructing the visibility graph of the vertices ofP (using an output-sensitive number of processors), constructing the shortest-path tree from a vertex ofP, and determining all-farthest neighbors for the vertices inP. The computational model we use is the CREW PRAM.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758856
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 93
    Electronic Resource
    Electronic Resource
    Sieve algorithms for perfect power testing (1993)
    Springer
    Algorithmica 9 (1993), S. 313-328 
    Details
    ISSN: 1432-0541
    Keywords: Perfect powers ; Number theoretic algorithms ; Riemann hypothesis ; Newton's method ; Sieve algorithms ; Parallel algorithms ; Average-case analysis
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A positive integern is a perfect power if there exist integersx andk, both at least 2, such thatn=x k . The usual algorithm to recognize perfect powers computes approximatekth roots fork≤log 2 n, and runs in time O(log3 n log log logn). First we improve this worst-case running time toO(log3 n) by using a modified Newton's method to compute approximatekth roots. Parallelizing this gives anNC 2 algorithm. Second, we present a sieve algorithm that avoidskth-root computations by seeing if the inputn is a perfectkth power modulo small primes. Ifn is chosen uniformly from a large enough interval, the average running time isO(log2 n). Third, we incorporate trial division to give a sieve algorithm with an average running time ofO(log2 n/log2 logn) and a median running time ofO(logn). The two sieve algorithms use a precomputed table of small primes. We give a heuristic argument and computational evidence that the largest prime needed in this table is (logn)1+O(1); assuming the Extended Riemann Hypothesis, primes up to (logn)2+O(1) suffice. The table can be computed in time roughly proportional to the largest prime it contains. We also present computational results indicating that our sieve algorithms perform extremely well in practice.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01228507
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 94
    Electronic Resource
    Electronic Resource
    Optimal parallel algorithms for multiple updates of minimum spanning trees (1993)
    Springer
    Algorithmica 9 (1993), S. 357-381 
    Details
    ISSN: 1432-0541
    Keywords: CREW PRAM ; Parallel algorithms ; Optimality ; Updates ; Minimum spanning tree
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Parallel updates of minimum spanning trees (MSTs) have been studied in the past. These updates allowed a single change in the underlying graph, such as a change in the cost of an edge or an insertion of a new vertex. Multiple update problems for MSTs are concerned with handling more than one such change. In the sequential case multiple update problems may be solved using repeated applications of an efficient algorithm for a single update. However, for efficiency reasons, parallel algorithms for multiple update problems must consider all changes to the underlying graph simultaneously. In this paper we describe parallel algorithms for updating an MST whenk new vertices are inserted or deleted in the underlying graph, when the costs ofk edges are changed, or whenk edge insertions and deletions are performed. For multiple vertex insertion update, our algorithm achieves time and processor bounds ofO(log n·logk) and nk/(logn·logk), respectively, on a CREW parallel random access machine. These bounds are optimal for dense graphs. A novel feature of this algorithm is a transformation of the previous MST andk new vertices to a bipartite graph which enables us to obtain the above-mentioned bounds.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01228509
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 95
    Electronic Resource
    Electronic Resource
    Finding least-weight subsequences with fewer processors (1993)
    Springer
    Algorithmica 9 (1993), S. 615-628 
    Details
    ISSN: 1432-0541
    Keywords: Parallel algorithms ; Dynamic programming ; Monotone matrix
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract By restricting weight functions to satisfy the quadrangle inequality or the inverse quadrangle inequality, significant progress has been made in developing efficient sequential algorithms for the least-weight subsequence problem [10], [9], [12], [16]. However, not much is known on the improvement of the naive parallel algorithm for the problem, which is fast but demands too many processors (i.e., it takesO(log2 n) time on a CREW PRAM with n3/logn processors). In this paper we show that if the weight function satisfies the inverse quadrangle inequality, the problem can be solved on a CREW PRAM in O(log2 n log logn) time withn/log logn processors, or in O(log2 n) time withn logn processors. Notice that the processor-time complexity of our algorithm is much closer to the almost linear-time complexity of the best-known sequential algorithm [12].
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01190159
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 96
    Electronic Resource
    Electronic Resource
    Mapping dynamic programming onto modular linear systolic arrays (1993)
    Springer
    Distributed computing 6 (1993), S. 165-179 
    Details
    ISSN: 1432-0452
    Keywords: Parallel algorithms ; Linear systolic arrays ; Modular arrays ; Complexity ; Dynamic Programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Summary In this paper we propose a novel way of deriving a family of fully-pipelined linear systolic algorithms for the computation of the solutions of a dynamic programming problem. In many instances, modularity is an important feature of these algorithms. One may simply add more processors to the array as the size of the problem increases. Each cell has a fixed amount of local storage α and the time delay between two consecutive cells of the array is constant. The time complexity and the number of cells in our array tend ton 2+O(n) andn 2/α +O(n), respectively, as α increases. This represents the best known performance for such an algorithm.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02242705
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 97
    Electronic Resource
    Electronic Resource
    Technical note: Bias and the quantification of stability (1995)
    Springer
    Machine learning 20 (1995), S. 23-33 
    Details
    ISSN: 0885-6125
    Keywords: stability ; bias ; accuracy ; repeatability ; agreement ; similarity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Research on bias in machine learning algorithms has generally been concerned with the impact of bias on predictive accuracy. We believe that there are other factors that should also play a role in the evaluation of bias. One such factor is the stability of the algorithm; in other words, the repeatability of the results. If we obtain two sets of data from the same phenomenon, with the same underlying probability distribution, then we would like our learning algorithm to induce approximately the same concepts from both sets of data. This paper introduces a method for quantifying stability, based on a measure of the agreement between concepts. We also discuss the relationships among stability, predictive accuracy, and bias.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00993473
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 98
    Electronic Resource
    Electronic Resource
    A reinforcement connectionist approach to robot path finding in non-maze-like environments (1992)
    Springer
    Machine learning 8 (1992), S. 363-395 
    Details
    ISSN: 0885-6125
    Keywords: Connectionism ; reinforcement learning ; robot path finding ; stability ; reactive systems
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract This paper presents a reinforcement connectionist system which finds and learns the suitable situation-action rules so as to generate feasible paths for a point robot in a 2D environment with circular obstacles. The basic reinforcement algorithm is extended with a strategy for discovering stable solution paths. Equipped with this strategy and a powerful codification scheme, the path-finder (i) learns quickly, (ii) deals with continuous-valued inputs and outputs, (iii) exhibits good noise-tolerance and generalization capabilities, (iv) copes with dynamic environments, and (v) solves an instance of the path finding problem with strong performance demands.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00992702
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 99
    Electronic Resource
    Electronic Resource
    A Reinforcement Connectionist Approach to Robot Path Finding in Non-Maze-Like Environments (1992)
    Springer
    Machine learning 8 (1992), S. 363-395 
    Details
    ISSN: 0885-6125
    Keywords: Connectionism ; reinforcement learning ; robot path finding ; stability ; reactive systems
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract This paper presents a reinforcement connectionist system which finds and learns the suitable situation-action rules so as to generate feasible paths for a point robot in a 2D environment with circular obstacles. The basic reinforcement algorithm is extended with a strategy for discovering stable solution paths. Equipped with this strategy and a powerful codification scheme, the path-finder (i) learns quickly, (ii) deals with continuous-valued inputs and outputs, (iii) exhibits good noise-tolerance and generalization capabilities, (iv) copes with dynamic environments, and (v) solves an instance of the path finding problem with strong performance demands.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1022684924132
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 100
    Electronic Resource
    Electronic Resource
    Technical Note: Bias and the Quantification of Stability (1995)
    Springer
    Machine learning 20 (1995), S. 23-33 
    Details
    ISSN: 0885-6125
    Keywords: stability ; bias ; accuracy ; repeatability ; agreement ; similarity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Research on bias in machine learning algorithms has generally been concerned with the impact of bias on predictive accuracy. We believe that there are other factors that should also play a role in the evaluation of bias. One such factor is the stability of the algorithm; in other words, the repeatability of the results. If we obtain two sets of data from the same phenomenon, with the same underlying probability distribution, then we would like our learning algorithm to induce approximately the same concepts from both sets of data. This paper introduces a method for quantifying stability, based on a measure of the agreement between concepts. We also discuss the relationships among stability, predictive accuracy, and bias.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1022682001417
    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...