165 research outputs found
Modeling and Performance Analysis of Service Discovery Strategies in Ad Hoc Networks (Extended Abstract)
No full textMichel Barbeau Evangelos Kranakis School of Computer Science Carleton University Ottawa, Canada Email: fbarbeau,[email protected] Abstract---We define post-query strategies: these are time dependent post-query protocols that are being executed in rounds. We show how existing service discovery protocols, like Jini, Bluetooth, and SLP fit within this framework. We propose several new post-query strategies that can be used for locating a service in an ad-hoc network. These include: non-adaptive, deterministic, randomized, memoryless, incremental, and greedy. We analyze and evaluate several of these strategies and present results of our simulations. Our methodology for evaluating the performance and efficiency of such service discovery protocols can be useful in the context of ad-hoc networks
Fun with Algorithms6th International Conference, FUN 2012,
No full textThe proceedings contain 37 papers. The topics discussed include: distributed algorithms by forgetful mobile robots; stability and metastability of the logit dynamics of strategic games; the vulcan game of kal-toh: finding or making triconnected planar subgraphs; Scandinavian thins on top of cake: on the smallest one-size-fits-all box; the kissing problem: how to end a gathering when everyone kisses everyone else goodbye; train marshalling is fixed parameter tractable; conflict-free graph orientations with parity constraints; picture-hanging puzzles; optimal sensor networks for area monitoring using rotating and beam sensors; the Byzantine brides problem; lean programs, branch mispredictions, and sorting; on computer integrated rationalized crossword puzzle manufacturing; solving single-digit sudoku subproblems; to satisfy impatient web surfers is hard; and making life easier for firefighters
Structural RNA has lower folding energy than random RNA of the same dinucleotide frequency
No full textWe present results of computer experiments that indicate that several RNAs for which the native state (minimum free energy secondary structure) is functionally important (type III hammerhead ribozymes, signal recognition particle RNAs, U2 small nucleolar spliceosomal RNAs, certain riboswitches, etc.) all have lower folding energy than random RNAs of the same length and dinucleotide frequency. Additionally, we find that whole mRNA as well as 5'-UTR, 3'-UTR, and cds regions of mRNA have folding energies comparable to that of random RNA, although there may be a statistically insignificant trace signal in 3'-UTR and cds regions. Various authors have used nucleotide (approximate) pattern matching and the computation of minimum free energy as filters to detect potential RNAs in ESTs and genomes. We introduce a new concept of the asymptotic Z-score and describe a fast, whole-genome scanning algorithm to compute asymptotic minimum free energy Z-scores of moving-window contents. Asymptotic Z-score computations offer another filter, to be used along with nucleotide pattern matching and minimum free energy computations, to detect potential functional RNAs in ESTs and genomic regions
A survey of new results in coding with feedback and searching with lies
No full textDeppe C. A survey of new results in coding with feedback and searching with lies. In: Kranakis E, Haroutunian EA, Shahbazian E, eds. Aspects of network and information security. NATO Science for Peace and Security Series - D: Information and Communication Security. Vol 17. IOS Press: Amsterdam; 2008: 299-307.This paper is a continuation of [17]. It gives an overview of new results in the area of searching with errors and the related field of error-correcting coding from 2000 to 2005
Asynchronous deterministic rendezvous in graphs
No full textTwo mobile agents (robots) having distinct labels and located in nodes of an unknown anonymous connected graph have to meet.
We consider the asynchronous version of this well-studied rendezvous problem and we seek fast deterministic algorithms for it.
Since in the asynchronous setting, meeting at a node, which is normally required in rendezvous, is in general impossible, we relax
the demand by allowing meeting of the agents inside an edge as well. The measure of performance of a rendezvous algorithm is its
cost: for a given initial location of agents in a graph, this is the number of edge traversals of both agents until rendezvous is achieved.
If agents are initially situated at a distance D in an infinite line, we show a rendezvous algorithm with cost O(D|Lmin|2) when D
is known and O((D + |Lmax|)3) if D is unknown, where |Lmin| and |Lmax| are the lengths of the shorter and longer label of the
agents, respectively. These results still hold for the case of the ring of unknown size, but then we also give an optimal algorithm of
cost O(n|Lmin|), if the size n of the ring is known, and of cost O(n|Lmax|), if it is unknown. For arbitrary graphs, we show that
rendezvous is feasible if an upper bound on the size of the graph is known and we give an optimal algorithm of cost O(D|Lmin|) if
the topology of the graph and the initial positions are known to agents
Line Search for an Oblivious Moving Target
No full textConsider search on an infinite line involving an autonomous robot starting at
the origin of the line and an oblivious moving target at initial distance from it. The robot can change direction and move anywhere on the line
with constant maximum speed while the target is also moving on the line
with constant speed but is unable to change its speed or direction. The
goal is for the robot to catch up to the target in as little time as possible.
The classic case where and the target's initial distance is unknown
to the robot is the well-studied ``cow-path problem''. Alpert and Gal gave an
optimal algorithm for the case where a target with unknown initial distance
is moving away from the robot with a known speed . In this paper we design
and analyze search algorithms for the remaining possible knowledge situations,
namely, when and are known, when is known but is unknown, when
is known but is unknown, and when both and are unknown.
Furthermore, for each of these knowledge models we consider separately the case
where the target is moving away from the origin and the case where it is moving
toward the origin. We design algorithms and analyze competitive ratios for all
eight cases above. The resulting competitive ratios are shown to be optimal
when the target is moving towards the origin as well as when is known and
the target is moving away from the origin
Bundled crossings in embedded graphs
No full text\u3cp\u3eEdge crossings in a graph drawing are an important factor in the drawing’s quality. However, it is not just the presence of crossings that determines the drawing’s quality: any drawing of a nonplanar graph in the plane necessarily contains crossings, but the geometric structure of those crossings can have a significant impact on the drawing’s readability. In particular, the structure of two disjoint groups of locally parallel edges (bundles) intersecting in a complete crossbar (a bundled crossing) is visually simpler—even if it involves many individual crossings—than an equal number of random crossings scattered in the plane. In this paper, we investigate the complexity of partitioning the crossings of a given drawing of a graph into a minimum number of bundled crossings. We show that this problem is NP-hard, propose a constant-factor approximation scheme for the case of circular embeddings, where all vertices lie on the outer face, and show that the bundled crossings problem in general graphs is related to a minimum dissection problem.\u3c/p\u3
Divorcing made easy
No full textWe discuss the proportionally fair allocation of a set of indivisible items to k agents. We assume that each agent specifies only a ranking of the items from best to worst. Agents do not specify their valuations of the items. An allocation is proportionally fair if all agents believe that they have received their fair share of the value according to how they value the items.
We give simple conditions (and a fast algorithm) for determining whether the agents rankings give sufficient information to determine a proportionally fair allocation. An important special case is a divorce situation with two agents. For such a divorce situation, we provide a particularly simple allocation rule that should have applications in the real world
Amplifying the Security of One-Way Functions -- A Proof of Yao's XOR-Lemma
No full textIn this paper we give a consistent and simple proof for the XOR-Lemma which was hinted at by Yao and subsequently presented by him in lectures.
It can be found in print in "E. Kranakis, Primality and Cryptography, Wiley-Teubner Series in Computer Science, 1986". By the lemma we know that the security of any one-way function f:Xlongrightarrow { 0,1} can be substantially amplified if the function is replaced by the XOR with itself, namely by foplus f:X imes Xlongrightarrow { 0,1}, (x,y)longrightarrow f(x)oplus f(y).
Applications are in cryptography and complexity theory. However, the existence of one-way functions still remains an open problem
- …
