1,721,077 research outputs found
Contiguous search problem in Sierpinski graphs
No full textIn this paper we consider the problem of capturing an intruder in a particular fractal graph, the Sierpiński graph SG n . The problem consists of having a team of mobile software agents that collaborate in order to capture the intruder. The intruder is a mobile entity that escapes from the team of agents, moving arbitrarily fast inside the network, i.e., traversing any number of contiguous nodes as long as no other agent resides on them. The agents move asynchronously and they know the network topology they are in is a Sierpiński graph SG n .
We first derive lower bounds on the minimum number of agents, number of moves and time steps required to capture the intruder. We then consider some variations of the model based on the capabilities of the agents: visibility, where the agents can “see” the state of their neighbors and thus can move autonomously; locality, where the agents can only access local information and thus their moves have to be coordinated by a leader. For each model, we design a capturing strategy and we make some observations. One of our goals is to continue a previous study on what is the impact of visibility on complexity: in this topology we are able to reach an optimal bound on the number of agents required by both cleaning strategies. However, the strategy in the visibility model is fully distributed, whereas the other strategy requires a leader. Moreover, the second strategy requires a higher number of moves and time steps
Intruder Capture in Sierpinski Graphs.
No full textIn this paper we consider the problem of capturing an intruder in a networked environment. The intruder is defined as a mobile entity that moves arbitrarily fast inside the network and escapes from a team of software agents. The agents have to collaborate and coordinate their moves in order to isolate the intruder. They move asynchronously and they know the network topology they are in is a particular fractal graph, the Sierpiński graph SG n .\ud
We first derive lower bounds on the minimum number of agents, number of moves and time steps required to capture the intruder. We then consider two models: one in which agents have a capability, of “seeing” the state of their neighbors; the second one in which the actions of the agents are leaded by a coordinator. One of our goals is to continue a previous study on what is the impact of visibility on complexity: we have found that in this topology the visibility assumption allows us to reach an optimal bound on the number of agents required for the cleaning strategy. On the other hand, the second strategy relies only on local computations but requires an extra agent and a higher (by a constant) complexity in terms of time and number of moves
Web accessibility recommendations for the design of tourism websites for people with autism spectrum disorders
No full textThe universal Web design represents an ambitious and open challenge for the current research on the Web. Key aspects are Web accessibility and Web usability by people with the widest possible range of abilities, operating within the widest possible range of situations. Universal design is adaptive for the users, and provides personalised answers to different users. A recent study shows an estimation of the global burden of people with Autism Spectrum Disorders. In the last 24 years, the incidence of autism has a stable prevalence of 7.6 per 1000 or one in 132 persons. They represent a significant number of people. People with Autism Spectrum Disorders are usually solitary and visual thinkers and they could take advantage by the use of the Web. This paper discusses of tourism, website and people with Autism Spectrum Disorders. The aim is to define a set of recommendations for the design of tourist websites for people with Autism Spectrum Disorders, and to present a case study articulated in two tourist, autistic-friendly, websites. The first website considers the area of Rieti, central Italy; it has been validated through expert reviews, and several trials with many autistic, verbal users of a specialised centre for neurological and physical disabilities. The second website contains as a tourist destination the area around Mestre, close to Venice, Italy. In this case, the website has been validated on a single, non-verbal autistic user
Learning distributed algorithms by programming robots
No full textThe learning process of theoretical concepts such as the model of a distributed environment and different distributed algorithms together with their execution and correctness requires time and is often considered by students a hard and non-challenging issue. In this paper we suggest adopting a more practical approach based on real implementations of distributed algorithms with the help of robots. A learning-by-doing approach can, in our opinion, help students acquiring a deeper knowledge of the model and of the algorithms, and can also stimulate them, and let them improve their teamwork skills. In this paper, we present a specific case study of a practical project, run for two consecutive years at the University Cà Foscari of Venice, inside an International Master of Computer Science course of Advanced Algorithms. The students for their final exam had to work in groups and their task was to design and implement a distributed algorithm to solve an assigned problem, using a Lego Mindstorm EV3 robot and a Makeblock mBot robot. In this paper, we discuss the positive effects of such a non-traditional teamwork approach by analyzing the teacher’s perception, the feasible impact on the students’ grades, and the students’ involvement and positive feeling, highlighted by the results of some questionnaires proposed at the beginning and the end of the projects. We finally discuss the limits of such an approach and possible improvements.The learning process of theoretical concepts such as the model of a distributed environment and different distributed algorithms together with their execution and correctness requires time and is often considered by students a hard and non-challenging issue. In this paper we suggest adopting a more practical approach based on real implementations of distributed algorithms with the help of robots. A learning-by-doing approach can, in our opinion, help students acquiring a deeper knowledge of the model and of the algorithms, and can also stimulate them, and let them improve their teamwork skills. In this paper, we present a specific case study of a practical project, run for two consecutive years at the University Ca' Foscari of Venice, inside an International Master of Computer Science course of Advanced Algorithms. The students for their final exam had to work in groups and their task was to design and implement a distributed algorithm to solve an assigned problem, using a Lego Mindstorm EV3 robot and a Makeblock mBot robot. In this paper, we discuss the positive effects of such a non-traditional teamwork approach by analyzing the teacher's perception, the feasible impact on the students' grades, and the students' involvement and positive feeling, highlighted by the results of some questionnaires proposed at the beginning and the end of the projects. We finally discuss the limits of such an approach and possible improvements
Minimum Feedback Vertex Set in Pyramid and Mesh of Trees Networks
No full textIn this paper we consider the minimum feedback vertex set problem in graphs, i.e., the problem of finding a minimal subset of vertices that have to be removed from a graph, to induce an acyclic subgraph. The problem in NP-hard for general topologies, but many different polynomial time algorithms have been provided for particular networks. In this paper we present close lower and upper bounds to the problem in two different topologies, namely pyramid networks and rectangular mesh of trees networks
On the convergence of a parallel algorithm for finding polynomial zeros
No full textThe problem of finding the zeros of a polynomial p(z) of degree n is considered. Some results related to a parallel algorithm given by Bini and Gemignani are improved. The algorithm is a reformulation of Householder's sequential algorithm ([7]) that is based on the computation of the polynomial remainder sequence generated by the Euclidean scheme. The approximation to the sought after zeros (or factors) can be carried out if, at the generic j-th step of the Euclidean scheme, the modulus of a certain quantity βj, that depends on the remainder of the division, is 'sufficiently small.' This condition is verified through the detection of a strong break-point for the zeros, that is, a value of j such that if zi, i = 1,..., n are the zeros of p(z), then |a(zj+1)÷a(zj)| < 1 - 1÷nk for a given k and for a given function a(z). In this paper we present sufficient conditions and necessary conditions for the existence of a strong break point
Accessible and Usable Websites and Mobile Applications for People with Autism Spectrum Disorders: a Comparative Study
Full text linkAccessibility, usability and inclusion represent desirable challenges of current research in the field of universal design: in some cases, these features require adaptive behaviours and specialised customisations, while, in general, it is possible to identify common and shareable guidelines. We focus our attention on children with autism spectrum disorders. Many studies show the positive impact of using computer technologies for supporting the lives of these users. Despite that, just a restricted part of the current websites and apps is accessible and usable for people with ASD. In this paper, we present general and shared guidelines and best practices for accessibility and usability for all; and we propose specialised guidelines for designers and developers of websites and mobile applications for users with ASD. We then present a review of many of the existing websites and applications, in order to check which comply with all, or parts of these guidelines
- …
