Minimize the Maximum Duty in Multi-interface Networks

We consider devices equipped with multiple wired or wireless interfaces. By switching of various interfaces, each device might establish several connections. A connection is established when the devices at its endpoints share at least one active interface. Each interface is assumed to require an activation cost. In this paper, we consider two basic networking problems in the field of multi-interface networks. The first one, known as the Coverage problem, requires to establish the connections defined by a network. The second one, known as Connectivity problem, requires to guarantee a connecting path between any pair of nodes of a network. Both are subject to the constraint of keeping as low as possible the maximum cost set of active interfaces at each single node. We study the problems of minimizing the maximum cost set of active interfaces among the nodes of the network in order to cover all the edges in the first case, or to ensure connectivity in the second case. We prove that the Coverage problem is NP-hard for any fixed Δ≥5 and k≥16, with Δ being the maximum degree, and k being the number of different interfaces among the network. We also show that, unless P=NP, the problem cannot be approximated within a factor of ηln?Δ, for a certain constant η. We then provide a general approximation algorithm which guarantees a factor of O((1+b)ln?Δ), with b being a parameter depending on the topology of the input graph. Interestingly, b can be bounded by a constant for many graph classes. Other approximation and exact algorithms for special cases are presented. Concerning the Connectivity problem, we prove that it is NP-hard for any fixed Δ≥3 and k≥10. Also for this problem, the inapproximability result holds, that is, unless P=NP, the problem cannot be approximated within a factor of ηln?Δ, for a certain constant η. We then provide approximation and exact algorithms for the general problem and for special cases, respectively.     

Stratigraphic analysis of intercalated graphite electrodes in aqueous inorganic acid solutions

A detailed stratigraphic investigation of the intercalation mechanism when graphite electrodes are immersed inside diluted perchloric(HClO₄)and sulfuric(H₂SO₄)electrolytes is obtained by comparing results when graphite crystals are simply immersed in the same acid solutions.By combining time-of-flight secondary ion mass spectrometry(ToF-SIMS)and in-situ atomic force microscopy(AFM),we provide a picture of the chemical species involved in the intercalation reaction.The depth intensity profile of the ion signals along the electrode crystal clearly shows a more complex mechanism for the intercalation process,where the local morphology of the basal plane plays a crucial role.Solvated anions are mostly located within the first tens of nanometers of graphite,but electrolytes also diffuse inside the buried layers for hundreds of nanometers,the latter process is also aided by the presence of mesoscopic crystal defects.Residual material from the electrolyte solution was found localized in well-defined circular spots,which represent preferential interaction areas.Interestingly,blister-like micro-structures similar to those observed on the highly oriented pyrolytic graphite(HOPG)surface were found in the buried layers,confirming the equivalence of the chemical condition on the graphite surface and in the underneath layers.     

The surface energy of palygorskite

An average value for the surface energy (γ¯_S) of palygorskite was determined from experimental data of spreading pressure, the surface tension of water and its contact angle using a formula based on the combination of the Young equation with a general equation of pair interaction. The value found is 226.6 mJ m^− 2. Some factors that affect the determination of surface energy via solid-liquid interaction are exposed. The backgrounds of previous formulas for the calculation of the surface energy of palygorskite are also critically examined.     

Engineering a New Algorithm for Distributed Shortest Paths on Dynamic Networks

We study the problem of dynamically updating all-pairs shortest paths in a distributed network while edge update operations occur to the network. We consider the practical case of a dynamic network in which an edge update can occur while one or more other edge updates are under processing. A node of the network might be affected by a subset of these changes, thus being involved in the concurrent executions related to such changes. In this paper, we provide a new algorithm for this problem, and experimentally compare its performance with respect to those of the most popular solutions in the literature: the classical distributed Bellman-Ford method, which is still used in real network and implemented in the RIP protocol, and DUAL, the Diffuse Update ALgorithm, which is part of CISCO’s widely used EIGRP protocol. As input to the algorithms, we used both real-world and artificial instances of the problem. The experiments performed show that the space occupancy per node required by the new algorithm is smaller than that required by both Bellman-Ford and DUAL. In terms of messages, the new algorithm outperforms both Bellman-Ford and DUAL on the real-world topologies, while on artificial instances, the new algorithm sends a number of messages that is more than that of DUAL and much smaller than that of Bellman-Ford.     

On the Fixed-Parameter Tractability of the Maximum Connectivity Improvement Problem

Theory of Computing Systems - In the Maximum Connectivity Improvement (MCI) problem, we are given a directed graph G = (V,E) and an integer B and we are asked to find B new edges to be added to G...     

Stable Alignment of Tautomers at Room Temperature in Porphyrin 2D Layers

A major challenge in molecular electronics is to develop logic devices based on a truly intramolecular switching mechanism. Recently, a new type of molecular device has been proposed where the switching characteristic is mediated by the bistability in the position of the two hydrogen atoms which can occupy different, energetically equivalent positions (tautomerization) in the inner cavity of porphyrins and naphthalocyanines. Up to now, such a reaction has only been exploited at low temperatures and induced or detected through atomic scale manipulation. In addition, the unpredictability of the tautomer orientation currently excludes molecular interconnection to functional electronic circuits. Here, full evidence is provided that, following a newly proposed growth strategy, 2D layers of metal‐free tetraphenylporphyrins (H₂TPP) show frozen tautomerization even at room temperature on macroscopic domains, with the H atoms aligned along a direction settled a priori. This behavior is ascribed to the buckling of the molecule, anchored to the substrate, which removes the degeneracy between the two tautomer alignments. On this basis, a new way to exploit uniaxially oriented H₂TPP tautomers in a first elementary logic device is proposed.     

Out-Of-Plane Metal Coordination for a True Solvent-Free Building with Molecular Bricks: Dodging the Surface Ligand Effect for On-Surface Vacuum Self-Assembly

The desirable self-assembly (SA) of repeated 2D stacked layers requires a “holistic analysis” of three interconnected components: the electrode, the interface, and the molecular component; among them, the contact interface bears the largest burden responsibilities. Epitaxial growth (EG) of coherent 2D+n stacked heterojunction by solvent-free deposition holds great promise, although the feasibility has never been demonstrated given multiple drawbacks (e.g., surface-ligand effect, SLE). Here, it is demonstrated how a coherent 2D+n (n = 3) layered heterorganic film is grown on an archetypal Fe metal electrode. The groundbreaking achievement is the result of the in-vacuum integration of: i) chemical decoupling of the basal organic layer (a Zn^II-tetraphenylporphyrine, ZnTPP) from the metal electrode, ii) 2D-ordering of the ZnTPP commensurate to the substrate, iii) rigid, stoichiometric, and orthogonally arranged, the molecule-to-molecule coupling between ZnTPP and a ditopic linear bridging ligand (i.e., DPNDI) guided by SA coordination chemistry, and iv) sharp (chemical) termination of the layered film.     

Partially dynamic efficient algorithms for distributed shortest paths

We study the dynamic version of the distributed all-pairs shortest paths problem. Most of the solutions given in the literature for this problem, either (i) work under the assumption that before dealing with an edge operation, the algorithm for the previous operation has to be terminated, that is, they are not able to update shortest paths concurrently, or (ii) concurrently update shortest paths, but their convergence can be very slow (possibly infinite) due to the looping and counting infinity phenomena. In this paper, we propose partially dynamic algorithms that are able to concurrently update shortest paths. We experimentally analyze the effectiveness and efficiency of our algorithms by comparing them against several implementations of the well-known Bellman–Ford algorithm.     

Gathering on rings under the Look–Compute–Move model

A set of robots arbitrarily placed on different nodes of an anonymous ring have to meet at one common node and there remain. This problem is known in the literature as the gathering. Anonymous and oblivious robots operate in Look–Compute–Move cycles; in one cycle, a robot takes a snapshot of the current configuration (Look), decides whether to stay idle or to move to one of its neighbors (Compute), and in the latter case makes the computed move instantaneously (Move). Cycles are asynchronous among robots. Moreover, each robot is empowered by the so called multiplicity detection capability, that is, it is able to detect during its Look operation whether a node is empty, or occupied by one robot, or occupied by an undefined number of robots greater than one. The described problem has been extensively studied during the last years. However, the known solutions work only for specific initial configurations and leave some open cases. In this paper, we provide an algorithm which solves the general problem but for few marginal and specific cases, and is able to detect all the ungatherable configurations. It is worth noting that our new algorithm makes use of some previous techniques and unifies them with new strategies in order to deal with any initial configuration, even those left open by previous works.