Search Constraints
Filtering by:
Publisher
Springer Berlin Heidelberg
Remove constraint Publisher: Springer Berlin Heidelberg
Number of results to display per page
Search Results
-
- Resource Type:
- Conference Proceeding
- Creator:
- Markou, Euripides, Kranakis, Evangelos, and Krizanc, Danny
- Abstract:
- We consider the rendezvous problem for identical mobile agents (i.e., running the same deterministic algorithm) with tokens in a synchronous torus with a sense of direction and show that there is a striking computational difference between one and more tokens. More specifically, we show that 1) two agents with a constant number of unmovable tokens, or with one movable token, each cannot rendezvous if they have o(log n) memory, while they can perform rendezvous with detection as long as they have one unmovable token and O(log n) memory; in contrast, 2) when two agents have two movable tokens each then rendezvous (respectively, rendezvous with detection) is possible with constant memory in an arbitrary n × m (respectively, n × n) torus; and finally, 3) two agents with three movable tokens each and constant memory can perform rendezvous with detection in a n × m torus. This is the first publication in the literature that studies tradeoffs between the number of tokens, memory and knowledge the agents need in order to meet in such a network.
- Date Created:
- 2006-07-10
-
- Resource Type:
- Conference Proceeding
- Creator:
- Kranakis, Evangelos, Morin, Pat, and Krizanc, Danny
- Abstract:
- We present a tradeoff between the expected time for two identical agents to rendez-vous on a synchronous, anonymous, oriented ring and the memory requirements of the agents. In particular, we show that there exists a 2t state agent, which can achieve rendez-vous on an n node ring in expected time O( n 2/2 t ∈+∈2 t ) and that any t/2 state agent requires expected time Ω( n 2/2 t ). As a corollary we observe that Θ(loglogn) bits of memory are necessary and sufficient to achieve rendez-vous in linear time.
- Date Created:
- 2008-05-12
-
- Resource Type:
- Conference Proceeding
- Creator:
- Dujmović, Vida, Wood, David, and Bose, Prosenjit
- Abstract:
- We prove that for all 0 ≤ t ≤ k and d ≥ 2k, every graph G with treewidth at most k has a 'large' induced subgraph H, where H has treewidth at most t and every vertex in H has degree at most d in G, The order of H depends on t, k, d, and the order of G. With t = k, we obtain large sets of bounded degree vertices. With t = 0, we obtain large independent sets of bounded degree. In both these cases, our bounds on the order of H are tight. For bounded degree independent sets in trees, we characterise the extremal graphs. Finally, we prove that an interval graph with maximum clique size k has a maximum independent set in which every vertex has degree at most 2k.
- Date Created:
- 2005-12-01
-
- Resource Type:
- Conference Proceeding
- Creator:
- Loke, R. K.S. and Oommen, B. John
- Abstract:
- We consider a problem which can greatly enhance the areas of cursive script recognition and the recognition of printed character sequences. This problem involves recognizing words/strings by processing their noisy subsequences. Let X* be any unknown word from a finite dictionary H. Let U be any arbitrary subsequence of X*. We study the problem of estimating X* by processing Y, a noisy version of U. Y contains substitution, insertion, deletion and generalized transposition errors — the latter occurring when transposed characters are themselves subsequently substituted. We solve the noisy subsequence recognition problem by defining and using the constrained edit distance between X ε H and Y subject to any arbitrary edit constraint involving the number and type of edit operations to be performed. An algorithm to compute this constrained edit distance has been presented. Using these algorithms we present a syntactic Pattern Recognition (PR) scheme which corrects noisy text containing all these types of errors. Experimental results which involve strings of lengths between 40 and 80 with an average of 30.24 deleted characters and an overall average noise of 68.69 % demonstrate the superiority of our system over existing methods.
- Date Created:
- 1995-01-01
-
- Resource Type:
- Conference Proceeding
- Creator:
- Jiang, Lei, Bertossi, Leopoldo, and Rizzolo, Flavio
- Abstract:
- We motivate, formalize and investigate the notions of data quality assessment and data quality query answering as context dependent activities. Contexts for the assessment and usage of a data source at hand are modeled as collections of external databases, that can be materialized or virtual, and mappings within the collections and with the data source at hand. In this way, the context becomes "the complement" of the data source wrt a data integration system. The proposed model allows for natural extensions, like considering data quality predicates, and even more expressive ontologies for data quality assessment.
- Date Created:
- 2011-01-01
-
- Resource Type:
- Conference Proceeding
- Creator:
- Smid, Michiel
- Date Created:
- 2009-10-16
-
- Resource Type:
- Conference Proceeding
- Creator:
- Ponce, Oscar Morales, Pacheco, Eduardo, Kranakis, Evangelos, Ga̧sieniec, Leszek, Czyzowicz, Jurek, and Kosowski, Adrian
- Abstract:
- A collection of n anonymous mobile robots is deployed on a unit-perimeter ring or a unit-length line segment. Every robot starts moving at constant speed, and bounces each time it meets any other robot or segment endpoint, changing its walk direction. We study the problem of position discovery, in which the task of each robot is to detect the presence and the initial positions of all other robots. The robots cannot communicate or perceive information about the environment in any way other than by bouncing. Each robot has a clock allowing it to observe the times of its bounces. The robots have no control on their walks, which are determined by their initial positions and the starting directions. Each robot executes the same position detection algorithm, which receives input data in real-time about the times of the bounces, and terminates when the robot is assured about the existence and the positions of all the robots. Some initial configuration of robots are shown to be infeasible - no position detection algorithm exists for them. We give complete characterizations of all infeasible initial configurations for both the ring and the segment, and we design optimal position detection algorithms for all feasible configurations. For the case of the ring, we show that all robot configurations in which not all the robots have the same initial direction are feasible. We give a position detection algorithm working for all feasible configurations. The cost of our algorithm depends on the number of robots starting their movement in each direction. If the less frequently used initial direction is given to k ≤ n/2 robots, the time until completion of the algorithm by the last robot is 1/2 ⌈n/k⌉. We prove that this time is optimal. By contrast to the case of the ring, for the unit segment we show that the family of infeasible configurations is exactly the set of so-called symmetric configurations. We give a position detection algorithm which works for all feasible configurations on the segment in time 2, and this algorithm is also proven to be optimal.
- Date Created:
- 2012-11-09
-
- Resource Type:
- Conference Proceeding
- Creator:
- Gardezi, Jaffer and Bertossi, Leopoldo
- Abstract:
- Matching Dependencies (MDs) are a recent proposal for declarative entity resolution. They are rules that specify, given the similarities satisfied by values in a database, what values should be considered duplicates, and have to be matched. On the basis of a chase-like procedure for MD enforcement, we can obtain clean (duplicate-free) instances; actually possibly several of them. The clean answers to queries (which we call the resolved answers) are invariant under the resulting class of instances. In this paper, we investigate a query rewriting approach to obtaining the resolved answers (for certain classes of queries and MDs). The rewritten queries are specified in stratified Datalog not,s with aggregation. In addition to the rewriting algorithm, we discuss the semantics of the rewritten queries, and how they could be implemented by means of a DBMS.
- Date Created:
- 2012-10-10
-
- Resource Type:
- Conference Proceeding
- Creator:
- Smid, Michiel, Maheshwari, Anil, Das, Sandip, and Banik, Aritra
- Abstract:
- Let P be a simple polygon with m vertices and let be a set of n points in P. We consider the points of to be users. We consider a game with two players and. In this game, places a point facility inside P, after which places another point facility inside P. We say that a user is served by its nearest facility, where distances are measured by the geodesic distance in P. The objective of each player is to maximize the number of users they serve. We show that for any given placement of a facility by, an optimal placement for can be computed in O(m + n(logn + logm)) time. We also provide a polynomial-time algorithm for computing an optimal placement for.
- Date Created:
- 2013-10-08
-
- Resource Type:
- Conference Proceeding
- Creator:
- Zeh, Norbert, Hutchinson, David, and Maheshwari, Anil
- Abstract:
- We present results related to satisfying shortest path queries on a planar graph stored in external memory. In particular, we show how to store rooted trees in external memory so that bottom-up paths can be traversed I/O-efficiently, and we present I/O-efficient algorithms for triangulating planar graphs and computing small separators of such graphs. Using these techniques, we can construct a data structure that allows for answering shortest path queries on a planar graph I/O-efficiently.
- Date Created:
- 1999-01-01