Browsing by Author "Misra, P."

Filter results by typing the first few letters
Now showing 1 - 3 of 3
  • No Thumbnail Available
    Item
    Parameterized algorithms for survivable network design with uniform demands
    (2018) Bang-Jensen, J.; Basavaraju, M.; Klinkby, K.V.; Misra, P.; Ramanujan, M.S.; Saurabh, S.; Zehavi, M.
    In the Survivable Network Design Problem (SNDP), the input is an edge-weighted (di)graph G and an integer ruv for every pair of vertices u; v 2 V (G). The objective is to construct a subgraph H of minimum weight which contains ruv edge-disjoint (or node-disjoint) u-v paths. This is a fundamental problem in combinatorial optimization that captures numerous well-studied problems in graph theory and graph algorithms. Consequently, there is a long line of research into exact-polynomial time algorithms as well as approximation algorithms for various restrictions of this problem. An important restriction of this problem is one where the connectivity demands are the same for every pair of vertices. In this paper, we first consider the edge-connectivity version of this problem which we call ?-Edge Connected Subgraph ( ?-ECS). In this problem, the input is a ?-edge connected (di)graph G and an integer k and the objective is to check whether G contains a spanning subgraph H that is also ?-edge connected and H excludes at least k edges of G. In other words, we are asked to compute a maximum subset of edges, of cardinality at least k, which may be safely deleted from G without affecting its connectivity. If we replace ?-edge connectivity with ?-vertex connectivity we get the ?-Vertex Connected Subgraph ( ?-VCS) problem. We show that ?-ECS is fixed-parameter tractable (FPT) for both graphs and digraphs even if the (di)graph has nonnegative real weights on the edges and the objective is to exclude from H, some edges of G whose total weight exceeds a prescribed value. In particular, we design an algorithm for the weighted variant of the problem with running time 2O(k log k)jV (G)jO(1). We follow up on this result and obtain a polynomial compression for ?-ECS on unweighted graphs. As a direct consequence of our results, we obtain the first FPT algorithm for the parameterized version of the classical Minimum Equivalent Graph (MEG) problem. We also show that ?-VCS is FPT on digraphs; however the problem on undirected graphs remains open. Finally, we complement our algorithmic findings by showing that SNDP is W[1]-hard for both arc and vertex connectivity versions on digraphs. The core of our algorithms is composed of new combinatorial results on connectivity in digraphs and undirected graphs. � Copyright 2018 by SIAM.
  • No Thumbnail Available
    Item
    Parameterized algorithms for survivable network design with uniform demands
    (Association for Computing Machinery acmhelp@acm.org, 2018) Bang-Jensen, J.; Basavaraju, M.; Klinkby, K.V.; Misra, P.; Ramanujan, M.S.; Saurabh, S.; Zehavi, M.
    In the Survivable Network Design Problem (SNDP), the input is an edge-weighted (di)graph G and an integer ruv for every pair of vertices u; v 2 V (G). The objective is to construct a subgraph H of minimum weight which contains ruv edge-disjoint (or node-disjoint) u-v paths. This is a fundamental problem in combinatorial optimization that captures numerous well-studied problems in graph theory and graph algorithms. Consequently, there is a long line of research into exact-polynomial time algorithms as well as approximation algorithms for various restrictions of this problem. An important restriction of this problem is one where the connectivity demands are the same for every pair of vertices. In this paper, we first consider the edge-connectivity version of this problem which we call λ-Edge Connected Subgraph ( λ-ECS). In this problem, the input is a λ-edge connected (di)graph G and an integer k and the objective is to check whether G contains a spanning subgraph H that is also λ-edge connected and H excludes at least k edges of G. In other words, we are asked to compute a maximum subset of edges, of cardinality at least k, which may be safely deleted from G without affecting its connectivity. If we replace λ-edge connectivity with λ-vertex connectivity we get the λ-Vertex Connected Subgraph ( λ-VCS) problem. We show that λ-ECS is fixed-parameter tractable (FPT) for both graphs and digraphs even if the (di)graph has nonnegative real weights on the edges and the objective is to exclude from H, some edges of G whose total weight exceeds a prescribed value. In particular, we design an algorithm for the weighted variant of the problem with running time 2O(k log k)jV (G)jO(1). We follow up on this result and obtain a polynomial compression for λ-ECS on unweighted graphs. As a direct consequence of our results, we obtain the first FPT algorithm for the parameterized version of the classical Minimum Equivalent Graph (MEG) problem. We also show that λ-VCS is FPT on digraphs; however the problem on undirected graphs remains open. Finally, we complement our algorithmic findings by showing that SNDP is W[1]-hard for both arc and vertex connectivity versions on digraphs. The core of our algorithms is composed of new combinatorial results on connectivity in digraphs and undirected graphs. © Copyright 2018 by SIAM.
  • No Thumbnail Available
    Item
    Studies on Resistive Switching of Cu/Ta2O5/Pt Devices for Non-volatile Memory Application
    (Springer, 2021) Thathron, T.; Sahu, V.K.; Ajimsha, R.S.; Das, A.K.; Misra, P.
    In recent times, memory devices based on resistive switching (RS) phenomena in dielectric materials have become a strong contender for the futuristic universal memory. Among other materials being explored for RS application, tantalum pentaoxide (Ta2O5) has emerged as potential candidate due to its large dielectric constant and compatibility with the existing complementary metal-oxide semiconductor process. In view of this, we have studied the resistive switching memory characteristics of Ta2O5 thin film in Cu/Ta2O5/Pt device configuration. About 200 nm thick films of Ta2O5were deposited on platinum-coated silicon (Pt/Si) substrate by Pulsed Laser Deposition (PLD) method. On the top of Ta2O5 thin film, Cu electrodes of radius ~100 µm and thickness ~ 100nm were grown by RF magnetron sputtering using shadow masking. The RS behaviour of Cu/Ta2O5/Pt devices was studied by current–voltage (I-V) measurements at room temperature. The as-fabricated Cu/Ta2O5/Pt devices showed repeatable and reliable, non-volatile bipolar resistance switching for 100 cycles, indicating good endurance. Due to virgin low resistance state of the device, the initial electroforming step was not required for bipolar RS. The mean resistance of high resistance state (HRS) and low resistance state (LRS) was ~300 MΩ and 500 Ω respectively with very high resistance ratio of ~106. The Cu/Ta2O5/Pt devices showed good data retention up to 103 s. The resistive switching mechanism in Cu/Ta2O5/Pt devices was understood in terms of redox reaction based formation and rupturing of conducting filaments constituting copper ions. The conduction mechanism in LRS was explained on the basis of Ohmic conduction, whereas Schottky emission and space charge limited conduction (SCLC) were found as possible conduction mechanisms in HRS. Our studies clearly show that Ta2O5-based resistive switching devices may have applications in futuristic universal non-volatile memory technology. © 2021, The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.