اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدNovel O(H(N)+N/H(N)) Algorithmic Techniques for Several Types of Queries and Updates on Rooted Trees and Lists
107
0
0.0
(
0
)
نشر من قبل
Mugurel Ionut Andreica
تاريخ النشر
2013
مجال البحث
الهندسة المعلوماتية
والبحث باللغة
English
تأليف
Mugurel Ionut Andreica
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
In this paper we present novel algorithmic techniques with a O(H(N)+N/H(N)) time complexity for performing several types of queries and updates on general rooted trees, binary search trees and lists of size N. For rooted trees we introduce a new compressed super-node tree representation which can be used for efficiently addressing a wide range of applications. For binary search trees we discuss the idea of globally rebuilding the entire tree in a fully balanced manner whenever the height of the tree exceeds the value of a conveniently chosen function of the number of tree nodes. In the end of the paper we introduce the H-list data structure which supports concatenation, split and several types of queries. Note that when choosing H(N)=sqrt(N) we obtain O(H(N)+N/H(N))=O(sqrt(N)).
قيم البحث
اقرأ أيضاً
Tree comparison metrics have proven to be an invaluable aide in the reconstruction and analysis of phylogenetic (evolutionary) trees. The path-length distance between trees is a particularly attractive measure as it reflects differences in tree shape
as well as differences between branch lengths. The distance equals the sum, over all pairs of taxa, of the squared differences between the lengths of the unique path connecting them in each tree. We describe an $O(n log n)$ time for computing this distance, making extensive use of tree decomposition techniques introduced by Brodal et al. (2004).
Three related analyses of $phi^4$ theory with $O(N)$ symmetry are presented. In the first, we review the $O(N)$ model over the $p$-adic numbers and the discrete renormalization group transformations which can be understood as spin blocking in an ultr
ametric context. We demonstrate the existence of a Wilson-Fisher fixed point using an $epsilon$ expansion, and we show how to obtain leading order results for the anomalous dimensions of low dimension operators near the fixed point. Along the way, we note an important aspect of ultrametric field theories, which is a non-renormalization theorem for kinetic terms. In the second analysis, we employ large $N$ methods to establish formulas for anomalous dimensions which are valid equally for field theories over the $p$-adic numbers and field theories on $mathbb{R}^n$. Results for anomalous dimensions agree between the first and second analyses when they can be meaningfully compared. In the third analysis, we consider higher derivativ
We use integral field spectroscopic (IFS) observations from Gemini North Multi-Object Spectrograph (GMOS-N) of a group of four H II regions and the surrounding gas in the central region of the blue compact dwarf (BCD) galaxy NGC 4670. At spatial scal
es of $sim$ 9 pc, we map the spatial distribution of a variety of physical properties of the ionised gas: internal dust attenuation, kinematics, stellar age, star-formation rate, emission line ratios and chemical abundances. The region of study is found to be photoionised. Using the robust direct T$_e$-method, we estimate metallicity, nitrogen-to-oxygen ratio and helium abundance of the four H II regions. The same parameters are also mapped for the entire region using the HII-CHI-mistry code. We find that log(N/O) is increased in the region where the Wolf-Rayet bump is detected.The region coincides with the continuum region, around which we detect a slight increase in He abundance. We estimate the number of WC4, WN2-4 and WN7-9 stars from the integrated spectrum of WR bump region. We study the relation between log(N/O) and 12 + log(O/H) using the spatially-resolved data of the FOV as well as the integrated data of the H II regions from ten BCDs. We find an unexpected negative trend between N/O and metallicity. Several scenarios are explored to explain this trend, including nitrogen enrichment, and variations in star formation efficiency via chemical evolution models.
The make-up of the outer planets, and many of their moons, are dominated by matter from the H-C-N-O chemical space, commonly assumed to originate from mixtures of hydrogen and the planetary ices H$_2$O, CH$_4$, and NH$_3$. In their interiors, these i
ces experience extreme pressure conditions, around 5 Mbar at the Neptune mantle-core boundary, and it is expected that they undergo phase transitions, decompose, and form entirely new compounds. In turn, this determines planets interior structure, thermal history, magnetic field generation, etc. Despite its importance, the H-C-N-O space has not been surveyed systematically. Asked simply: at high-pressure conditions, what compounds emerge within this space, and what governs their stability? Here, we report on results from an unbiased crystal structure search amongst H-C-N-O compounds at 5 Mbar to answer this question.
We investigate the cohomology rings of regular semisimple Hessenberg varieties whose Hessenberg functions are of the form $h=(h(1),ndots,n)$ in Lie type $A_{n-1}$. The main result of this paper gives an explicit presentation of the cohomology rings i
n terms of generators and their relations. Our presentation naturally specializes to Borels presentation of the cohomology ring of the flag variety and it is compatible with the representation of the symmetric group $mathfrak{S}_n$ on the cohomology constructed by J. Tymoczko. As a corollary, we also give an explicit presentation of the $mathfrak{S}_n$-invariant subring of the cohomology ring.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
