Generalized honeycomb torus is Hamiltonian

Generalized honeycomb torus is a candidate for interconnection network architectures, which includes honeycomb torus, honeycomb rectangular torus, and honeycomb parallelogramic torus as special cases. Existence of Hamiltonian cycle is a basic requirement for interconnection networks since it helps map a "token ring" parallel algorithm onto the associated network in an efficient way. Cho and Hsu [Inform. Process. Lett. 86 (4) (2003) 185-190] speculated that every generalized honeycomb torus is Hamiltonian. In this paper, we have proved this conjecture. (C) 2004 Elsevier B.V. All rights reserved.

Preferential Field Coverage Through Detour-Based Mobility Coordination

Controlling the mobility pattern of mobile nodes (e.g., robots) to monitor a given field is a well-studied problem in sensor networks. In this setup, absolute control over the nodes’ mobility is assumed. Apart from the physical ones, no other constraints are imposed on planning mobility of these nodes. In this paper, we address a more general version of the problem. Specifically, we consider a setting in which mobility of each node is externally constrained by a schedule consisting of a list of locations that the node must visit at particular times. Typically, such schedules exhibit some level of slack, which could be leveraged to achieve a specific coverage distribution of a field. Such a distribution defines the relative importance of different field locations. We define the Constrained Mobility Coordination problem for Preferential Coverage (CMC-PC) as follows: given a field with a desired monitoring distribution, and a number of nodes n, each with its own schedule, we need to coordinate the mobility of the nodes in order to achieve the following two goals: 1) satisfy the schedules of all nodes, and 2) attain the required coverage of the given field. We show that the CMC-PC problem is NP-complete (by reduction to the Hamiltonian Cycle problem). Then we propose TFM, a distributed heuristic to achieve field coverage that is as close as possible to the required coverage distribution. We verify the premise of TFM using extensive simulations, as well as taxi logs from a major metropolitan area. We compare TFM to the random mobility strategy—the latter provides a lower bound on performance. Our results show that TFM is very successful in matching the required field coverage distribution, and that it provides, at least, two-fold query success ratio for queries that follow the target coverage distribution of the field.

O problema do caixeiro viajante alugador : um estudo algorítmico

The Car Rental Salesman Problem (CaRS) is a variant of the classical Traveling Salesman Problem which was not described in the literature where a tour of visits can be decomposed into contiguous paths that may be performed in different rental cars. The aim is to determine the Hamiltonian cycle that results in a final minimum cost, considering the cost of the route added to the cost of an expected penalty paid for each exchange of vehicles on the route. This penalty is due to the return of the car dropped to the base. This paper introduces the general problem and illustrates some examples, also featuring some of its associated variants. An overview of the complexity of this combinatorial problem is also outlined, to justify their classification in the NPhard class. A database of instances for the problem is presented, describing the methodology of its constitution. The presented problem is also the subject of a study based on experimental algorithmic implementation of six metaheuristic solutions, representing adaptations of the best of state-of-the-art heuristic programming. New neighborhoods, construction procedures, search operators, evolutionary agents, cooperation by multi-pheromone are created for this problem. Furtermore, computational experiments and comparative performance tests are conducted on a sample of 60 instances of the created database, aiming to offer a algorithm with an efficient solution for this problem. These results will illustrate the best performance reached by the transgenetic algorithm in all instances of the dataset

First-priority relation graph-based malicious users detection in mobile social networks

Mobile social networks (MSNs) consist of many mobile users (individuals) with social characteristics, that provide a variety of data delivery services involving the social relationship among mobile individuals. Because mobile users move around based on their common interests and contact with each other more frequently if they have more social features in common in MSNs. In this paper, we first propose the first-priority relation graph, say FPRG, of MSNs. However, some users in MSNs may be malicious. Malicious users can break the data delivery through terminating the data delivery or tampering with the data. Therefore, malicious users will be detected in the process of looking for the data delivery routing to obtain efficient and reliable data delivery routing along the first-priority relation graph. Secondly, we propose one hamiltonian cycle decomposition of FPRG-based adaptive detection algorithm based on in MSNs under the PMC detection model (the system-level detection model).

Integrating health and sustainability in life cycle assessment

Until now health impact assessment and environmental impact assessment are two different issues, often not addressed together. Both issues have to be dealt with for sustainable building. The aim of this paper is to link healthy and sustainable housing in life cycle assessment. Two strategies are studied: clean air as a functional unity and health as a quality indicator. The strategies are illustrated with an example on the basis of Eco-Quantum, which is a Dutch whole-building assessment tool. It turns out that both strategies do not conflict with the LCA methodology. The LCA methodology has to be refined for this purpose.

Particle and gaseous emissions from commercial aircraft at each stage of the landing and takeoff cycle

A novel technique was used to measure emission factors for commonly used commercial aircraft including a range of Boeing and Airbus airframes under real world conditions. Engine exhaust emission factors for particles in terms of particle number and mass (PM2.5), along with those for CO2, and NOx were measured for over 280 individual aircraft during the various modes of landing/takeoff (LTO) cycle. Results from this study show that particle number, and NOx emission factors are dependant on aircraft engine thrust level. Minimum and maximum emissions factors for particle number, PM2.5, and NOx emissions were found to be in the range of 4.16×1015-5.42×1016 kg-1, 0.03-0.72 g.kg-1, and 3.25-37.94 g.kg-1 respectively for all measured airframes and LTO cycle modes. Number size distributions of emitted particles for the naturally diluted aircraft plumes in each mode of LTO cycle showed that particles were predominantly in the range of 4 to 100 nm in diameter in all cases. In general, size distributions exhibit similar modality during all phases of the LTO cycle. A very distinct nucleation mode was observed in all particle size distributions, except for taxiing and landing of A320 aircraft. Accumulation modes were also observed in all particle size distributions. Analysis of aircraft engine emissions during LTO cycle showed that aircraft thrust level is considerably higher during taxiing than idling suggesting that International Civil Aviation Organization (ICAO) standards need to be modified as the thrust levels for taxi and idle are considered to be the same (7% of total thrust) [1].