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

Minimum Consistent Subset in Trees and Interval Graphs 44

学校读者我要写书评

暂无评论

Minimum Consistent Subset in Trees and Interval Graphs

44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 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 Bhubaneswar India Theoretical Computer Science The Institute of Mathematical Sciences Chennai India School of Computer Science Carleton University OttawaON Canada Department of Mathematics Indian Institute of Technology Kharagpur India Advanced Computing and Microelectronics Unit Indian Statistical Institute Kolkata India

ISBN: (纸本)9783959773553

In the Minimum Consistent Subset (MCS) problem, we are presented with a connected simple undirected graph G, consisting of a vertex set V (G) of size n and an edge set E(G). Each vertex in V (G) is assigned a color from the set {1, 2, ⋯, c}. The objective is to determine a subset V′ ⊆ V (G) with minimum possible cardinality, such that for every vertex v ∈ V (G), 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 is NP-complete on trees. We also provide a fixed-parameter tractable (FPT) algorithm for MCS on trees parameterized by the number of colors (c) 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. © 2024 Aritra Banik, Sayani Das, Anil Maheshwari, Bubai Manna, Subhas C. Nandy, Krishna Priya K. M., Bodhayan Roy, Sasanka Roy, and Abhishek Sahu.

关键词： Undirected graphs

Mutual Visibility by Fat Robots with Slim Omnidirectional Camera

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Bose, Kaustav Chakraborty, Abhinav Mukhopadhyaya, Krishnendu Advanced Computing and Microelectronics Unit Indian Statistical Institute Kolkata India Advanced Computing and Microelectronics Unit Indian Statistical Institute Kolkata India Advanced Computing and Microelectronics Unit Indian Statistical Institute Kolkata India

In the existing literature of the MUTUAL VISIBILITY problem for autonomous robot swarms, the adopted visibility models have some idealistic assumptions that are not consistent with practical sensing device implementations. This paper investigates the problem in the more realistic visibility model called opaque fat robots with slim omnidirectional camera. The robots are modeled as unit disks, each having an omnidirectional camera represented as a disk of smaller size. We assume that the robots have compasses that allow agreement in the direction and orientation of both axes of their local coordinate systems. The robots are equipped with visible lights which serve as a medium of communication and also as a form of memory. We present a distributed algorithm for the MUTUAL VISIBILITY problem which is provably correct in the semi-synchronous setting. Our algorithm also provides a solution for LEADER ELECTION which we use as a subroutine in our main algorithm. Although LEADER ELECTION is trivial with two axis agreement in the full visibility model, it is challenging in our case and is of independent interest. Copyright © 2022, The Authors. All rights reserved.

关键词： Visibility

Resource-aware scheduling of multiple quantum circuits on a hardware device

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Bhoumik, Debasmita Majumdar, Ritajit Sur-Kolay, Susmita Advanced Computing & Microelectronics Unit Indian Statistical Institute India IBM Quantum IBM India Research Lab India

Recent quantum technologies and quantum error-correcting codes emphasize the requirement for arranging interacting qubits in a nearest-neighbor (NN) configuration while mapping a quantum circuit onto a given hardware device, in order to avoid undesirable noise. It is equally important to minimize the wastage of qubits in a quantum hardware device with m qubits while running circuits of n qubits in total, with n © 2024, CC BY.

关键词： Timing circuits

A Framework for Tile Processing on Edge Servers for Roadside Traffic Surveillance 23

学校读者我要写书评

暂无评论

A Framework for Tile Processing on Edge Servers for Roadside...

Proceedings of the 7th International Conference on Algorithms, computing and Systems

作者： Saumya Jaipuria Arani Bhattacharya Ansuman Banerjee Advanced Computing and Microelectronics Unit Indian Statistical Institute India Department of Computer Science Indraprastha Institute of Information Technology India

ISBN: (纸本)9798400709098

Roadside traffic monitoring is increasingly performed by deploying roadside high-resolution video cameras and then running Computer Vision (CV) models on the video data. Since computer vision models are compute-intensive as they utilize Deep Neural Networks (DNNs), the data is usually sent to one or more edge servers located adjacent to mobile base stations. Recent techniques propose running CV models on tiles of videos separately to detect and track small objects. Several CV models exist, each with different requirements of compute and memory. Since more compute and memory-intensive CV models provide higher accuracy, a key challenge of such techniques is to determine which vision model should be used on which tile. This becomes even more challenging if multiple videos are processed by the same edge server. In this paper, we first formulate this problem of model selection on edge devices as an Integer Linear Programming (ILP) problem, and then propose a heuristic to solve it. Our experiments show that it is quite effective in practice.

关键词： Computer Vision Edge computing Integer Linear Programming

A Fast Community-based Approach for Discovering Anomalies in Evolutionary Networks 14

学校读者我要写书评

暂无评论

A Fast Community-based Approach for Discovering Anomalies in...

14th International Conference on COMmunication Systems and NETworkS, COMSNETS 2022

作者： Ghoshal, Arnab Kumar Das, Nabanita Das, Soham Asutosh College Department of Computer Science Kolkata India Indian Statistical Institute Advanced Computing and Microelectronics Unit Kolkata India Microsoft Corporation RedmondWA United States

ISBN: (纸本)9781665421041

Many real-life networks such as social networks, biological networks, citation networks etc., are temporally evolving by nature. In general, the evolution takes place gradually with time. But occasionally, the nodes may exhibit anomalous behavior that is to be detected and reported in real time. In this work, for anomaly detection in evolutionary networks, an action based approach is followed taking into account the network topology. The network is represented as a temporal stream of weighted graphs, where edge weights stand for frequency or power of actions. A new definition of anomaly score is introduced for nodes based on its action history. To reduce the search space, the community structure of the graph is exploited. It has been shown that only the nodes having multiple community membership are enough to detect anomaly in a temporally evolving network with overlapping community structure. To the best of our knowledge, this is the first work to exploit the overlapping community structure of an evolutionary network to identify the graph snapshots containing anomalous events. Experimental studies on both synthetic and real-world evolutionary networks show that the proposed technique achieves almost 16% improvement in F-Score compared to the state-of-the-art algorithms. Moreover, parallel implementation of the proposed technique results nearly 10× speedup making it suitable for real time computation of anomaly in evolutionary networks. © 2022 IEEE.

关键词： Anomaly detection

DCSK-based Waveform Design for Self-sustainable RIS-aided Noncoherent SWIPT

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Mukherjee, Priyadarshi Psomas, Constantinos Krikidis, Ioannis The Advanced Computing & Microelectronics Unit Indian Statistical Institute Kolkata India The Department of Electrical and Computer Engineering University of Cyprus Nicosia1678 Cyprus

This paper investigates the problem of transmit waveform design in the context of a chaotic signal-based self-sustainable reconfigurable intelligent surface (RIS)-aided system for simultaneous wireless information and power transfer (SWIPT). Specifically, we propose a differential chaos shift keying (DCSK)-based RIS-aided point-to-point set-up, where the RIS is partitioned into two non-overlapping surfaces. The elements of the first sub-surface perform energy harvesting (EH), which in turn, provide the required power to the other sub-surface operating in the information transfer (IT) mode. In this framework, by considering a generalized frequency-selective Nakagami-m fading scenario as well as the nonlinearities of the EH process, we derive closed-form analytical expressions for both the bit error rate (BER) at the receiver and the harvested power at the RIS. Our analysis demonstrates, that both these performance metrics depend on the parameters of the wireless channel, the transmit waveform design, and the number of reflecting elements at the RIS, which switch between the IT and EH modes, depending on the application requirements. Moreover, we show that, having more reflecting elements in the IT mode is not always beneficial and also, for a given acceptable BER, we derive a lower bound on the number of RIS elements that need to be operated in the EH mode. Furthermore, for a fixed RIS configuration, we investigate a trade-off between the achievable BER and the harvested power at the RIS and accordingly, we propose appropriate transmit waveform designs. Finally, our numerical results illustrate the importance of our intelligent DCSK-based waveform design on the considered framework. © 2024, CC BY-NC-ND.

关键词： Inductive power transmission

Exploring a Dynamic Ring Without Landmark 23rd

学校读者我要写书评

暂无评论

Exploring a Dynamic Ring Without Landmark

23rd International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2021

作者： Das, Archak Bose, Kaustav Sau, Buddhadeb Department of Mathematics Jadavpur University Kolkata India Advanced Computing and Microelectronics Unit Indian Statistical Institute Kolkata India

ISBN: (纸本)9783030910808

Consider a group of autonomous mobile computational entities, called agents, arbitrarily placed at some nodes of a dynamic but always connected ring. The agents neither have any knowledge about the size of the ring nor have a common notion of orientation. We consider the Exploration problem where the agents have to collaboratively explore the graph and terminate, with the requirement that each node has to be visited by at least one agent. It has been shown by Di Luna et al. [Distrib. Comput. 2020] that the problem is solvable by two anonymous agents if there is a single observably different node in the ring called landmark node. The problem is unsolvable by any number of anonymous agents in absence of a landmark node. We consider the problem with non-anonymous agents (agents with distinct identifiers) in a ring with no landmark node. The assumption of agents with distinct identifiers is strictly weaker than having a landmark node as the problem is unsolvable by two agents with distinct identifiers in absence of a landmark node. This setting has been recently studied by Mandal et al. [ALGOSENSORS 2020]. There it is shown that the problem is solvable in this setting by three agents assuming that they have edge crossing detection capability. Edge crossing detection capability is a strong assumption which enables two agents moving in opposite directions through an edge in the same round to detect each other and also exchange information. In this paper we give an algorithm that solves the problem with three agents without the edge crossing detection capability. © 2021, Springer Nature Switzerland AG.

关键词： Mobile agents

Synergy of machine learning with quantum computing and communication

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Bhoumik, Debasmita Sur-Kolay, Susmita Latesh Kumar, K.J. Iyengar, Sundaraja Sitharama Advanced Computing & Microelectronics Unit Indian Statistical Institute Kolkata India KFSCIS Florida International University MiamiFL United States

Machine learning in quantum computing and communication provides intensive opportunities for revolutionizing the field of Physics, Mathematics, and Computer Science. There exists an aperture of understanding behind this interdisciplinary domain and a lack of core understanding renders an opportunity to explore the machine learning techniques for this domain. This paper gives a comprehensive review of state-of-the-art approaches in quantum computing and quantum communication in the context of Artificial Intelligence and machine learning models. The paper reviews the classical ML models that have been employed in various ways for quantum computation such as quantum error correction, quantum communication, quantum cryptography, and mapping quantum algorithms to the existing hardware. The paper also illustrates how the relevant current challenges can be transformed into future research avenues. © 2023, CC BY.

关键词： Quantum communication

L(2, 1)-edge labeling of Infinite Triangular Grid 22

学校读者我要写书评

暂无评论

L(2, 1)-edge labeling of Infinite Triangular Grid

22nd Italian Conference on Theoretical Computer Science, ICTCS 2021

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

An L(h, k)-edge labeling of a graph G is the assignment of labels {0, 1, · · · , n} to the edges in such a way that two adjacent edges get labels with a difference at least h and the labels of distance two edges, i.e., two non-adjacent edges having a common edge connecting them get labels with a difference at least k, where h and k are two given non-negative integers. The span λ 0 h,k(G) is the minimum n such that G admits an L(h, k)-edge labeling. For three given integers n, h and k, an n-circular-L(h, k)-edge labeling f 0 of a graph G is an assignment from integers {0, 1, · · · , n1} in such a way that if two edges e and e 0 are adjacent then |f 0 (e) - f 0 (e 0 )|n ≥ h and if they are distance two edges then |f 0 (e) - f 0 (e 0 )|n ≥ k, where |x|n = min{x, n - x}. The circular span σ 0 h,k(G) is the minimum n such that G admits an n-circular L(h, k)-edge labeling. Here, we focus on finding λ 0 2,1(G) and σ 0 2,1(G) where G is infinite regular triangular grid T6. We work on the conjecture λ 0 2,1(T6) = 16 and the bound σ 0 2,1(T6) ≤ 18 given by Lin and Wu [J. Comb. Opt., 2013]. We prove the conjecture and give a labeling function for T6 such that σ 0 2,1(T6) ≤ 18 as no labeling function was given by Lin and Wu in this case. © 2021 CEUR-WS. All rights reserved.

关键词： Combinatorial optimization