L'objectiu del grup és la producció de contribucions rellevants en les àrees d'expertesa dels components del grup i la seva disseminació en revistes i conferències internacionals de prestigi reconegut. És voluntat del grup que les contribucions tinguin un impacte significatiu a llarg termini. La transferència de tecnologia és considerada com una conseqüència de l'excel·lència en la recerca i s'ha de portar a terme com un mitjà per incrementar l'impacte dels resultats, obtenir recursos per al grup i explorar nous temes per a la recerca en el futur.
One of the main computational challenges facing metagenomic analysis is the taxonomic identification of short DNA fragments. The combination of sequence alignment methods with taxonomic assignment based on consensus can provide an accurate estimate of the microbial diversity in a sample. In this note, we show how recent improvements to these consensus methods, as implemented in the latest release of the TANGO tool, can provide an improved estimate of diversity in simulated datasets.
Galceran, M.; Gotmanov, A.; Cortadella, J.; Kishinevsky, M. ACM journal on emerging technologies in computing systems Vol. 7, num. 4, p. 1-24 DOI: 10.1145/2043643.2043648 Data de publicació: 2011-12 Article en revista
Barolli, L.; Spaho, E.; Oda, T.; Barolli, A.; Xhafa, F.; Takizawa, M. International Conference on Advances in Mobile Computing and Multimedia p. 110-115 DOI: 10.1145/2095697.2095718 Data de presentació: 2011-12 Presentació treball a congrés
Spaho, E.; Barolli, L.; Xhafa, F.; Iwashige, J.; Koyama, A. International Conference on Intelligent Networking and Collaborative Systems p. 373-377 DOI: 10.1109/INCoS.2011.21 Data de presentació: 2011-12 Presentació treball a congrés
Toral, S.; Bessis, N.; Martinez, M.; Franc, F.; Barrero, F.; Xhafa, F. International Conference on Intelligent Networking and Collaborative Systems p. 21-26 DOI: 10.1109/INCoS.2011.49 Data de presentació: 2011-12 Presentació treball a congrés
Umezaki, K.; Spaho, E.; Ogata, Y.; Barolli, L.; Xhafa, F.; Iwashige, J. International Conference on Intelligent Networking and Collaborative Systems p. 484-489 DOI: 10.1109/INCoS.2011.22 Data de presentació: 2011-12 Presentació treball a congrés
Xhafa, F.; Asimakopoulou, E.; Bessis, N.; Barolli, L.; Takizawa, M. International Conference on Intelligent Networking and Collaborative Systems p. 741-745 DOI: 10.1109/INCoS.2011.161 Data de presentació: 2011-12 Presentació treball a congrés
Xhafa, F.; Duran, B.; Kolodziej, J.; Barolli, L.; Takizawa, M. International Conference on Intelligent Networking and Collaborative Systems p. 164-171 DOI: 10.1109/INCoS.2011.128 Data de presentació: 2011-12 Presentació treball a congrés
Xhafa, F.; Sánchez, C.; Barolli, A.; Takizawa, M. International Conference on Intelligent Networking and Collaborative Systems p. 53-59 DOI: 10.1109/INCoS.2011.44 Data de presentació: 2011-12 Presentació treball a congrés
Yang, T.; Barolli, L.; Iwashige, J.; Xhafa, F.; Durresi, A. International Conference on Intelligent Networking and Collaborative Systems p. 196-202 DOI: 10.1109/INCoS.2011.68 Data de presentació: 2011-12 Presentació treball a congrés
Simultaneous switching noise has become an important issue due to its signal integrity and timing implications.
Therefore a lot of time and resources are spent during the PDN design to minimize the supply voltage variation. This paper presents the self-adaptive clock as an alternative to tolerate the critical path delay variation due to supply noise thanks to its self-adaptable nature. A self-adaptive clock generation circuit is
proposed in this paper and its benefits, in terms of clock period reduction, are assessed under a realistic supply noise obtained through simulation for different switching activities.
Xhafa, F.; Barolli, A.; Sánchez, C.; Barolli, L. Simulation modelling practice and theory Vol. 19, num. 10, p. 2276-2284 DOI: 10.1016/j.simpat.2010.08.014 Data de publicació: 2011-11 Article en revista
Verborgh, R.; Steiner, T.; Van Deursen, D.; Van de Walle, R.; Gabarro, J. Next Generation Web Services Practices p. 373-379 DOI: 10.1109/NWeSP.2011.6088208 Data de presentació: 2011-10-20 Presentació treball a congrés
Hyperlinks and forms let humans navigate with ease through websites they have never seen before. In contrast, automated agents can only perform preprogrammed actions on Web services, reducing their generality and restricting their usefulness to a specialized domain. Many of the employed services call themselves RESTful, although they neglect the hypermedia constraint as defined by Roy T. Fielding, stating that the application state should be driven by hypertext. This lack of link usage on the Web of services severely limits agents in what they can do, while connectedness forms a primary feature of the human Web. An urgent need for more intelligent agents becomes apparent, and in this paper, we demonstrate how the conjunction of functional service descriptions and hypermedia links leads to advanced, interactive agent behavior. We propose a new mode for our previously introduced semantic service description format RESTdesc, providing the mechanisms for agents to consume Web services based on links, similar to human browsing strategies. We illustrate the potential of these descriptions by a use case that shows the enhanced capabilities they offer to automated agents, and explain how this is vital for the future Web.
The social networking website Facebook offers to its users a feature called “status updates” (or just “status”), which allows users to create microposts directed to all their contacts, or a subset thereof. Readers can respond to microposts, or in addition to that also click a “Like” button to show their appreciation for a certain micropost. Adding semantic meaning in the sense of unambiguous intended ideas to such microposts can, for example, be achieved via Natural Language Processing (NLP). Therefore, we have implemented a RESTful mash-up NLP API, which is based on a combination of several third party NLP APIs in order to retrieve more accurate results in the sense of emergence. In consequence, our API uses third party APIs opaquely in the background in order to deliver its output. In this paper, we describe how one can keep track of provenance, and credit back the contributions of each single API to the combined result of all APIs. In addition to that, we show how the existence of provenance metadata can help understand the way a combined result is formed, and optimize the result combination process. Therefore, we use the HTTP Vocabulary in RDF and the Provenance Vocabulary. The main contribution of our work is a description of how provenance metadata can be automatically added to the output of mash-up APIs like the one presented here.
In 2002, J. Díaz, M. Serna and the author published “A Survey of Graph
Layout Problems”, which then was a complete view of the current state of
the art of layout problems from an algorithmic point of view. The current
review expands the contents of the original survey with updated results from these latest ten years and contributes an extensive bibliography.
Simple games cover voting systems in which a single alter-
native, such as a bill or an amendment, is pitted against the status quo. A simple game or a yes-no voting system is a set of rules that specifies exactly which collections of “yea” votes yield passage of the issue at hand. Each of these collections of “yea” voters forms a winning coalition. We are interested in performing a complexity analysis on problems defined on such families of games. This analysis as usual depends on the game representation used as input. We consider four natural explicit representations: winning, losing, minimal winning, and maximal losing. We first analyze the complexity of testing whether a game is simple and testing whether a game is weighted. We show that, for the four types of representations, both problems can be solved in polynomial time. Finally, we provide results on the complexity of testing whether a simple game or a weighted game is of a special type. We analyze strongness, properness, weightedness, homogeneousness, decisiveness and majorityness, which are desirable properties to be fulfilled for a simple game.
Finally, we consider the possibility of representing a game in a more
succinct and natural way and show that the corresponding recognition
problem is hard.
The original publication is available at www.rairo-ro.org
In this work we describe our experience teaching an innovative Android programming workshop organized by the Universitat Politècnica de Catalunya (UPC) within the AndroidEDU Google EMEA Program. The growing interest in Android has allowed us to apply proactive learning techniques with very good results. As teachers, this was a challenging experience, that has forced us to rethink our role, to create educational material
accordant with the new communication media (forums, YouTube, etc.), and to supply the lack of expertise with an interesting collaboration between teachers and students. After three semesters teaching this workshop, we are convinced that this is an experience to share since the results have far exceeded our expectations.
We consider a general multi-agent framework in which a set of n agents are roaming a network where m valuable and sharable goods (resources, services, information ....) are hidden in m different vertices of the network. We analyze several strategic situations that arise in this setting by means of game theory. To do so, we introduce a class of strategic games that we call strategic search games. In those games agents have to select a simple path in the network that starts from a predetermined set of initial vertices. Depending on how the value of the retrieved goods is splitted among the agents, we consider two game types: finders-share in which the agents that find a good split among them the corresponding benefit and firsts-share in which only the agents that first find a good share the corresponding benefit. We show that finders-share games always have pure Nash equilibria (pne ). For obtaining this result, we introduce the notion of Nash-preserving reduction between strategic games. We show that finders-share games are Nash-reducible to single-source network congestion games. This is done through a series of Nash-preserving reductions. For firsts-share games we show the existence of games with and without pne. Furthermore, we identify some graph families in which the firsts-share game has always a pne that is computable in polynomial time.
Alvarez, C.; Diaz, J.; Dieter, M.; Serna, M. International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities p. 1-10 Data de presentació: 2011-09-08 Presentació treball a congrés
Barolli, A.; Oda, T.; Xhafa, F.; Barolli, L.; Takizawa, M.; Uchida, K. Journal of interconnection networks Vol. 12, num. 3, p. 205-219 DOI: 10.1142/S0219265911002952 Data de publicació: 2011-09 Article en revista
Research in metaheuristics for combinatorial optimization problems has lately experienced a noteworthy shift towards the hybridization of metaheuristics with other techniques for optimization. At the same time, the focus of research has changed from being rather algorithm-oriented to being more problem-oriented.
Nowadays the focus is on solving the problem at hand in the best way possible, rather than
promoting a certain metaheuristic. This has led to an enormously fruitful cross-fertilization of different areas of optimization. This cross-fertilization is documented by a multitude of powerful hybrid algorithms that were obtained by combining components from several different optimization techniques. Hereby, hybridization is not restricted to the combination of different metaheuristics but includes, for example, the combination of exact algorithms and metaheuristics. In this work we provide a survey of some of the most important lines of hybridization. The literature review is accompanied by the presentation of illustrative examples.
Ants are generally believed to follow an intensive work routine. Numerous tales and fables refer to ants as conscientious workers. Nevertheless, biologists have discovered that ants also rest for extended periods of time. This does not only hold for individual ants. Interestingly, ant colonies exhibit synchronized activity phases that result from self-organization. In this work, self-synchronization in ant colonies is taken as the inspiring source for a new mechanism of self-synchronized duty-cycling in mobile sensor networks. Hereby, we assume that sensor nodes are equipped with energy harvesting capabilities such as, for example, solar cells. We show that the proposed self-synchronization mechanism can be made adaptive depending on variable energy resources. The main objective of
this paper is to study and explore the swarm intelligence foundations of self-synchronized dutycycling. With this purpose in mind, physical constraints such as packet collisions and packet loss are
generally not considered.
Term unification plays an important role in many areas of computer science, especially in those related to logic. The universal mechanism of grammar-based compression for terms, in particular the so-called singleton
tree grammars (STGAs), have recently drawn considerable attention. Using STGs, terms of exponential size and height can be represented in linear space. Furthermore, the term representation by directed acyclic
graphs (dags) can be efficiently simulated. The present article is the result of an investigation on term unification and matching when the terms given as input are represented using different compression mechanisms for terms such as dags and singleton tree grammars. We describe a polynomial time algorithm for context matching with dags, when the number of different context variables is fixed for the problem. For the same problem, NP-completeness is obtained when the terms are represented using the more general
formalism of singleton tree grammars. For first-order unification and matching polynomial time algorithms are presented, each of them improving previous results for those problems.
We prove that the maximum degree Δn of a random series-parallel graph with n vertices
satisfies Δn/ log n → c in probability, and EΔn ∼ c log n for a computable constant c > 0.
The same kind of result holds for 2-connected series-parallel graphs, for outerplanar graphs,
and for 2-connected outerplanar graphs.
This algorithm does not use linear programming, being its computational
complexity analysis easier than the ones which use it. Moreover, the enumeration is made (pre-)ordering the complete games in a lattice structure, which may be interesting for the verification of other properties; for instance, the level of a game inside the lattice, its distance to the greatest and least element, or the distance between two different games.
Finally, we also compare this algorithm with the used in [FM08], from the point of view of CPU time, and the maximum number of players for which is able to obtain in the practice all complete games.