<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=undefined&type=result"></script>');
-->
</script>

COPY SCRIPT

For further information contact us at helpdesk@openaire.eu

Data structures maxima

Data structures' maxima

descriptionPublicationkeyboard_double_arrow_right Part of book or chapter of book , Article 01 Jan 1991 Belgium English Publisher:Springer Berlin HeidelbergJournal:SIAM Journal on Computing, volume 26, pages 1,006-1,042 (issn: 0097-5397, eissn: 1095-7111,

Authors: Louchard, Guy; Kenyon, Claire; Schott, René;

doi: 10.1007/3-540-54458-5_78 , 10.1137/s0097539791196603

handle: 2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/281734 , 2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/166328

Data structures maxima

- Summary
- Subjects
- Metrics

Abstract

Summary: The purpose of this paper is to analyze the maxima properties (value and position) of some data structures. Our theorems concern the distribution of these random variables. Previously known results usually dealt with the mean and sometimes the variance of the random variables. Many of our results rely on diffusion techniques. This is a very powerful tool that has already been used with some success in algorithm complexity analysis.

Country

Belgium

Related Organizations

French National Centre for Scientific Research
France
Université Libre de Bruxelles
Belgium
Centre national de la recherche scientifique
France

Keywords

diffusion techniques, Data structures, Probabilistic analysis of algorithms, Informatique générale, Analysis of algorithms and problem complexity, Diffusion techniques, probabilistic analysis of algorithms, queueing theory, Brownian bridges, Queueing theory (aspects of probability theory), Mathématiques, data structures, Informatique mathématique, Brownian motion, Diffusion processes, Applications of Brownian motions and diffusion theory (population genetics, absorption problems, etc.), Queuing theory

Impact byBIP!

	citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	12
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average