Surface and Biocidal Properties of Gemini Cationic Surfactants Based on Propoxylated 1,6-Diaminohexane and Alkyl Bromides

Two new classes of gemini cationic surfactants—hexanediyl-1,6-bis[(isopropylol) alkylammonium] dibromide {in the abbreviation form: C_nC₆C_n[iPr-OH] and C_nC₆C_n[iPr-OH]₂; alkyl: C_nH_{2n + 1} with n = 9, 10, 12 and 14}—have been synthesized by interaction of alkyl bromides with N,N′-di-(isopropylol)-1,6-diaminohexane and N,N,N′,N′-tetra-(isopropylol)-1,6-diaminohexane. The surface tension, electrical conductivity, and dynamic light scattering (DLS) techniques were used to investigate the aggregation properties of the gemini cationic surfactants in aqueous solution. The formation of critical aggregates at two concentrations in an aqueous solution from obtained gemini cationic surfactants were determined via the tensiometric method. Thus, these gemini cationic surfactants start to form aggregates at concentrations well below their critical micelle concentrations (CMC). The surface properties and the binding degree (β) of the opposite ion were tested against the length of the surfactant hydrocarbon chain and the number of the isopropylol groups in the head group. By applying the DLS technique, it was explored that how the number of isopropylol groups in gemini cationic surfactants with C₁₂H₂₅ chain affects the sizes of micelles at concentrations greater than CMC. It was discovered that the obtained gemini cationic surfactants have a biocidal character.     

An exact algorithm for minimum distortion embedding

Let G be an unweighted connected graph on n vertices. We show that an embedding of the shortest path metric of G into the line with minimum distortion can be found in time 5^n+o(n). This is the first algorithm breaking the trivial n!-barrier.     

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”.     

Spanners of bounded degree graphs

A k-spanner of a graph G is a spanning subgraph of G in which the distance between any pair of vertices is at most k times the distance in G. We prove that for fixed k,w, the problem of deciding if a given graph has a k-spanner of treewidth w is fixed-parameter tractable on graphs of bounded degree. In particular, this implies that finding a k-spanner that is a tree (a tree k-spanner) is fixed-parameter tractable on graphs of bounded degree. In contrast, we observe that if the graph has only one vertex of unbounded degree, then Treek-Spanner is NP-complete for k?4.     

Implicit branching and parameterized partial cover problems

Covering problems are fundamental classical problems in optimization, computer science and complexity theory. Typically an input to these problems is a family of sets over a finite universe and the goal is to cover the elements of the universe with as few sets of the family as possible. The variations of covering problems include well-known problems like Set Cover, Vertex Cover, Dominating Set and Facility Location to name a few. Recently there has been a lot of study on partial covering problems, a natural generalization of covering problems. Here, the goal is not to cover all the elements but to cover the specified number of elements with the minimum number of sets. In this paper we study partial covering problems in graphs in the realm of parameterized complexity. Classical (non-partial) version of all these problems has been intensively studied in planar graphs and in graphs excluding a fixed graph H as a minor. However, the techniques developed for parameterized version of non-partial covering problems cannot be applied directly to their partial counterparts. The approach we use, to show that various partial covering problems are fixed parameter tractable on planar graphs, graphs of bounded local treewidth and graph excluding some graph as a minor, is quite different from previously known techniques. The main idea behind our approach is the concept of implicit branching. We find implicit branching technique to be interesting on its own and believe that it can be used for some other problems.