In this paper we determine the computational complexity of dynamic convex hull problem in planar case. We present a data structure that maintains finite set n points plane under insertion and deletion amortized O(log n) time per operation. The space usage is O(n). supports extreme point queries given direction, tangent through point, for neighboring on time. can be used to decide whether or not line intersects hull, inside hull. give lower bound asymptotic matches performance structure.

Given an alphabet $\Sigma$, a (directed) graph G whose edges are weighted and $\Sigma$-labeled, formal language $L\subseteq\Sigma^*$, the formal-language-constrained shortest/simple path problem consists of finding shortest (simple) p in complying with additional constraint that l(p) \in L$. Here denotes unique word obtained by concatenating $\Sigma$-labels along p. The main contributions this paper include following: We show is solvable efficiently polynomial time when L restricted to be...

We propose a version of cache oblivious search trees which is simpler than the previous proposal Bender, Demaine and Farach-Colton has same complexity bounds. In particular, our data structure avoids use weight balanced B-trees, can be implemented as just single array elements, without pointers. The also improves space utilization.For storing n uses (1 + e)n times element size memory, performs searches in worst case O(logBn) memory transfers, updates amortized O((log2n)/(eB)) range queries...

We consider efficient algorithms for exact time-table queries, i.e. that find optimal itineraries travelers using a train system. propose to use time-dependent networks as model and show advantages of this approach over space-time models.

Peer-to-peer systems rely on scalable overlay networks that enable efficient routing between its members. Hypercubic topologies facilitate such operations while each node only needs to connect a small number of other nodes. In contrast static communication networks, peer-to-peer allow nodes adapt their neighbor set over time in order react join and leave events failures. This paper shows how maintain robust manner. Concretely, we present distributed self-stabilizing algorithm constructs...

Abstract In this article, we study the train classification problem. Train basically is process of rearranging cars a in specified order, which can be regarded as special sorting This done railway installation called yard, and described by schedule. develop novel encoding schedules, allows characterizing methods simply classes schedules. Applying efficient encoding, achieve simpler, more precise analysis well‐known methods. Furthermore, elaborate valuable optimality condition inherent our...

We carry out an experimental analysis of a number shortest-path (routing) algorithms investigated in the context TRANSIMS (TRansportation ANalysis and SIMulation System) project. The main focus paper is to study how various heuristic as well exact solutions associated data structures affect computational performance software developed for realistic transportation networks. For this purpose we have used road network representing, with high degree resolution, Dallas Fort-Worth urban area.We...

Peer-to-peer systems rely on a scalable overlay network that enables efficient routing between its members. Hypercubic topologies facilitate such operations while each node only needs to connect small number of other nodes. In contrast static communication networks, peer-to-peer networks allow nodes adapt their neighbor set over time in order react join and leave events failures. This article shows how maintain robust manner. Concretely, we present distributed self-stabilizing algorithm...

We propose a version of cache oblivious search trees which is simpler than the previous proposal Bender, Demaine and Farach-Colton has same complexity bounds. In particular, our data structure avoids use weight balanced B-trees, can be implemented as just single array elements, without pointers. The also improves space utilization.<br /> <br />For storing n uses (1+epsilon)n times element size memory, performs searches in worst case O(log_B n) memory transfers, updates amortized...

Tandem mass spectrometry allows for high-throughput identification of complex protein samples. Searching tandem spectra against sequence databases is the main analysis method nowadays. Since many peptide variations are possible, including them in search space seems only logical. However, usually grows exponentially with number independent and may therefore overwhelm computational resources.We provide fast, cache-efficient algorithms to screen large spaces non-tryptic peptides, whole genomes,...

We analyze the problem of sparse-matrix dense-vector multiplication (SpMV) in I/O-model. The task SpMV is to compute y := Ax, where A a sparse N x matrix and are vectors. Here, sparsity expressed by parameter k that states has total at most kN nonzeros, i.e., an average number nonzeros per column. extreme choices for well studied special cases, namely k=1 permuting k=N dense matrix-vector multiplication.

Motivated by the asymmetric read and write costs of emerging non-volatile memory technologies, we study lower bounds for problems sorting, permuting multiplying a sparse matrix dense vector in external model (AEM). Given an AEM with internal (symmetric) size M, transfers between symmetric blocks B ratio ω costs, show Ω(min (N, ωN/B logω M/B N/B) bound cost N input elements. This also applies to problem sorting proves that existing algorithms are optimal within constant factor reasonable...

Modern computer networks support interesting new routing models in which traffic flows from a source sto destination t can be flexibly steered through sequence of waypoints, such as (hardware) middleboxes or (virtualized) network functions (VNFs), to create innovative services like service chains segment routing. While the benefits and technological challenges providing have been articulated studied intensively over last years, less is known about underlying algorithmic problems. The goal...