Monotony properties of connected visible graph searching

Search games are attractive for their correspondence with classical width parameters. For instance, the invisible search number (a.k.a. node search number) of a graph is equal to its pathwidth plus 1, and the visible search number of a graph is equal to its treewidth plus 1. The connected variants of these games ask for search strategies that are connected, i.e., at every step of the strategy, the searched part of the graph induces a connected subgraph. We focus on monotone search strategies, i.e., strategies for which every node is searched exactly once. The monotone connected visible search number of an n-node graph is at most O(logn) times its visible search number. First, we prove that this logarithmic bound is tight. Precisely, we prove that there is an infinite family of graphs for which the ratio monotone connected visible search number over visible search number is Ω(logn). Second, we prove that, as opposed to the non-connected variant of visible graph searching, “recontamination helps” for connected visible search. Precisely, we prove that, for any k4, there exists a graph with connected visible search number at most k, and monotone connected visible search number >k     

Nondeterministic Graph Searching: From Pathwidth to Treewidth

We introduce nondeterministic graph searching with a controlled amount of nondeterminism and show how this new tool can be used in algorithm design and combinatorial analysis applying to both pathwidth and treewidth. We prove equivalence between this game-theoretic approach and graph decompositions called q -branched tree decompositions, which can be interpreted as a parameterized version of tree decompositions. Path decomposition and (standard) tree decomposition are two extreme cases of q-branched tree decompositions. The equivalence between nondeterministic graph searching and q-branched tree decomposition enables us to design an exact (exponential time) algorithm computing q-branched treewidth for all q≥0, which is thus valid for both treewidth and pathwidth. This algorithm performs as fast as the best known exact algorithm for pathwidth. Conversely, this equivalence also enables us to design a lower bound on the amount of nondeterminism required to search a graph with the minimum number of searchers. Additional support of F.V. Fomin by the Research Council of Norway. Additional supports of P. Fraigniaud from the INRIA Project “Grand Large”, and from the Project PairAPair of the ACI “Masse de Données”. Additional supports of N. Nisse from the Project Fragile of the ACI “Sécurité & Informatique”.     

Graph searching with advice

Fraigniaud et al. [L. Blin, P. Fraigniaud, N. Nisse, S. Vial, Distributing chasing of network intruders, in: 13th Colloquium on Structural Information and Communication Complexity, SIROCCO, in: LNCS, vol. 4056, Springer-Verlag, 2006, pp. 70–84] introduced a new measure of difficulty for a distributed task in a network. The smallest number of bits of advice   of a distributed problem is the smallest number of bits of information that has to be available to nodes in order to accomplish the task efficiently. Our paper deals with the number of bits of advice required to perform efficiently the graph searching problem in a distributed setting. In this variant of the problem, all searchers are initially placed at a particular node of the network. The aim of the team of searchers is to clear a contaminated graph in a monotone connected way, i.e., the cleared part of the graph is permanently connected, and never decreases while the search strategy is executed. Moreover, the clearing of the graph must be performed using the optimal number of searchers, i.e. the minimum number of searchers sufficient to clear the graph in a monotone connected way in a centralized setting. We show that the minimum number of bits of advice permitting the monotone connected and optimal clearing of a network in a distributed setting is Θ(nlogn)$\Theta (nlogn)$, where n$n$ is the number of nodes of the network. More precisely, we first provide a labelling of the vertices of any graph G$G$, using a total of O(nlogn)$O(nlogn)$ bits, and a protocol using this labelling that enables the optimal number of searchers to clear G$G$ in a monotone connected distributed way. Then, we show that this number of bits of advice is optimal: any distributed protocol requires Ω(nlogn)$\Omega (nlogn)$ bits of advice to clear a network in a monotone connected way, using an optimal number of searchers.     

Structural features of a polypeptide carrier promoting secretion of a β-lactamase fusion protein in yeast

Escherichia coli β-lactamase was secreted into the culture medium of Saccharomyces cerevisiae in biologically active form, when fused to the C-terminus of the hsp150δ-carrier. The hsp150δ-carrier is an N-terminal fragment of the yeast hsp150 protein, having a signal peptide and consisting mostly of a 19 amino acid peptide repeated 11 times in tandem. Here we expressed the hsp150δ-carrier fragment alone in S. cerevisiae. Apparently due to a positional effect of the gene insertion, large amounts of the hsp150δ-carrier were synthesized. About half of the de novo synthesized carrier molecules were secreted into the culture medium, the rest remaining mostly in the pre-Golgi compartment. The extensively O-glycosylated carrier fragment was purified from the culture medium under non-denaturing conditions. Circular dichroism spectroscopy showed that it had no regular secondary structure. Nuclear magnetic resonance spectroscopy showed that a non-glycosylated synthetic peptide, the consensus sequence of the repetitive 19 amino acid peptide, also lacked secondary structure. The unstructured carrier polypeptide may facilitate proper folding and secretion of heterologous proteins attached to it.     

Modelling and analysing a distributed dynamic channel allocation algorithm for mobile computing using high-level net methods

A distributed dynamic channel allocation algorithm has been proposed in [11]. In this paper the algorithm is modelled using predicate/transition nets. The same model can be used for any number of cell and channel configurations. The Maria reachability analyser has been used to analyse the protocol for some configurations. These are deadlock-free and are shown to satisfy the requirement that the same channel is never allocated to two neighbouring cells. The suitability of high-level nets for the modelling and analysis of distributed algorithms is discussed. Published online: 24 August 2001     

The cost of monotonicity in distributed graph searching

Blin et al. (Theor Comput Sci 399(1–2):12–37, 2008) proposed a distributed protocol enabling the smallest possible number of searchers to clear any unknown graph in a decentralized manner. However, the strategy that is actually performed lacks of an important property, namely the monotonicity. This paper deals with the smallest number of searchers that are necessary and sufficient to monotonously clear any unknown graph in a decentralized manner. The clearing of the graph is required to be connected, i.e., the clear part of the graph must remain permanently connected, and monotone, i.e., the clear part of the graph only grows. We prove that a distributed protocol clearing any unknown n-node graph in a monotone connected way, in a decentralized setting, can achieve but cannot beat competitive ratio of Q(\fracnlogn){\Theta(\frac{n}{\log n})} , compared with the centralized minimum number of searchers. Moreover, our lower bound holds even in a synchronous setting, while our constructive upper bound holds even in an asynchronous setting.     

The hsp150Δ-carrier confers secretion competence to the rat nerve growth factor receptor ectodomain in Saccharomyces cerevisiae

When the extracellular domain of rat low-affinity nerve growth factor receptor (NGFR_e) was synthesized in Saccharomyces cerevisiae with the signal peptide of invertase, NGFR_e was translocated to the endoplasmic reticulum (ER) and retained there. However, when NGFR_e was fused to the C-terminus of the hsp150Δ-carrier, the hsp150Δ–NGFR_e fusion protein was efficiently secreted to the growth medium with no apparent retention in the ER. The NGFR_e portion was disulphide-bonded and its single N-glycosylation site was occupied. The hsp150Δ-carrier is an N-terminal signal peptide-containing fragment of a yeast secretory glycoprotein. Hsp150Δ–NGFR_e, harvested from the culture medium, inhibited the cross-linking of [¹²⁵I]NGF to authentic NGFR on the surface of human melanoma cells. Moreover, [¹²⁵I]NGF could be chemically cross-linked to secretory hsp150Δ–NGFR_e, suggesting that the NGFR_e portion had adopted a ligand-binding conformation. However, inhibition of the cross-linking by unlabelled NGF was less effective than in the case of the authentic receptor. The hsp150Δ-carrier may have potential in the production of mammalian proteins, which require elaborate folding and disulphide formation in the ER.     

Sodium aluminate from alumina-bearing intermediates and wastes

It has been ascertained from theoretical premises and commercial practice that sodium aluminate may be produced using alumina-bearing industrial intermediates and wastes, including spent potliner and salt cake resulting from aluminum-dross recycling. The utilization of these unused waste materials can provide a supply for the world’s demand for sodium aluminate and improve environmental conditions. Victor Rayzman earned his Ph.D. in metallurgy at the National Research and Design Institute of Aluminum, Magnesium and Electrod Industry (VAMI) in 1978. He is currently an independent consultant. Igor Filipovich earned his M.Sc. in metallurgy at Leningrad Mining Institute of St. Petersburg in 1980. He is currently an analytical chemist for Safety Kleen Corporation. Leonid Nisse earned his M.Sc. in chemical engineering at Leningrad Technological Institute in 1967. He is currently a supervisor of an alumina workshop at Leningrad Pilot Plant in St. Petersburg, Russia. Yuri Vlasenko earned his M.Sc. in metallurgy at Leningrad Mining Institute of St. Petersburg in 1959. He is currently a researcher at St. Petersburg Institute of Mineral Resources Enrichment (Mekhanobr).