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

Almost Empty Monochromatic Triangles in Planar Point Sets

Electronic Notes in Discrete Mathematics 2013年 44卷 53-59页

作者： Basu, Deepan Bhattacharya, Bhaswar B. Das, Sandip Indian Statistical Institute Kolkata India Department of Statistics Stanford University California United States Advanced Computing and Microelectronics Unit Indian Statistical Institute Kolkata India

For positive integers c, s≥1, let M3(c, s) be the smallest integer such that any set of at least M3(c, s) points in the plane, no three on a line, and colored with c colors, contains a monochromatic triangle with at ... 详细信息

For positive integers c, s≥1, let M₃(c, s) be the smallest integer such that any set of at least M₃(c, s) points in the plane, no three on a line, and colored with c colors, contains a monochromatic triangle with at most s interior points. The case s=0, which corresponds to empty monochromatic triangles, has been studied extensively over the last few years. In particular, it is known that M₃(1, 0)=3, M₃(2, 0)=9 and M₃(c, 0)=∞, for c≥3. In this paper, we prove that the smallest integer λ₃(c) such that M₃(c, λ₃(c))<∞ is bounded above by c-2. We show this by proving M₃(c, c-2)≤(c+1)², for c≥2. We also determine the exact values of M₃(c, s) for small values of c and s. © 2013 Elsevier B.V.

关键词： Combinatorial convexity Discrete geometry Empty polygons Erdos-Szekeres theorem

来源：评论

学校读者我要写书评

暂无评论

A Study on the Problems of Dispersion and Exploration on Graph Topology 22

A Study on the Problems of Dispersion and Exploration on Gra...

引用

23rd International Conference on Distributed computing and Networking, ICDCN 2022

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

ISBN: (纸本)9781450395601

In this paper we discuss two important problems: Dispersion and Exploration. We have provided two optimal algorithms for each of them. For Dispersion we have provided an algorithm which is optimal in terms of memory complexity and for Exploration we have given an algorithm which is optimal in terms of number of robots in a dynamic ring. We give a brief idea about our algorithms and novelty of our techniques. © 2022 ACM.

关键词： Topology

来源：评论

学校读者我要写书评

暂无评论

Message Complexity of Multi-Valued Implicit Agreement with Shared Random Bits 22

Message Complexity of Multi-Valued Implicit Agreement with S...

引用

23rd International Conference on Distributed computing and Networking, ICDCN 2022

作者： Bose, Kaustav Molla, Anisur Rahaman Advanced Computing and Microelectronics Unit Indian Statistical Institute India R. C. Bose Centre for Cryptology and Security Indian Statistical Institute India

ISBN: (纸本)9781450395601

An agreement protocol enables a system of n nodes in a distributed network to agree on a common input value. In the implicit version of the problem, only a subset of the nodes are required to decide the common value. This paper focuses on the message complexity of randomized implicit agreement in synchronous distributed networks. It has been shown by Augustine et al. [PODC 2018] that if the nodes have access to a shared coin, then implicit agreement can be solved with high probability1 using messages2 in expectation. However, their algorithm works only for binary input values, i.e, the input values given to the nodes are from the set {0, 1}. In this paper, we extended the result to the multi-valued setting where the input values may come from a larger but constant sized domain. We present an algorithm that solves the multi-valued implicit agreement problem with matching performance guarantees as in binary agreement. © 2022 ACM.

关键词： Parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Approximation algorithms for deployment of sensors for line segment coverage in wireless sensor networks

Approximation algorithms for deployment of sensors for line ...

引用

2012 4th International Conference on Communication Systems and Networks, COMSNETS 2012

作者： Dash, Dinesh Bishnu, Arijit Gupta, Arobinda Nandy, Subhas C. Department of Computer Science and Engineering Indian Institute of Technology Kharagpur India Advanced Computing and Microelectronics Unit Indian Statistical Institute India

ISBN: (纸本)9781467302982

The coverage problem in wireless sensor network deals with the problem of covering a region or parts of it with sensors. In this paper, we address the problem of covering a set of line segments with minimum number of sensors. A line segment is said to be 1-covered if it intersects the sensing region of at least one among the sensors distributed in a bounded rectangular region R. We assume that the sensing radius of each sensor is uniform. The problem of finding the minimum number of sensors needed to 1-cover each member in a given set of line segments in R is NP-hard. We propose two constant factor approximation algorithms and a PTAS (Polynomial Time Approximation Scheme) for the problem for 1-covering a set of axis-parallel line segments. We also show that a PTAS exists for 1-covering a set of arbitrarily oriented line segments in R where the length of the line segments are bounded within a constant factor of the sensing radius of each sensor. © 2012 IEEE.

关键词： Wireless sensor networks

来源：评论

学校读者我要写书评

暂无评论

One-round discrete voronoi game in R2 in presence of existing facilities 25

One-round discrete voronoi game in R2 in presence of existin...

引用

25th Canadian Conference on Computational Geometry, CCCG 2013

作者： Banik, Aritra Bhattacharya, Bhaswar B. Das, Sandip Mukherjee, Satyaki Advanced Computing and Microelectronics Unit Indian Statistical Institute Kolkata India Department of Statistics Stanford University United States Indian Statistical Institute Bangalore India

In this paper we consider a simplified variant of the discrete Voronoi Game in R2, which is also of independent interest in competitive facility location. The game consists of two players P1 and P2, and a finite set U of users in the plane. The players have already placed two sets of facilities F and S, respectively in the plane. The game begins by P1 placing a new facility followed by P2 placing another facility, and the objective of both the players is to maximize their own total payoffs. When |F| = |S| = m, this corresponds to the last round of the (m + 1)-round discrete Voronoi Game in R2. In this paper we propose polynomial time algorithms for obtaining optimal strategies of both the players under arbitrary locations of the existing facilities F and S. We show that the optimal strategy of P2, given any placement of P1, can be found in O(n2) time, and the optimal strategy of P1 can be found in O(n8) time.

关键词： Polynomial approximation

来源：评论

学校读者我要写书评

暂无评论

Self-stabilizing checkpointing algorithm in ring topology 1

引用

7th International Workshop on Distributed computing, IWDC 2005

作者： Mandal, Partha Sarathi Mukhopadhyaya, Krishnendu Advanced Computing and Microelectronics Unit Indian Statistical Institute 203 B T Road Kolkata 700108 India

ISBN: (数字)9783540324287

ISBN: (纸本)3540309594

If the variables used for a checkpointing algorithm have data faults, the algorithm may fail. In this paper, a self-stabilizing checkpointing algorithm is proposed for handling data faults in a ring network. The proposed algorithm can deal with concurrent initiations of checkpointing and at most one data fault per process. However, several processes may be faulty. © Springer-Verlag Berlin Heidelberg 2005.

关键词： Algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Distributed Pattern Formation by Autonomous Robot Swarm 22

Distributed Pattern Formation by Autonomous Robot Swarm

引用

23rd International Conference on Distributed computing and Networking, ICDCN 2022

作者： Bose, Kaustav Adhikary, Ranendu Kundu, Manash Kumar Das, Archak Sau, Buddhadeb Advanced Computing and Microelectronics Unit Indian Statistical Institute India Jadavpur University India Gayeshpur Government Polytechnic India

ISBN: (纸本)9781450395601

Arbitrary Pattern Formation is a fundamental robot coordination problem. The problem asks for a distributed algorithm that allows a swarm of autonomous mobile robots to form any pattern given as input. The majority of the works in the literature investigate the problem under models with very idealistic assumptions regarding motion and sensing capabilities of the robots. We investigate the problem, aiming towards removing these assumptions and understanding their effect on the solvability of the problem. © 2022 ACM.

关键词： Robots

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Fast FPGA placement using space-filling curve

Fast FPGA placement using space-filling curve

引用

2005 International Conference on Field Programmable Logic and Applications, FPL

作者： Banerjee, Pritha Bhattacharjee, Subhasis Sur-Kolay, Susmita Das, Sandip Nandy, Subhas C. Advanced Computing and Microelectronics Unit Indian Statistical Institute 203 B. T. Road Kolkata India

ISBN: (纸本)0780393627

In this paper, we propose a placement method for island-style FPGAs, based on recursive bi-partitioning followed by application of space-filling curves. Experimental results of our method show 55% improvement in cost, when compared to random initial placement of the popular tool VPR. The solutions thus obtained require 44.5% fewer moves during final iterative refinement by ultra-low temperature simulated annealing, whereas the quality of solution is on the average 0.1% better. This establishes the utility of the method for fast reconfiguration of FPGA based co-processors. © 2005 IEEE.

关键词： Field programmable gate arrays

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：