Quasi-Upward Planarity

Abstract. An upward planar drawing of a directed graph (digraph) is a planar drawing such that all the edges are represented by curves monotonically increasing in the vertical direction. In this paper we introduce and study the concept of quasi-upward planarity. Quasi-upward planarity allows us to extend the upward planarity theory to a large class of digraphs including digraphs that also have directed cycles. First, we characterize the digraphs that have a quasi-upward planar drawing. Second, we give a polynomial time algorithm for computing ``optimal' quasi-upward planar drawings within a given planar embedding. Further, we apply branch and bound techniques to the problem of computing optimal quasi-upward planar drawings, considering all possible planar embeddings. The paper also contains experimental results about the proposed techniques.     

Logic based methods for SNPs tagging and reconstruction

SNPs are positions of the DNA sequences where the differences among individuals are embedded. The knowledge of such SNPs is crucial for disease association studies, but even if the number of such positions is low (about 1% of the entire sequence), the cost to extract the complete information is actually very high. Recent studies have shown that DNA sequences are structured into blocks of positions, that are conserved during evolution, where there is strong correlation among values (alleles) of different loci. To reduce the cost of extracting SNPs information, the block structure of the DNA has suggested to limit the process to a subset of SNPs, the so-called Tag SNPs, that are able to maintain the most of the information contained in the whole sequence. In this paper, we apply a technique for feature selection based on integer programming to the problem of Tag SNP selection. Moreover, to test the quality of our approach, we consider also the problem of SNPs reconstruction, i.e. the problem of deriving unknown SNPs from the value of Tag SNPs and propose two reconstruction methods, one based on a majority vote and the other on a machine learning approach. We test our algorithm on two public data sets of different nature, providing results that are, when comparable, in line with the related literature. One of the interesting aspects of the proposed method is to be found in its capability to deal simultaneously with very large SNPs sets, and, in addition, to provide highly informative reconstruction rules in the form of logic formulas.     

On the design of efficient ATM routing schemes

In this paper we deal with the problem of designing virtual path layouts in ATM networks when the hop-count is given and the load has to be minimized. We first prove a lower bound for networks with arbitrary topology and arbitrary set of connection requests. This result is then applied to derive lower bounds for the following settings: (i) one-to-all (one node has to be connected to all other nodes of the network) in arbitrary networks; (ii) all-to-all (each node has to be connected to all other nodes in the network) in several classes of networks, including planar and k-separable networks and networks of bounded genus. We finally study the all-to-all setting on two-dimensional meshes and we design a virtual path layout for this problem. When the hop-count and the network degree are bounded by constants, our results show that the upper bounds proposed in this paper for the one-to-all problem in arbitrary networks and for the all-to-all problem in two-dimensional mesh networks are asymptotically optimal. Moreover, the general lower bound shows that the algorithm proposed in Gerstel (Ph.D. Thesis, Technion-Haifa, Israel, 1995) for the all-to-all problem in k-separable networks is also asymptotically optimal. The upper bound for mesh networks also shows that the lower bound presented in this paper for the all-to-all problem in planar networks is asymptotically tight.     

Quasi-Upward Planarity

An upward planar drawing of a directed graph (digraph) is a planar drawing such that all the edges are represented by curves monotonically increasing in the vertical direction. In this paper we introduce and study the concept of quasi-upward planarity. Quasi-upward planarity allows us to extend the upward planarity theory to a large class of digraphs including digraphs that also have directed cycles. First, we characterize the digraphs that have a quasi-upward planar drawing. Second, we give a polynomial time algorithm for computing ``optimal'' quasi-upward planar drawings within a given planar embedding. Further, we apply branch and bound techniques to the problem of computing optimal quasi-upward planar drawings, considering all possible planar embeddings. The paper also contains experimental results about the proposed techniques.     

Molecular Approach to Electrochemically Switchable Monolayer MoS2 Transistors

As Moore's law is running to its physical limit, tomorrow's electronic systems can be leveraged to a higher value by integrating “More than Moore” technologies into CMOS digital circuits. The hybrid heterostructure composed of two-dimensional (2D) semiconductors and molecular materials represents a powerful strategy to confer new properties to the former components, realize stimuli-responsive functional devices, and enable diversification in “More than Moore” technologies. Here, an ionic liquid (IL) gated 2D MoS₂ field-effect transistor (FET) with molecular functionalization is fabricated. The suitably designed ferrocene-substituted alkanethiol molecules not only improve the FET performance, but also show reversible electrochemical switching on the surface of MoS₂. Field-effect mobility of monolayer MoS₂ reaches values as high as ≈116 cm² V⁻¹ s⁻¹ with I_on/I_off ratio exceeding 10⁵. Molecules in their neutral or charged state impose distinct doping effect, efficiently tuning the electron density in monolayer MoS₂. It is noteworthy that the joint doping effect from IL and switchable molecules results in the steep subthreshold swing of MoS₂ FET in the backward sweep. These results demonstrate that the device architecture represents an unprecedented and powerful strategy to fabricate switchable 2D FET with a chemically programmed electrochemical signal as a remote control, paving the road toward novel functional devices.     

A method for determining the optimal districting in urban emergency services

In this paper a method is suggested for dealing with one of the main allocation problems often appearing in urban emergency services, that of districting.A mathematical model is developed in terms of constrained optimization with binary variables.An algorithm, derived from Balas' filter-method, which seems to be quite efficient for this class of problems, has been utilized.The objective function, considered here, is the overall travel time in the region under consideration.The optimal travel time, in the case of the Rome fire service, turns out to be meaningfully lower than that derived from the actual situation. At the end is indicated a way of applying the method to the assignment of response areas to the different stations as a function of the current state of the system.     

Use of glucagon in the treatment of severe contractile insufficiency of the myocardium

Glucagon hydrochloride has been used to treat severe contractile insufficiency of the myocardium. The drug was administered to cardiopathic patients who had been admitted to the intensive care unit. Results in the various groups examined were satisfactory, particularly in cases of patients with valve diseases and with chronic pulmonary heart and cardiac insufficiency recalcitrant to digitalis therapy. No important side-effects were noted.     

Engineering Chemically Active Defects in Monolayer MoS2 Transistors via Ion‐Beam Irradiation and Their Healing via Vapor Deposition of Alkanethiols

Irradiation of 2D sheets of transition metal dichalcogenides with ion beams has emerged as an effective approach to engineer chemically active defects in 2D materials. In this context, argon‐ion bombardment has been utilized to introduce sulfur vacancies in monolayer molybdenum disulfide (MoS₂). However, a detailed understanding of the effects of generated defects on the functional properties of 2D MoS₂ is still lacking. In this work, the correlation between critical electronic device parameters and the density of sulfur vacancies is systematically investigated through the fabrication and characterization of back‐gated monolayer MoS₂ field‐effect transistors (FETs) exposed to a variable fluence of low‐energy argon ions. The electrical properties of pristine and ion‐irradiated FETs can be largely improved/recovered by exposing the devices to vapors of short linear thiolated molecules. Such a solvent‐free chemical treatment—carried out strictly under inert atmosphere—rules out secondary healing effects induced by oxygen or oxygen‐containing molecules. The results provide a guideline to design monolayer MoS₂ optoelectronic devices with a controlled density of sulfur vacancies, which can be further exploited to introduce ad hoc molecular functionalities by means of thiol chemistry approaches.     

Upward drawings of triconnected digraphs

A polynomial-time algorithm for testing if a triconnected directed graph has an upward drkwing is presented. An upward drkwing is a planar drkwing such that all the edges flow in a common direction (e.g., from bottom to top). The problem arises in the fields of automatic graph drkwing and ordered sets, and has been open for several years. The proposed algorithm is based on a new combinatorial characterization that maps the problem into a max-flow problem on a sparse network; the time complexity isO(n+r ²⁾ , wheren is the number of vertices andr is the number of sources and sinks of the directed graph. If the directed graph has an upward drkwing, the algorithm allows us to construct one easily.This work was partially supported by the Progetto Finalizzato Sistemi Informatici e Calcolo Parallelo of the Italian National Research Council (CNR) Sottoprogetto 6, Infokit and by the ESPRIT II Basic Research Actions Program of the EC (project ALgorithms and COMplexity). An extended abstract of this paper has been presented in P. Bertolazzi and G. Di Battista, On Upward Drkwing Testing of Triconnected Digraphs,Proc. 7th ACM Symposium on Computational Geometry, pp. 272–280, 1991.     

A VLSI structure for the deadlock avoidance problem

In this paper we present two VLSI structures implementing the banker's algorithm for the deadlock avoidance problem, and we derive the area x (time)² lower bound for such an algorithm. The first structure is based on the VLSI mesh of trees. The second structure is a modification of the first one, and it approaches more closely the theoretical lower bound.