Foundations of Software Technology and Theoretical Computer by Micha Sharir (auth.), C. Pandu Rangan, V. Raman, R.

By Micha Sharir (auth.), C. Pandu Rangan, V. Raman, R. Ramanujam (eds.)

This booklet constitutes the refereed lawsuits of the nineteenth convention on Foundations of software program expertise and Theoretical computing device technological know-how, FSTTCS'99, held in Chennai, India, in December 1999.
The 30 revised complete papers offered have been rigorously reviewed and chosen from a complete of eighty four submissions. additionally integrated are six invited contributions. The papers provided deal with all present concerns in theoretical computing device technological know-how and programming concept.

Show description

Read or Download Foundations of Software Technology and Theoretical Computer Science: 19th Conference Chennai, India, December 13-15, 1999 Proceedings PDF

Best international conferences and symposiums books

Object-Oriented Programming: 8th European Conference, ECOOP '94 Bologna, Italy, July 4–8, 1994 Proceedings

This quantity includes the court cases of the eighth eu convention on Object-Oriented Programming (ECCOP '94), held in Bologna, Italy in July 1994. ECOOP is the optimum eu occasion on object-oriented programming and expertise. The 25 complete refereed papers offered within the quantity have been chosen from 161 submissions; they're grouped in periods on classification layout, concurrency, styles, declarative programming, implementation, specification, dispatching, and event.

Principles of Data Mining and Knowledge Discovery: First European Symposium, PKDD '97 Trondheim, Norway, June 24–27, 1997 Proceedings

This ebook constitutes the refereed court cases of the 1st eu Symposium on rules of knowledge Mining and data Discovery, PKDD '97, held in Trondheim, Norway, in June 1997. the amount offers a complete of 38 revised complete papers including abstracts of 1 invited speak and 4 tutorials.

Interactive Distributed Multimedia Systems and Telecommunication Services: 5th International Workshop, IDMS'98 Oslo, Norway, September 8–11, 1998 Proceedings

This booklet constitutes the refereed complaints of the fifth overseas Workshop on Interactive dispensed Multimedia structures and Telecommunication companies, IDMS'98, held in Oslo, Norway, in September 1998. The 23 revised complete papers provided have been conscientiously chosen from a complete of sixty eight submissions.

Current Trends in Database Technology – EDBT 2006: EDBT 2006 Workshops PhD, DataX, IIDB, IIHA, ICSNW, QLQP, PIM, PaRMA, and Reactivity on the Web, Munich, Germany, March 26-31, 2006, Revised Selected Papers

This publication constitutes the completely refereed joint post-proceedings of 9 workshops held as a part of the tenth overseas convention on Extending Database expertise, EDBT 2006, held in Munich, Germany in March 2006. The 70 revised complete papers offered have been chosen from various submissions in the course of rounds of reviewing and revision.

Extra resources for Foundations of Software Technology and Theoretical Computer Science: 19th Conference Chennai, India, December 13-15, 1999 Proceedings

Example text

22, 23, 23, 31, 31 11. : Combine and conquer. Algorithmica 18 (1997) 51–73. 22 12. : A fast algorithm for particle simulations. Journal of Computational Physics 73 (1987) 325–348. 28, 28 13. : A data structure for dynamically maintaining rooted trees. Proc. ACM-SIAM Symposium on Discrete Algorithms (1993) 175–194. 22 14. : Query-Sensitive ray shooting. International Journal of Computational Geometry and Applications 7 (1997) 317–347. 22 Dynamic Compressed Hyperoctrees with Application to the N-body Problem 33 15.

Hyperoctree is a popular data structure for organizing multidimensional point data. The main drawback of this data structure is that its size and the run-time of operations supported by it are dependent upon the distribution of the points. Clarkson rectified the distributiondependency in the size of hyperoctrees by introducing compressed hyperoctrees. He presents an O(n log n) expected time randomized algorithm to construct a compressed hyperoctree. In this paper, we give three deterministic algorithms to construct a compressed hyperoctree in O(n log n) time, for any fixed dimension d.

A DIAT tree T for S1 ∪ S2 can be constructed in O(|S1 | + |S2 |) time by merging T1 and T2 . To merge T1 and T2 , we start at their roots r1 and r2 . Suppose that at some stage during the execution of the algorithm, we are at node v1 in T1 and at node v2 in T2 with the task of merging the subtrees rooted at v1 and v2 . An invariant of the merging algorithm is that L(v1 ) and L(v2 ) cannot be disjoint. Furthermore, it can be asserted that L(v1 ) ∩ L(v2 ) ⊇ S(v1 ) ∪ S(v2 ). For convenience, assume that a node may be empty.

Download PDF sample

Rated 4.85 of 5 – based on 7 votes