8,261 research outputs found
Structures and Hyperstructures in Metabolic NetworksGraph-Theoretic Concepts in Computer Science
No full textAlgorithms for secure communication
No full textThe design of algorithms for sending confidential messages (i.e. messages that no one can read, except the intended receiver) goes back to the beginning of our civilization. However, before the widespread of modern computers, cryptography was practiced by few people: soldiers, or diplomats, or scientists fascinated by the problem of confidential communication. Cryptography algorithms designed in the past were ingenious transformations but were lacking a sound mathematical basis. Recently, the development of computers and of the Internet has opened up new applications of cryptography in business and society. To answer these needs, new algorithms have been developed that use sound mathematical techniques and have produced surprising results, which have opened up impressive possibilities that were considered unrealistic before.We will see examples of algorithms that use modular arithmetic (in which operations are performed modulo an integer) that are based on using functions that are easy to compute but difficult to invert. © Springer-Verlag Berlin Heidelberg 2013. All rights reserved
Dynamic algorithms for shortest paths in planar graphs
No full textAbstractWe propose data structures for maintaining shortest paths in planar graphs in which the weight of an edge is modified. Our data structures allow us to compute, after an update, the shortest-path tree rooted at an arbitrary query node in time O(nlog logn) and to perform an update in O((logn)3). Our data structure can be applied also to the problem of maintaining the maximum flow problem in an s–t planar network.As far as the all-pairs shortest-path problem is concerned, we are interested in computing the shortest distances between q pairs of nodes. We show how to obtain an o(n2) algorithm for computing the shortest path between q pairs of nodes whenever q = o(n2). We also consider the dynamic version of the problem in which we allow the modification of the weight of an edge
Feasibility Analysis of Sporadic Real-Time Multiprocessor Task Systems
No full textWe give the first algorithm for testing the feasibility of a system of sporadic
real-time tasks on a set of identical processors, solving an open problem in
the area of multiprocessor real-time scheduling~[S.~Baruah and K.~Pruhs,
Journal of Scheduling, 2009]. We also investigate the related notion of
schedulability and a notion that we call online feasibility. Finally, we show
that discrete-time schedules are as powerful as continuous-time schedules,
which answers another open question in the above mentioned survey
Feasibility Analysis of Sporadic Real-Time Multiprocessor Task Systems
No full textWe give the first algorithm for testing the feasibility of a system of sporadic real-time tasks on a set of identical processors, solving an open problem in the area of multiprocessor real-time scheduling (Baruah and Pruhs in Journal of Scheduling 13(6):577-582, 2009). We also investigate the related notion of schedulability and a notion that we call online feasibility. Finally, we show that discrete-time schedules are as powerful as continuous-time schedules, which answers another open question in the above mentioned survey
International ICST Conference on Theory and Practice of Algorithms in (Computer) Systems, TAPAS
No full textIn the light of continuously increasing interaction between communication and computing, there arise a number of interesting, and difficult algorithmic issues in diverse areas including coverage, mobility, routing, cooperation, capacity planning, scheduling, and power control. The aim of TAPAS is to provide a forum for presentation of original research in the design, implementation and evaluation of algorithms. TAPAS is dedicated to the use, design and evaluation of algorithms for combinatorial optimization problems (either efficient optimal or efficient approximation algorithms) and to real-world applications, engineering and experimental analysis of algorithms. It aims, in particular, at fostering the cooperation among researchers in computer science, networking, discrete mathematics, mathematical programming and operations research
THE WEIGHTED LIST UPDATE PROBLEM AND THE LAZY ADVERSARY
No full textThe list update problem consists in maintaining a dictionary as an unsorted linear list. Any request specifies an item to be found by sequential scanning through the list. After an item has been found, the list may be rearranged in order to reduce the cost of processing a sequence of requests. Several kinds of adversaries can be considered to analyze the behavior of heuristics for this problem. The move-to-front (MTF) heuristic is 2-competitive against a strong adversary, matching the deterministic lower bound for this problem [Sleator and Tarjan (1985)]. But, for this problem, moving elements does not help the adversary. A lazy adversary has the limitation that he can use only a static arrangement of the list to process (off-line) the sequence of requests: still, no algorithm can be better than 2-competitive against the lazy adversary [Bentley and McGeogh (1985)]. In this paper we consider the weighted list update problem (WLUP), where the cost of accessing an item depends on the item itself. It is shown that MTF is not competitive by any constant factor for this problem against a lazy adversary. Two heuristics, based on the MTF strategy, are presented for WLUP: random move-to-front is randomized and uses biased coins; counting move-to-front is deterministic, and replaces coins by counters. Both are shown to be 2-competitive against a lazy adversary. This is optimal for the deterministic case. We apply this approach for searching items in a tree, proving that any c-competitive heuristic for the weighted list update problem provides a c-competitive heuristic for the tree update problem
- …
