Abstract

An acyclic vertex coloring of a graph is a proper vertex coloring such that there are no bichromatic cycles. The acyclic chromatic number of G, denoted a (G), is the minimum number of colors required for acyclic vertex coloring of graph G=(V, E). In this paper we show that for any graph G with maximum degree∆, a (G)≤ 3∆ 2+ 4∆+ 8

Abstract

people volunteer their time and energy and work in a dedicated fashion to pull everything together each year, including our very supportive Steering Comm-tee members led by Sukumar Ghosh. However, the success of ICDCN is mainly due to the hard work of all those people who submit papers and/or attend the conference. We thank you all. January 2009 Prasad Jayanti Andrew T. Campbell Message from the Technical Program Chairs Welcome to the proceedings of the 10thInternationalConferenceon Distributed Computing and Networking (ICDCN) 2009. As ICDCN celebrates its 10th-niversary, ithasbecomeanimportantforumfordisseminatingthelatestresearch results in distributed computing and networking. We received 179 submissions from all over the world, including Algeria, A-tralia, Canada, China, Egypt, France, Germany, Hong Kong, Iran, Italy, Japan, Malaysia, The Netherlands, Poland, Singapore, South Korea, Taiwan, and the USA, besides India, the host country. The submissions were read and evaluated by the Program Committee, which consisted of 25 members for the Distributed Computing Track and 28 members for the Networking Track, with the ad-tional help of external reviewers. The Program Committee selected 20 regular papers and 32 short papers for inclusion in the proceedings and presentation at the conference. We were fortunate to have several distinguished scientists as keynote speakers. Andrew Campbell (Dartmouth College, USA), Maurice Herlihy (Brown University, USA), and PR Kumar (University of of Illinois, Urbana-Champaign) delivered the keynote address. Krithi Ramamritham from IIT Bombay, India

Abstract

In this paper, we address the security of routing protocols. Internet routing protocols are subject to attacks in the control plane as well as the data plane. In the control plane, a routing protocol, e.g., BGP, OSPF, exchanges routing state updates and enables routers to compute the best paths towards various destinations. During this phase, an attacker can modify or inject malicious control messages leading to incorrect computation of routing paths. In the data plane, the routers forward the data along the paths computed in the control plane. Even if an attacker is not successful during the control phase, he can choose not to use the correct routing paths and forward data along routes that benefit him. Research shows that, attacks on the control plane can be mitigated by ensuring message integrity and, attacks on the data plane can be mitigated by ensuring route integrity. Earlier works have addressed these two problems independently with many interesting solutions. However, due to the nature of these solutions, network architects cannot deploy security at both planes without increasing the overhead on the network. In this paper, we focus on an integrated approach and propose the use of symmetric key protocols for addressing the security at both the control and data planes. We describe approaches that enable the reuse of the symmetric key protocols thereby eliminating the need for separate solutions at different planes. We used symmetric key protocols as they are efficient and scalable. Our experimental results show that our approaches are practical and can be incrementally deployed as well.

Abstract

Scenarios such as online banking, mobile payment systems, stock trading, selling merchandise, and a host of other applications that need a high level of security have moved from the research domain to real world. Moreover, the nature of clients has been changing from traditional desktops to mobile and handheld devices. Protocols like SSL, SSH are the present standard for establishing secure channels. However, the drawback in these protocols is that both the server and the client need to perform computationally expensive public-key operations for secure channel establishment. In this paper, we present simple constructions that spread the cost of secure channel establishment over several sessions. Our constructions are incrementally deployable and can operate with existing protocols such as SSL and SSH. Experimental results indicate that our constructions are practical and efficient in reducing the computational load at the server as well as the client side.

Abstract

A vertex magic total labeling of a graph G = (V, E) is a bijection f: V ≼ E → {1, 2,…, |V| + |E|} such that for every vertex w, the sum is a constant. It is well known that all complete graphs Kn admit a vertex magic total labeling. In this paper we present a new proof of this theorem using the concepts of twin factorization and magic square.

Abstract

Let G = (V, E) be a graph and let f: V → {0, 1} be a mapping from the set of vertices to {0, 1} and for each edge (u, v) ∊ E assign the label |f(u) — f(v)|. If the number of vertices labeled with 0 and the number of vertices labeled with 1 differ by at most 1 and the number of edges labled with 0 and the number of edges labeled with 1 differ by at most 1, then f is called a cordial labeling. In this paper, we present two families of planar graphs, Pln and Plm,n defined shortly, that admit a cordial labeling. We also show that the class Plm,n admits a total product cordial labeling under certain conditions.

Abstract

Urea concentration dependent denaturation of proteins and nucleic acids has been widely used in obtaining (un)folding pathways and in calculating the free energies. Molecular dynamics simulations were performed on a 22-nt RNA hairpin in aqueous solution environment and in different concentrations (1-8M) of urea. The energetic and structural aspects of the role of urea in denaturating the RNA hairpin were investigated. In agreement with experimental studies, the RNA undergoes denaturation at higher concentrations of urea (> 6M). Surprisingly, the hairpin was observed to be more stable at lower concentrations of urea (1-2M) even compared to the RNA in aqueous environment. Various structural, energetic and solvation properties were analyzed to understand the mechanism of the interaction of urea with the hairpin. It was observed that urea does not directly facilitate the opening of the base pairs that leads to denaturation at higher concentrations. Instead, the open states of the RNA are stabilized by via hydrogen bonding interactions and stacking interactions thereby stabilizing the denatured form of the RNA.

Abstract

Base flipping is a process by which one of the bases of the DNA swings out from its helical position to an extrahelical form. Several proteins such as methyltransferases, glycosylases and endonucleases employ this phenomenon in order to gain access to the target base for chemical modification. Even in the absence of protein, base pair opening occurs in nucleic acids in solution. X-ray crystal studies, fluorescence spectroscopy and NMR imino proton exchange experiments have been extensively employed to study the structures and dynamics involved in this fascinating event. We have employed molecular dynamics simulations to study base flipping both in presence and absence of the protein. The free energy pathways obtained using potential of mean force calculations will be presented. The base pair opening dynamics of AT and GC base pairs was investigated by calculating the equilibrium constants corresponding to the equilibrium between the base pair open and closed states, and compared with experimental data. Our calculations showed that the contribution to the overall equilibrium constants of the base pair opening is primarily from the purine bases. The methodological issues such as sufficient sampling and force field parameters will be addressed. In another study, the role of THR250 HhaI methyltransferase in base flipping will be discussed. THR250 is a highly conserved residue in methyltransferases and was proposed to be crucial for the correct placement of flipped cytosine for methylation. Previous computational studies have shown that the protein actively facilitates the base flipping process. Free energy calculations of base flipping in the presence of the wild type and T250G, T250A and T250D mutants of the protein were computed. The free energy profiles, structural changes and the energetic parameters for the base flipping process will be presented.

Abstract

Sac7d is a protein present in Sulfolobus acidocaldarius, a hyperthermophilic archaeon, which is stable at extreme conditions. It is a chromosomal protein, which is capable of binding DNA thereby increasing its melting temperature. It was suggested to stabilize central 3 to 5 base pair steps in DNA. It binds to the minor groove of the DNA causing a kink in the helix without any sequential preference. We have used molecular dynamics (MD) simulations to study the binary complexes of Sac7d bound to DNA at 300 and 360 K. The objective is to understand the atomic detailed mechanism of the capability of Sac7d in facilitating DNA stability at higher temperature. As has been shown before, the structure of the protein is highly stable both at 300 and 360 K. The DNA duplex was found to be stable at 300 K and is similar to the X-ray crystal structure. Consistent with experiments, at least the central four base pairs of the DNA were found to be base paired during most of the simulation at 360 K. The dynamic properties of the protein in the protein-DNA complexes remained unchanged compared to when the protein is unbound. Interestingly, B- to A-form transitions occur in both the DNA molecules when bound to Sac7d, which was confirmed by sugar puckering angles, and backbone dihedral angles. Detailed examination of the protein-DNA interactions reveals that the stabilization of the DNA molecules is mostly due to the favorable interaction of the protein with the backbone of the DNA.

Abstract

Macrocyclic trienes are important precursors for the synthesis of several biologically relevant molecules such as steroids. These molecules undergo (4+2) cycloaddition to form tricyclic compounds, which has four newly formed stereocenters. The stereochemistry at these four carbon centers has been shown to be largely controlled by the reaction energy barriers, and the conformational preferences of the macrocycle. Molecular dynamics (MD) simulation is a highly efficient approach for studying conformational properties of chemical molecules and biological macromolecules. MP2/6-31G* method was used to obtain potential energy surfaces corresponding to appropriate model compounds and used as the target data. The force field parameters were refined to accurately represent the target data involving all the model compounds chosen. Using the refined molecular mechanics force field, MD simulations were performed on six possible 14-membered symmetric trienes at different temperatures. We have also used replica exchange MD (RexMD) simulations with eight replicas between 300 and 370 K. The molecules were found to sample a larger conformational space in the RexMD simulation compared to the regular MD simulations. The probability distributions corresponding to the dihedral angles, and distances between the reaction centers have been analyzed. The relationship between the conformational sampling of the macrocyclic trienes vis-à-vis their reactivity will be discussed. Additionally, clustering of the structures from the MD trajectories was done to identify all unique conformations using a new approach.