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

Channel-Oblivious counting algorithms for Large-Scale RFID Systems

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2015年第12期26卷 3303-3316页

作者： Sze, Wai Kit Deng, Yulin Lau, Wing Cheong Kodialam, Murali Nandagopal, Thyaga Yue, Onching SUNY Stony Brook Stony Brook NY 11794 USA Chinese Univ Hong Kong Dept Informat Engn Shatin Hong Kong Peoples R China Bell Labs Res Holmdel NJ 07733 USA Bell Labs Alcatel Lucent Technol Murray Hill NJ 07974 USA

Scalable, low-latency and accurate RFID counting algorithms have recently been proposed as a fundamental building block to support more complex query operations in a large-scale RFID system. One distinct feature of these algorithms is that they do not require explicit identification of individual tags and therefore can eliminate the latency bottleneck caused by serialization during multiple access control. However, these algorithms all assume reliable communications between the reader and the tags. While this assumption is also adopted by many tag-identification protocols in the current RFID standards, it is practically unachievable given the current technology and low-cost requirement of RFID tags. In fact, recent empirical studies have found that the communication between an RFID reader and a set of seemingly "in-range" tags are still unreliable and highly non-deterministic due to the varying channel conditions. In this paper, we discuss the design and performance analysis of a set of channel-oblivious RFID counting algorithms which can estimate the size of a tag-set of interest over unreliable wireless channels. The proposed schemes can provide accurate cardinality estimates without any prior knowledge of the channel parameters. We first propose a series of algorithms and analyze their performance under a simplified memoryless lossy channel model. We then extend them to handle the impact due to backscattering effects and correlated losses found in practical RFID systems. Our proposed designs only require simple modifications to standard RFID tags and readers and can be implemented using current technologies with minimal increase in tag/reader cost. Our designs can also be extended to other RFID counting algorithms which assumed reliable communication channels.

关键词： RFID counting algorithms wireless channel modeling time-correlated packet loss

来源：评论

学校读者我要写书评

暂无评论

counting triangulations and other crossing-free structures approximately

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2015年第5期48卷 386-397页

作者： Alvarez, Victor Bringmann, Karl Ray, Saurabh Seidel, Raimund Univ Saarland Informat Syst Grp Saarbrucken Germany Ben Gurion Univ Negev IL-84105 Beer Sheva Israel Univ Saarland Fachrichtung Informat Saarbrucken Germany

We consider the problem of counting straight-edge triangulations of a given set P of n points in the plane. Until very recently it was not known whether the exact number of triangulations of P can be computed asymptotically faster than by enumerating all triangulations. We now know that the number of triangulations of P can be computed in 0*(2(n)) time [9], which is less than the lower bound of Omega(2.43(n)) on the number of triangulations of any point set [30]. In this paper we address the question of whether one can approximately count triangulations in sub-exponential time. We present an algorithm with sub-exponential running time and sub-exponential approximation ratio, that is, denoting by Lambda the output of our algorithm and by c(n) the exact number of triangulations of P, for some positive constant c, we prove that c(n) <= Lambda <= c(n) . 2(0(n)). This is the first algorithm that in sub-exponential time computes a (1+ o(1))-approximation of the base of the number of triangulations, more precisely, c <= Lambda(1/n) <= (1 + o(1))c. Our algorithm can be adapted to approximately count other crossing-free structures on P, keeping the quality of approximation and running time intact. In this paper we show how to do this for matchings and spanning trees. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Algorithmic geometry Crossing-free structures counting algorithms Triangulations Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

A numerical algorithm for zero counting, I: Complexity and accuracy

引用

JOURNAL OF COMPLEXITY 2008年第5-6期24卷 582-605页

作者： Cucker, Felipe Krick, Teresa Malajovich, Gregorio Wschebor, Mario City Univ Hong Kong Dept Math Hong Kong Hong Kong Peoples R China Univ Buenos Aires Dept Matemat RA-1053 Buenos Aires DF Argentina Consejo Nacl Invest Cient & Tecn RA-1033 Buenos Aires DF Argentina Univ Fed Rio de Janeiro Dept Matemat Aplicada BR-21941 Rio De Janeiro Brazil Univ Republica Ctr Matemat Montevideo Uruguay

We describe an algorithm to count the number of distinct real zeros of a polynomial (square) system f. The algorithm performs O(log(nDk(f))) iterations (grid refinements) where n is the number of polynomials (as well as the dimension of the ambient space), D is a bound on the polynomials' degree, and k(f) is a condition number for the system. Each iteration uses an exponential number of operations. The algorithm uses finite-precision arithmetic and a major feature of our results is a bound for the precision required to ensure that the returned output is correct which is polynomial in n and D and logarithmic in k(f). The algorithm parallelizes well in the sense that each iteration can be computed in parallel polynomial time in n, log D and log(k(f)). (C) 2008 Elsevier Inc. All rights reserved.

关键词： counting algorithms Polynomial systems Finite precision

来源：评论

学校读者我要写书评

暂无评论

counting Triangulations and Other Crossing-Free Structures via Onion Layers

引用

DISCRETE & COMPUTATIONAL GEOMETRY 2015年第4期53卷 675-690页

作者： Alvarez, Victor Bringmann, Karl Curticapean, Radu Ray, Saurabh Univ Saarland Fachbereich Informat D-81310 Saarbrucken Germany Swiss Fed Inst Technol Inst Theoret Comp Sci Zurich Switzerland Max Planck Inst Informat D-66123 Saarbrucken Germany

Let be a set of points in the plane. A crossing-free structure on is a straight-edge plane graph with vertex set . Examples of crossing-free structures include triangulations and spanning cycles, also known as polygonalizations. In recent years, there has been a large amount of research trying to bound the number of such structures;in particular, bounding the number of (crossing-free) triangulations spanned by has received considerable attention. It is currently known that every set of points has at most O and at least triangulations. However, much less is known about the algorithmic problem of counting crossing-free structures of a given set . In this paper, we develop a general technique for computing the number of crossing-free structures of an input set . We apply the technique to obtain algorithms for computing the number of triangulations, matchings, and spanning cycles of . The running time of our algorithms is upper-bounded by , where is the number of onion layers of . In particular, for our algorithms run in polynomial time. Additionally, we show that our algorithm for counting triangulations in the worst case over all takes time O. [In the notations , and , we neglect polynomial terms and we just present the dominating exponential term.] Given that there are several well-studied configurations of points with at least triangulations, and some even with triangulations, our algorithm asymptotically outperforms any enumeration algorithm for such instances. We also show that our techniques are general enough to solve the Restricted-Triangulation-counting-Problem, which we prove to be -hard in the parameter . This implies that in order to be fixed-parameter tractable, our general algorithm must rely on additional properties that are specific to the considered class of crossing-free structures.

关键词： Triangulations Crossing-free structures Algorithmic geometry counting algorithms Matchings Spanning cycles Spanning trees

来源：评论

学校读者我要写书评

暂无评论

counting NUMERICAL SEMIGROUPS WITH SHORT GENERATING FUNCTIONS

引用

INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION 2011年第7期21卷 1217-1235页

作者： Blanco, Victor Garcia-Sanchez, Pedro A. Univ Granada Dept Algebra E-18071 Granada Spain

This paper presents a new methodology to compute the number of numerical semigroups of given genus or Frobenius number. We apply generating function tools to the bounded polyhedron that classifies the semigroups with given genus (or Frobenius number) and multiplicity. First, we give theoretical results about the polynomial-time complexity of counting these semigroups. We also illustrate the methodology analyzing the cases of multiplicity 3 and 4 where some formulas for the number of numerical semigroups for any genus and Frobenius number are obtained.

关键词： Numerical semigroups generating functions counting algorithms

来源：评论

学校读者我要写书评

暂无评论

Conscious and Unconscious counting on Anonymous Dynamic Networks

Conscious and Unconscious Counting on Anonymous Dynamic Netw...

引用

15th International Conference on Distributed Computing and Networking (ICDCN)

作者： Di Luna, Giuseppe Antonio Baldoni, Roberto Bonomi, Silvia Chatzigiannakis, Ioannis Univ Roma La Sapienza Cyber Intelligence & Informat Secur Res Ctr Piazzale Aldo Moro 5 I-00185 Rome Italy CTI Patras Greece

ISBN: (纸本)9783642452482;9783642452499

This paper addresses the problem of counting the size of a network where (i) processes have the same identifiers (anonymous nodes) and (ii) the network topology constantly changes (dynamic network). Changes are driven by a powerful adversary that can look at internal process states and add and remove edges in order to contrast the convergence of the algorithm to the correct count. The paper proposes two leader-based counting algorithms. Such algorithms are based on a technique that mimics an energy-transfer between network nodes. The first algorithm assumes that the adversary cannot generate either disconnected network graphs or network graphs where nodes have degree greater than D. In such algorithm, the leader can count the size of the network and detect the counting termination in a finite time (i. e., conscious counting algorithm). The second algorithm assumes that the adversary only keeps the network graph connected at any time and we prove that the leader can still converge to a correct count in a finite number of rounds, but it is not conscious when this convergence happens.

关键词： Anonymous Networks Dynamic Networks counting algorithms Dynamic Graph Adversary

来源：评论

学校读者我要写书评

暂无评论

counting Polyominoes, Revisited

Counting Polyominoes, Revisited

引用

Symposium on Algorithm Engineering and Experiments (ALENEX)

作者： Barequet, Gill Ben-Shachar, Gil Techion Israel Inst Technol Dept Comp Sci Haifa Israel

ISBN: (纸本)9781611977929

A polyomino is an edge-connected set of squares on the square lattice. In this paper, we improve Jensen's algorithm for counting polyominoes by considering bounding boxes on the square lattice rotated by 45 degrees instead of on the regular unrotated lattice. This allows us to extend significantly the count of polyominoes from 56 to 70 terms.

关键词： Polyominoes lattice animals counting algorithms

来源：评论

学校读者我要写书评

暂无评论

Tighter Bounds and Optimal algorithms for All Maximal α-gapped Repeats and Palindromes

引用

THEORY OF COMPUTING SYSTEMS 2018年第1期62卷 162-191页

作者： Gawrychowski, Pawel Tomohiro, I Inenaga, Shunsuke Koeppl, Dominik Manea, Florin Univ Warsaw Inst Informat Warsaw Poland Kyushu Inst Technol Dept Artificial Intelligence Fukuoka Japan Kyushu Univ Dept Informat Fukuoka Japan TU Dortmund Dept Comp Sci Dortmund Germany Univ Kiel Dept Comp Sci Kiel Germany

An alpha-gapped repeat (alpha >= 1) in a word w is a factor uvu of w such that |uv| <= alpha|u|;the two occurrences of u are called arms of this alpha-gapped repeat. An alpha-gapped repeat is called maximal if its arms cannot be extended simultaneously with the same character to the right nor to the left. We show that the number of all maximal alpha-gapped repeats occurring in words of length n is upper bounded by 18 alpha n. In the case of alpha-gapped palindromes, i.e., factors uvu(t) with |uv| <=alpha|u|, we show that the number of all maximal alpha-gapped palindromes occurring in words of length n is upper bounded by 28 alpha n + 7n. Both upper bounds allow us to construct algorithms finding all maximal alpha-gapped repeats and/or all maximal alpha-gapped palindromes of a word of length n on an integer alphabet of size n(O(1)) in O(alpha N)time. The presented running times are optimal since there are words that have Theta(alpha n) maximal alpha-gapped repeats/palindromes.

关键词： Combinatorics on words counting algorithms

来源：评论

学校读者我要写书评

暂无评论

ON COMPUTING THE FREQUENCIES OF INDUCED SUBHYPERGRAPHS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2010年第1期24卷 322-329页

作者： Nagle, Brendan Univ S Florida Dept Math & Stat Tampa FL 33620 USA

Let F be an r-uniform hypergraph with f vertices, where f > r >= 3. In [Inform. Process. Lett., 99 (2006), pp. 130-134], Yuster posed the problem of whether there exists an algorithm which, for a given r-uniform hypergraph H with n vertices, computes the number of induced copies of F in H in time o(n(f)). The analogous question for graphs (r = 2) was known to hold from an O(n(f-epsilon)) time algorithm of Nesetril and Poljak [Comment. Math. Univ. Carolin., 26 (1985), pp. 415-419] (for a constant epsilon = epsilon(f) > 0 which is independent of n). Here, we present an algorithm for this problem, when r >= 3, with running time O(n(f)/log(2) n).

关键词： hypergraphs counting algorithms induced containment

来源：评论

学校读者我要写书评

暂无评论

On Independent Sets and Bicliques in Graphs

引用

ALGORITHMICA 2012年第3-4期62卷 637-658页

作者： Gaspers, Serge Kratsch, Dieter Liedloff, Mathieu Vienna Univ Technol Inst Informat Syst A-1040 Vienna Austria Univ Paul Verlaine Metz LITA F-57045 Metz 01 France Univ Orleans LIFO F-45067 Orleans 2 France

Bicliques of graphs have been studied extensively, partially motivated by the large number of applications. In this paper we improve Prisner's upper bound on the number of maximal bicliques (Combinatorica, 20, 109-117, 2000) and show that the maximum number of maximal bicliques in a graph on n vertices is I similar to(3 (n/3)). Our major contribution is an exact exponential-time algorithm. This branching algorithm computes the number of distinct maximal independent sets in a graph in time O(1.3642 (n) ), where n is the number of vertices of the input graph. We use this counting algorithm and previously known algorithms for various other problems related to independent sets to derive algorithms for problems related to bicliques via polynomial-time reductions.

关键词： counting algorithms Combinatorial bound Maximal bicliques Maximal independent sets Exact exponential time algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：