检索结果-内蒙古大学图书馆

Improved bounds on the span of L(1, 2)-edge labeling of some infinite regular grids

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Bandopadhyay, Susobhan Ghosh, Sasthi C. Koley, Subhasis School Of Computer Sciences National Institute Of Science Education And Research Bhubaneswar India Advanced Computing And Microelectronics Unit Indian Statistical Institute Kolkata India

For two given nonnegative integers h and k, an L(h, k)-edge labeling of a graph G is the assignment of labels {0, 1,⋯, n} to the edges so that two edges having a common vertex are labeled with difference at least h and two edges not having any common vertex but having a common edge connecting them are labeled with difference at least k. The span λ′h,k(G) is the minimum n such that G admits an L(h, k)-edge labeling. Here our main focus is on finding λ′1,2(G) for L(1, 2)-edge labeling of infinite regular hexagonal (T3), square (T4), triangular (T6) and octagonal (T8) grids. It was known that 7 ≤ λ′1,2(T3) ≤ 8, 10 ≤ λ′1,2(T4) ≤ 11, 16 ≤ λ′1,2(T6) ≤ 20 and 25 ≤ λ′1,2(T8) ≤ 28. Here we settle two long standing open questions i.e. λ′1,2(T3) and λ′1,2(T4). We show λ′1,2(T3) = 7, λ′1,2(T4) = 11. We also improve the bound for T6and T8and prove λ′1,2(T6) ≥ 18, λ′1,2(T8) ≥ 26. © 2022, CC BY.

关键词： Graph theory

MAB based Network Selection mechanism for URLLC users in RIS assisted network

学校读者我要写书评

暂无评论

MAB based Network Selection mechanism for URLLC users in RIS...

IEEE International Symposium on Network computing and Applications

作者： Souvik Deb Shankar Kumar Ghosh Sasthi C. Ghosh Advanced Computing & Microelectronics Unit Indian Statistical Institute Kolkata India Department of CSE Shiv Nadar Institution of Eminence Delhi NCR India

ISBN: (纸本)9798350397314

In this work, a network selection mechanism for re-configurable intelligent surface (RIS) assisted network has been proposed. The goal of the proposed mechanism is to select appropriate base station (BS) or BS-RIS pair to maximize user throughput while satisfying the delay and reliability constraints of uRLLC users. First, the network selection mechanism for RIS assisted network has been formulated as multi arm bandit (MAB) problem; Then, based on the formulation, a network selection strategy has been proposed. Finally, through extensive system level simulations, it has been shown that the proposed scheme outperforms the existing A3 handover scheme in terms of reliability and user throughput.

关键词： Integer programming Base stations Computational modeling Ultra reliable low latency communication Handover Throughput Delays

Asymptotically improved circuit for a d-ary Grover's algorithm with advanced decomposition of the n-qudit Toffoli gate

学校读者我要写书评

暂无评论

Physical Review A 2022年第6期105卷 062453-062453页

作者： Amit Saha Ritajit Majumdar Debasri Saha Amlan Chakrabarti Susmita Sur-Kolay A. K. Choudhury School of Information Technology University of Calcutta Calcutta 700106 India ATOS Pune 411045 India Advanced Computing & Microelectronics Unit Indian Statistical Institute Calcutta 700108 India

The progress in building quantum computers to execute quantum algorithms has recently been remarkable. Grover's search algorithm in a binary quantum system provides a considerable speed-up over the classical paradigm. It can be extended to a d-ary (qudit) quantum system also for utilizing the advantage of larger state space, which helps to reduce the runtime of the algorithm as compared to the traditional binary quantum systems. In a qudit quantum system, an n-qudit Toffoli gate plays a significant role in the accurate implementation of Grover's algorithm. In this article, a generalized n-qudit Toffoli gate is realized using higher-dimensional qudits to attain a logarithmic depth decomposition without ancilla qudit. The circuit for Grover's algorithm has then been designed for any d-ary quantum system, where d≥2, with the proposed n-qudit Toffoli gate to obtain optimized depth compared to earlier approaches. The technique for decomposing an n-qudit Toffoli gate requires access to two immediately higher-energy levels, making the design susceptible to errors. Nevertheless, we show that the percentage decrease in the probability of error is significant with both gate count and circuit depth reduced as compared to that in state-of-the-art works.

关键词： Quantum computation Quantum engineering

MINIMUM CONSISTENT SUBSET IN TREES AND INTERVAL GRAPHS

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Banik, Aritra Das, Sayani Maheshwari, Anil Manna, Bubai Nandy, Subhas C. Krishna Priya, K.M. Roy, Bodhayan Roy, Sasanka Sahu, Abhishek National Institute of Science Education and Research An OCC of Homi Bhabha National Institute Odisha Bhubaneswar752050 India Theoretical Computer Science The Institute of Mathematical Sciences India School of Computer Science Carleton University Canada Department of Mathematics Indian Institute of Technology Kharagpur India Advanced Computing and Microelectronics Unit Indian Statistical Institute Kolkata India

In the Minimum Consistent Subset (MCS) problem, we are presented with a connected simple undirected graph G = (V, E), consisting of a vertex set V of size n and an edge set E. Each vertex in V is assigned a color from the set {1, 2, . . ., c}. The objective is to determine a subset V ′ ⊆ V with minimum possible cardinality, such that for every vertex v ∈ V , at least one of its nearest neighbors in V ′ (measured in terms of the hop distance) shares the same color as v. The decision problem, indicating whether there exists a subset V ′ of cardinality at most l for some positive integer l, is known to be NP-complete even for planar graphs. In this paper, we establish that the MCS problem for trees, when the number of colors c is considered an input parameter, is NP-complete10. We propose a fixed-parameter tractable (FPT) algorithm for MCS on trees running in O(26cn6) time, significantly improving the currently best-known algorithm whose running time is O(24cn2c+3). In an effort to comprehensively understand the computational complexity of the MCS problem across different graph classes, we extend our investigation to interval graphs. We show that it remains NP-complete for interval graphs, thus enriching graph classes where MCS remains intractable. Copyright © 2024, The Authors. All rights reserved.

关键词： Color

Evaluating Conditional Handover for 5g Networks with Dynamic Obstacles

学校读者我要写书评

暂无评论

SSRN

SSRN 2024年

作者： Deb, Souvik Rathod, Megh Balamurugan, Rishi Singh, Rajeev Kumar Sanyal, Samriddha Ghosh, Shankar K. Advanced Computing & Microelectronics Unit Indian Statistical Institute West Bengal Kolkata700108 India Department of Computer Science and Engineering Shiv Nadar Institution of Eminence Delhi201314 India School of Computing and Data Science FLAME University Maharashtra Pune412115 India Shiv Nadar University India

To enhance seamless connectivity in millimetre wave New radio networks, Conditional handover has evolved as a promising solution. Unlike A3 handover where handover execution is certain after receiving handover command from the serving access network, in conditional handover, handover execution is conditional on the Reference signal received power measurements from both current and target access networks, as well as on mobility parameters such as preparation and execution offsets. Presence of dynamic obstacles may block the signal from serving and (or) target access networks, which results in violation of the conditions for the handover preparation/execution. Moreover, signal blockage by dynamic obstacles may cause radio link failure, which may cause handover failure as well. Analytic evaluations of conditional handover performance in the presence of dynamic obstacles are quite limited in the preceding literature. In this work, handover performance of conditional handover has been carried out in terms of handover latency, handover packet loss and handover failure probability. A Markov model accounting the effect of dynamic obstacles, different mobility parameters (e.g., execution offset, preparation offset, time-to-preparation and time-to-execution), user velocity and channel fading characteristics has been proposed to characterize handover failure. Results obtained from the analytic model has been validated against extensive simulation results. Our study reveal that optimal configuration of the mobility parameters is actually conditional on the presence of dynamic obstacles, user velocity and fading characteristics. This study will be helpful for the mobile operators to configure the mobility parameters for New radio systems where dynamic obstacles are present. © 2024, The Authors. All rights reserved.

关键词： 5G mobile communication systems

SOK: An Evaluation of Quantum Authentication through Systematic Literature Review

学校读者我要写书评

暂无评论

SSRN

SSRN 2021年

作者： Majumdar, Ritajit Das, Sanchari Advanced Computing and Microelectronics Unit Indian Statistical Institute Kolkata India University of Denver

Quantum computers are considered a blessing to the dynamic technological world that promises to solve complex problems much faster than their known classical counterparts. Such computational power imposes critical threats on modern cryptography where it has been proven that asymmetric key cryptosystem will be rendered useless in a quantum world. However, we can utilize such a powerful mechanism for improving computer security by implementing such technology to solve complex data security problems such as authentication, secrets management, and others. Mainly, Quantum Authentication (QA) is an emerging concept in computer security that creates robust authentication for organizations, systems, and individuals. To delve deeper into the concept, for this research, we have further investigated QA through a detailed systematic literature review done on a corpus of N = 859 papers. We briefly discuss the major protocols used by various papers to achieve QA, and also note the distribution of papers using those protocols. We analyzed the technological limitations mentioned by previous researchers and highlighted the lack of human-centered solutions for such modern inventions. We emphasize the importance of research in the user aspect of QA to make the users aware of its potential advantages and disadvantages as we move to the quantum age. © 2021, The Authors. All rights reserved.

关键词： Authentication

On Fault Tolerance of Circuits with Intermediate Qutrit-assisted Gate Decomposition

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Majumdar, Ritajit A., Saha A., Chakrabarti S., Sur-Kolay Advanced Computing & Microelectronics Unit Indian Statistical Institute India Atos Pune India A. K. Choudhury School of Information Technology University of Calcutta India

The use of a few intermediate qutrits for efficient decomposition of 3-qubit unitary gates has been proposed, to obtain an exponential reduction in the depth of the decomposed circuit. An intermediate qutrit implies that a qubit is operated as a qutrit in a particular execution cycle. This method, primarily for the NISQ era, treats a qubit as a qutrit only for the duration when it requires access to the state |2〉 during the computation. In this article, we study the challenges of including fault-tolerance in such a decomposition. We first show that any qubit that requires access to the state |2〉 at any point in the circuit, must be encoded using a qutrit quantum error correcting code (QECC), thus resulting in a circuit with both qubits and qutrits at the outset. Since qutrits are noisier than qubits, the former is expected to require higher levels of concatenation to achieve a particular accuracy than that for qubit-only decomposition. Next, we derive analytically (i) the number of levels of concatenation required for qubit-qutrit and qubit-only decompositions as a function of the probability of error, and (ii) the criterion for which qubit-qutrit decomposition leads to a lower gate count than qubit-only decomposition. We present numerical results for these two types of decomposition and obtain the situation where qubit-qutrit decomposition excels for the example circuit of the quantum adder by considering different values for quantum hardware-noise and non-transversal implementation of the 2-controlled ternary CNOT gate. © 2022, CC BY.

关键词： Timing circuits

Approximate Shortest Paths in Polygons with Violations

学校读者我要写书评

暂无评论

International Journal of Computational Geometry and Applications 2020年第1期30卷 79-95页

作者： Dutta, Binayak Roy, Sasanka Department of Computer Science and Engineering Tezpur University Tezpur India Advanced Computing and Microelectronics Unit Indian Statistical Institute Kolkata India

We study the shortest k-violation path problem in a simple polygon. Let P be a simple polygon in 2 with n vertices and let s,t be a pair of points in P. Let int(P) represent the interior of P. Let P = 2(P) represent the exterior of P. For an integer k ≥ 0, the shortest k-violation path problem in P is the problem of computing the shortest path from s to t in P, such that at most k path segments are allowed to be in P. The subpaths of a k-violation path are not allowed to bend in P. For any k, we present a (1 + 2) factor approximation algorithm for the problem that runs in O(n2σ2klog n2σ2 + n2σ2k) time. Here σ = O(log(L r)) and, L, r are geometric parameters. © 2020 World Scientific Publishing Company.

关键词： approximation polygons shortest paths Steiner points triangulation violations

Parking Problem by Oblivious Mobile Robots in Infinite Grids

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Chakraborty, Abhinav Mukhopadhyaya, Krishnendu Department of Computer Science and Engineering Institute of Technical Education and Research Siksha O Anusandhan University Odisha Bhubaneswar India Advanced Computing and Microelectronics Unit Indian Statistical Institute 203 B. T. Road West Bengal Kolkata700108 India

In this paper, the parking problem of a swarm of mobile robots has been studied. The robots are deployed at the nodes of an infinite grid, which has a subset of prefixed nodes marked as parking nodes. Each parking node pi has a capacity of ki which is given as input and equals the maximum number of robots a parking node can accommodate. As a solution to the parking problem, robots need to partition themselves into groups so that each parking node contains a number of robots that are equal to the capacity of the node in the final configuration. It is assumed that the number of robots in the initial configuration represents the sum of the capacities of the parking nodes. The robots are assumed to be autonomous, anonymous, homogeneous, identical and oblivious. They operate under an asynchronous scheduler. They neither have any agreement on the coordinate axes nor do they agree on a common chirality. All the initial configurations for which the problem is unsolvable have been identified. A deterministic distributed algorithm has been proposed for the remaining configurations, ensuring the solvability of the problem. Copyright © 2023, The Authors. All rights reserved.

关键词： Mobile robots