1,721,027 research outputs found
AN ANALYSIS OF TIME USE DATA TO ACCESS THE IMPACT OF IMPROVEMENTS ON THE TRANSPORTATION SYSTEM: THE APPLICATION TO A TRAFFIC CORRIDOR
No full textBejeweled, candy crush and other match-three games are (NP-)hard
No full textThe twenty-first century has seen the rise of a new type of video games targeted at a mass audience of "casual" gamers. Many of these games require the player to swap items in order to form matches of three and are collectively known as tilematching match-three games. Among these, the most influential one is arguably Bejeweled in which the matched items (gems) pop and the above gems fall in their place. Bejeweled has been ported to many different platforms and influenced an incredible number of similar games. Very recently one of them, named Candy Crush Saga enjoyed a huge popularity and quickly went viral on social networks. We generalize this kind of games by only parameterizing the size of the board, while all the other elements (such as the rules or the number of gems) remain unchanged. Then, we prove that answering many natural questions regarding such games is actually NP-Hard. These questions include determining if the player can reach a certain score, play for a certain number of turns, and others. We also provide a playable web-based implementation of our reduction, which is accessible at http://candycrush.isnphard.com
Resilient Level Ancestor, Bottleneck, and Lowest Common Ancestor Queries in Dynamic Trees
Full text linkWe study the problem of designing a resilient data structure maintaining a tree under the Faulty-RAM model [Finocchi and Italiano, STOC'04] in which up to delta memory words can be corrupted by an adversary. Our data structure stores a rooted dynamic tree that can be updated via the addition of new leaves, requires linear size, and supports resilient (weighted) level ancestor queries, lowest common ancestor queries, and bottleneck vertex queries in O(delta) worst-case time per operation
UN MODELLO DISCRETO CONTINUO AD EQUAZIONI SIMULTANEE PER LO STUDIO DELLE RELAZIONI TRA ATTIVITA' E SPOSTAMENTI
No full textTime allocation to discretionary in-home, out-of-home activities and to trips
No full textThe present work analyzes the allocation of time to discretionary in-home and outof-
home activities separately from the trips they generate, so as to capture the effects that the
exogenous variables characterizing the transport system and the individual’s and household socioeconomic
characteristics have on time allocation to discretionary trips. A Nested-Tobit model
has been used, which is a discrete-continuous model with limited dependent variable. The model’s
structure embodies a hierarchical sequence of two equations that describe how the individuals
choose to allocate their discretionary time between in- and out-of-home activities (activity
programme) and between trips and activities (activity scheduling). The empirical results assign
greater descriptive power to mandatory non-work activities for the trade-off between in-home
and out-of-home activities, but the number of trips and the time allocated to mandatory trips were
the two activity variables that most influenced the time to be allocated to discretionary trips
Analysis of the interactions between time use and trip time using a structural equations model
No full textTHE IMPACT OF IMPROVEMENT IN TRANSPORTATION SUPPLY IN PARTICIPATION IN OUT OF HOME ACTIVITIES
No full text
An Improved Algorithm for Computing All the Best Swap Edges of a Tree Spanner
No full textA tree σ -spanner of a positively real-weighted n-vertex and m-edge undirected graph G is a spanning tree T of G which approximately preserves (i.e., up to a multiplicative stretch factor σ ) distances in G. Tree spanners with provably good stretch factors find applications in communication networks, distributed systems, and network design. However, finding an optimal or even a good tree spanner is a very hard computational task. Thus, if one has to face a transient edge failure in T, the overall effort that has to be afforded to rebuild a new tree spanner (i.e., computational costs, set-up of new links, updating of the routing tables, etc.) can be rather prohibitive. To circumvent this drawback, an effective alternative is that of associating with each tree edge a best possible (in terms of resulting stretch) swap edge—a well-established approach in the literature for several other tree topologies. Correspondingly, the problem of computing all the best swap edges of a tree spanner is a challenging algorithmic problem, since solving it efficiently means to exploit the structure of shortest paths not only in G, but also in all the scenarios in which an edge of T has failed. For this problem we provide a very efficient solution, running in O(n2log4n) time, which drastically improves (almost by a quadratic factor in n in dense graphs) on the previous known best result
- …
