1,000 research outputs found
Complexity of Scorpion Solitaire and applications to Klondike
No full textScorpion is a puzzle game that falls under the category of Solitaires. The problem of determining whether a starting configuration of a Solitaire game (generalised to contain an arbitrary number of cards) can lead to a winning configuration has been studied from the perspective of Computational Com- plexity for some of the most popular Solitaires, namely Free Cell [1], Klondike [2] and Spider [3], all resulting in hardness proofs. Scorpion, though, has a unique twist compared to aforementioned ones: each card can be moved to cover only one other card. This property narrows the set of possible moves and makes a worthwhile issue investigating whether the same problem proved NP-complete for Free Cell, Klondike and Spider falls in P as far as Scorpion is considered. In this paper we prove that the problem of deciding whether an n-card s-suits initial configuration of Scorpion allows for a winning sequence of moves is NP-complete for any s ≥ 1, and it remains so also when the ini- tial configuration contains no face down (locked) cards. We then negatively answer a question posed in [2] by proving that it is NP-complete to decide whether an n-card one red suit-one black suit configuration of the Klondike Solitaire allows for a winning sequence of moves
Il direttore generale con A. Juliano. presiede S. Sciarelli. Ciclo sull'industria del calcio a cura di N. De Ianni e P.Varvaro
No full text
L'oscenità tra delitto e diritto di libertà. La funzione sovversiva e disturbante dell'osceno in Pasolini e Ginsberg
No full textA note on the satisfactory partition problem: Constant size requirement
No full textA satisfactory partition is a partition of the vertex set V of a graph into two subsets such that each vertex has at least as many neighbors in the subset it belongs to as in the other subset. The definition can be generalized requiring that each vertex v has at least s(v) neighbors in the subset it belongs to, for a given function s : V → N. While the complexity of the problem of deciding if a graph admits a generalized satisfactory partition has been completely analized when s(v) is a function of the node degree, the issue had left open in the case s(v) is a constant. We prove that, for any constant k ≥ 2, the problem is NP-complete when s(v) = k for any v ∈ V
The minimum broadcast range assignment problem on linear multi-hop wireless networks
No full textGiven a set N of radio stations located on an Euclidean space, a source station s and an integer h (1 less than or equal to h less than or equal to N - 1), the minimum bounded-hop broadcast range assignment problem consists in finding a range assignment for N of minimum total power consumption that allows broadcast operations from s to every station in N in at most h hops. The problem is known to be NP-hard on d-dimensional spaces for any d greater than or equal to 2 (18th Annual Symp. on Theoretical Aspects of Computer Science (STACS'01), Lecture Notes in Computer Science, Vol. 1770, 2000, pp. 651-660.) and some efficient approximation algorithms have been given in Clementi et al. and Wann et al. (18th Annual Symp. on Theoretical Aspects of Computer Science (STACS'01), Lecture Notes in Computer Science, Vol. 1770, 2000, pp. 651-660, IEEE INFOCOM'01, 2001). In this paper, we address the case in which the stations are arbitrarily located along a line (i.e., the linear case). We provide the first polynomial-time algorithm that returns an optimal solution for any instance of the linear case. The algorithm works in O(hN(2)) time. (C) 2002 Published by Elsevier Science B.V
Microemulsion containing triamcinolone acetonide for buccal administration
No full textThe aim of the present work was to investigate the potential of microemulsions for the buccal administration of triamcinolone acetonide. Microemulsions were developed by the construction of pseudoternary phase diagrams, using the aqueous titration method. Among all microemulsions prepared and tested for stability, three were selected and submitted to characterization and in vitro permeation/retention experiments, using pig esophageal epithelium, an accepted model of the buccal mucosa. Furthermore, one microemulsion was added of excipients (stearylamine, CTAB and chitosan) able to alter the charge of droplets. The results obtained show that the permeation of triamcinolone acetonide across pig esophageal epithelium was not influenced by the droplet size nor by the composition, but only by the presence of chitosan, polysaccharide able to increase the transport across mono and stratified epithelia. The determination of the permeation parameters allowed us to show that chitosan acts on the diffusion parameter across the tissue and not on the partitioning parameter; for the same reason the tissue retention of triamcinolone acetonide was not modified. Triamcinolone flux (2.6 Î1⁄4g cmâ2hâ1) was too low to make systemic administration feasible (dose required 2.5 to 60 mg/day). The amount of triamcinolone acetonide recovered in the mucosa after only 10 min. of microemulsion application was much higher than after overnight application of the commercial paste Omicilon® A. This suggests that triamcinolone acetonide microemulsions can be an interesting alternative to the commercial formulation to treat diseases of the buccal mucosa. Owing to the fast uptake by the tissue, the formulation can be used as a mouthwash
MOMOSE: A Mobility Model Simulation Environment for Mobile Wireless Ad-hoc Networks
No full textThis paper describes MOMOSE, a highly flexible and easily extensible environment for the simulation of mobility models. MOMOSE not only allows a programmer to easily integrate a new mobility model into the set of models already included in its distribution, but it also allows the user to let the nodes of the MANET move in different ways by associating any mobility model to any subset of the nodes themselves. Moreover, MOMOSE can be easily adapted in order to record, during the simulation time, all the data necessary for the evaluation of the performance of any communication protocol or of any MANET-based application
A Domain Meta-wrapper Using Seeds for Intelligent Author List Extraction in the Domain of Scholarly Articles
No full textIn this paper we investigate about automated extraction of author lists in the domain of scientific digital libraries. It is given a list of known “seed” authors and we aim to extract complete lists of co-authors from Web pages in arbitrary format. We adopt a methodology embedding domain knowledge in a unique “meta-wrapper”, not requiring training, with negligible maintenance costs and based on the combination of several extraction techniques. Such methods are applied at the structural level, at the character level and at the annotation level. We describe the methodology, illustrate our tool, compare with known approaches and measure the accuracy of our techniques with proper experiments
- …
