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

1st International Conference on Networks and Communications

作者： Varatharajan, Sarvesh Ercal-Ozkaya, Gunes Univ Kansas Lawrence KS 66045 USA

ISBN: (纸本)9781424453641

We consider the problem of incentive compatible topology control for selfish all-to-one (reverse multicast) routing as modeled by a locally minimum cost forwarding game in [4], with new focus in this work on efficient local implementability in the absence of complete global information for realistic scenarios. In this work we consider a new locally computable heuristic "recommendation algorithm", which we refer to as localHeur for convenience. localHeur lies within the class of location based routing methods with particular similarity to the Nearest Forward Progress algorithm [7] though from the perspective of game-theoretic reverse multicast routing. We find that localHeur actually outperforms DeltaHeur of [4] in terms of global optimality in random Euclidean power instances which model wireless networks, though at the expense of loosening the Nash equilibrium condition. Nonetheless, we find that the relaxation of the Nash condition is strongly bounded in multiple ways, with high probability: The vast majority of players are provably playing a best response, while simulation results demonstrate that the average deviation ratio from a best response is within a decimal point of 1. Furthermore, the player deviating most from his best response is provably still within O(log n) of the cost of his best response, while simulation results support a much smaller maximum deviation from the best response.

关键词： sensor networks incentive compatible topology control game theory heuristics for NP-Hard problems location based routing local algorithm random Euclidean power graphs

来源：评论

学校读者我要写书评

暂无评论

local Construction of Connected and Plane Spanning Subgraphs under Acyclic Redundancy 18

Local Construction of Connected and Plane Spanning Subgraphs...

引用

18th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOPT)

作者： Boehmer, Steffen Boeltz, Lucas Frey, Hannes Univ Koblenz Landau Dept Comp Sci Koblenz Germany

ISBN: (纸本)9783903176294

Plane graphs play a major role for local routing and some other local network protocols in wireless communication. With such local algorithms each node requires information about its neighborhood only. It is assumed that nodes are deployed on the plane and each node knows its position in a given coordinate system. An arbitrary graph drawn on the plane can be transformed into a plane spanning subgraph by deleting edges. However, to assure connectivity at the same time some additional structural graph properties are required. Current graph classes that assure the existence of connected plane spanning subgraphs require assumptions, that are not very likely to hold for wireless network structures. In this work we develop the acyclic redundancy condition. This is a novel graph class with only one property that assures the existence of a connected plane spanning subgraph. Furthermore, we describe local algorithms that construct a connected plane spanning subgraph for graphs satisfying the acyclic redundancy condition. With numerical studies we confirm that the acyclic redundancy condition is a more realistic condition than existing graph classes that were required so far to construct connected plane spanning subgraphs.

关键词： plane subgraph local algorithm log-normal-shadowing stochastic analysis numerical evaluation

来源：评论

学校读者我要写书评

暂无评论

Thresholding random geometric graph properties motivated by ad hoc sensor networks

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2010年第7期76卷 686-696页

作者： Muthukrishnan, S. Pandurangan, Gopal Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA Rutgers State Univ Dept Comp Sci Piscataway NJ 08854 USA

We study the emerging phenomenon of ad hoc, sensor-based communication networks. The communication is modeled by the random geometric graph model G(n, r, l) where n points randomly placed within [0, l](d) form the nodes, and any two nodes that correspond to points at most distance r away from each other are connected. We study fundamental properties of G(n, r, l) of interest: connectivity, coverage, and routing-stretch. We use a technique that we call bin-covering that we apply uniformly to get (asymptotically) tight thresholds for each of these properties. Typically, in the past, random geometric graph analyses involved sophisticated methods from continuum percolation theory;on contrast, our bin-covering approach is discrete and very simple, yet it gives us tight threshold bounds. The technique also yields algorithmic benefits as illustrated by a simple local routing algorithm for finding paths with low stretch. Our specific results should also prove interesting to the sensor networking community that has seen a recent increase in the study of random geometric graphs motivated by engineering ad hoc networks. (C) 2010 Elsevier Inc. All rights reserved.

关键词： Random geometric graphs Thresholds Sensor network models local algorithm Coverage Stretch Connectivity

来源：评论

学校读者我要写书评

暂无评论

First steps to predicting pulp colour in whole melons using near-infrared reflectance spectroscopy

引用

BIOSYSTEMS ENGINEERING 2014年 123卷 12-18页

作者： Sanchez, Maria-Teresa Torres, Irina De la Haba, Maria-Jose Perez-Marin, Dolores Univ Cordoba Dept Bromatol & Food Technol E-14071 Cordoba Spain Univ Cordoba Dept Anim Prod E-14071 Cordoba Spain

Near-infrared reflectance spectroscopy (NIRS) technology was used for the non-destructive measurement of melon-pulp colour (a*, b*, C* and h*), one of the main indicators of ripeness and quality. A total of 432 Cantaloupe and Galia melons were used in the construction of calibration models, testing various spectral signal pretreatments and both linear and nonlinear regression algorithms. The coefficient of determination (r(2)) and the standard error of cross-validation (SECV) obtained for parameters a* (0.96, 2.16), b* (0.85, 3.25), C* (0.82, 3.76) and h* (0.96, 3.64) in intact fruit confirmed the a priori viability of NIRS technology with modified partial least squares (MPLS) regression for measuring melon ripeness and quality. Moreover, the application of a local algorithm improved the ability of models to predict all the internal-colour quality parameters studied. These results suggest that NIRS technology is a promising tool for monitoring ripening in melons and thus for establishing the optimal harvesting time. (C) 2014 IAgrE. Published by Elsevier Ltd. All rights reserved.

关键词： Near-infrared spectroscopy Melon Internal colour MPLS regression local algorithm

来源：评论

学校读者我要写书评

暂无评论

Optimal deterministic distributed algorithms for maximal independent set in geometric graphs

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2019年 132卷 36-47页

作者： Molla, Anisur Rahaman Pandit, Supantha Roy, Sasanka Indian Stat Inst Comp & Commun Sci Div 203 BT Rd Kolkata 700108 India Dhirubhai Ambani Inst Informat & Commun Technol Gandhinagar 382007 Gujrat India Indian Stat Inst Adv Comp & Microelect Unit 203 BT Rd Kolkata 700108 India Indian Stat Inst Kolkata India

Finding a maximal independent set (MIS) in a graph is one of the fundamental problems in distributed computing. Researchers in this community are trying to close the time complexity gap of computing a MIS in a graph, way back from Luby's [STOC'85] O(logn) time (randomized) algorithm and Linial's [SICOMP'92] Omega(log* n) lower bound result (n is the number of nodes of the graph). Since then, an extensive research has been done on this problem, however, most of the results are randomized and we are lack of efficient deterministic solution. In fact, no polylogarithmic (in n) time deterministic algorithm is known so far in general graphs an open question raised by Linial in 1993 [Comb. Probab. Comput.'93]. In this paper, we study the MIS problem in geometric graphs, a class of graphs which has both theoretical and practical importance. We present O(1)-time deterministic algorithms (hence, optimal) for computing MIS in unit interval graphs, unit square graphs and unit disk graphs. The same idea applies to develop optimal MIS algorithm for higher dimensional unit balls and unit hypercubes. We further extend the MIS algorithms to compute approximate maximum independent set (MaxIS) in the above geometric graph classes. The theoretical results are corroborated through extensive experiments to show the effectiveness and efficiency of our algorithms. Our algorithms are fully decentralized, scalable, and robust. In general, nodes exchange only O(log n) bits message through an edge per communication. Moreover, being local, our algorithms are also suitable in failure model, self-stabilizing and appropriate for dynamic environment. (C) 2019 Elsevier Inc. All rights reserved.

关键词： Distributed algorithm Maximal and maximum independent set local algorithm Unit interval graphs Geometric graphs

来源：评论

学校读者我要写书评

暂无评论

Curve length estimation based on cubic spline interpolation in gray-scale images

引用

Journal of Zhejiang University-Science C(Computers and Electronics) 2013年第10期14卷 777-784页

作者： Zhen-xin WANG Ji-hong OUYANG College of Computer Science and Technology Jilin University MOE Key Laboratory of Symbolic Computation and Knowledge Engineering Jilin University

This paper deals with a novel local arc length estimator for curves in gray-scale *** method first estimates a cubic spline curve fit for the boundary points using the gray-level information of the nearby pixels,and then computes the sum of the spline segments’*** this model,the second derivatives and y coordinates at the knots are required in the computation;the spline polynomial coefficients need not be computed *** provide the algorithm pseudo code for estimation and preprocessing,both taking linear *** shows that the proposed model gains a smaller relative error than other state-of-the-art methods.

关键词： Arc length estimation Cubic spline interpolation Gray-scale image local algorithm

来源：评论

学校读者我要写书评

暂无评论

Non-destructive characterization and quality control of intact strawberries based on NIR spectral data

引用

JOURNAL OF FOOD ENGINEERING 2012年第1期110卷 102-108页

作者： Sanchez, Maria-Teresa Jose De la Haba, M. Benitez-Lopez, Miriam Fernandez-Novales, Juan Garrido-Varo, Ana Perez-Marin, Dolores Univ Cordoba Dept Bromatol & Food Technol E-14071 Cordoba Spain Univ Cordoba Dept Anim Prod E-14071 Cordoba Spain

External and internal quality parameters of strawberries (Fragaria x ananassa Duch.) were studied at harvest and during postharvest refrigerated storage using a handheld micro-electro-mechanical system (MEMS) near-infrared spectrophotometer. A total of 189 strawberry punnets were used to develop calibration models using various spectral signal pretreatments and linear and non-linear regression algorithms: the sampling unit for both NIRS analysis and reference methods comprised 5 strawberries from each punnet. Modified partial least squares analysis confirmed the feasibility of NIRS for predicting color-related external quality parameters (L*, a* and C*) as well as firmness, soluble solid content and titratable acidity. For other tested parameters (b*, h* and pH), the results suggested that NIRS prediction was not feasible. However, the application of a local algorithm considerably improved the ability of models to predict all the internal quality parameters studied. Use of the local algorithm proved valuable in minimizing the error in NIRS models for predicting complex internal quality parameters, mainly those related to texture and acidity. Subsequently, the ability of NIR technology to classify individual strawberries as a function of variety was tested using partial least squares discriminant analysis (PLS-DA), which yielded percentages of correctly classified samples (ratio of correctly classified samples to total samples) ranging from 57% for the Camarosa variety to 78% for Antilla Fnm. (C) 2011 Elsevier Ltd. All rights reserved.

关键词： Handheld NIRS instrument MEMS technology Strawberry Variety Quality parameters local algorithm

来源：评论

学校读者我要写书评

暂无评论

An optimal maximal independent set algorithm for bounded-independence graphs

引用

DISTRIBUTED COMPUTING 2010年第5-6期22卷 349-361页

作者： Schneider, Johannes Wattenhofer, Roger Swiss Fed Inst Technol Comp Engn & Networks Lab CH-8092 Zurich Switzerland

We present a novel distributed algorithm for the maximal independent set problem (This is an extended journal version of Schneider and Wattenhofer in Twenty-seventh annual ACM SIGACT-SIGOPS symposium on principles of distributed computing, 2008). On bounded-independence graphs our deterministic algorithm finishes in O(log* n) time, n being the number of nodes. In light of Linial's Omega(log* n) lower bound our algorithm is asymptotically optimal. Furthermore, it solves the connected dominating set problem for unit disk graphs in O(log* n) time, exponentially faster than the state-of-the-art algorithm. With a new extension our algorithm also computes a delta + 1 coloring and a maximal matching in O(log* n) time, where delta is the maximum degree of the graph.

关键词： Ad Hoc network Sensor network Radio network Unit disk graph Growth bounded graph Bounded-independence graph local algorithm Parallel algorithm Maximal independent set Maximal matching Dominating set Connected Dominating Set Coloring Symmetry breaking

来源：评论

学校读者我要写书评

暂无评论

Constant memory routing in quasi-planar and quasi-polyhedral graphs

引用

DISCRETE APPLIED MATHEMATICS 2008年第18期156卷 3430-3442页

作者： Kranakis, Evangelos Mott, Tim Stacho, Ladislav Simon Fraser Univ Dept Math Burnaby BC V5A 1S6 Canada Carleton Univ Sch Comp Sci Ottawa ON K1S 5B6 Canada

We address the problem of online route discovery for it class of graphs that call be embedded either in two or in three-dimensional space. In two dimensions we propose the class of quasi-planar graphs and in three dimensions the class of quasi-polyhedral graphs. In the former case such graphs are geometrically embedded in R-2 and have an underlying backbone that is planar with convex faces;however within each face arbitrary edges (with arbitrary crossings) are allowed. In the latter case, these graphs are geometrically embedded in R-3 and consist of a backbone of convex polyhedra and arbitrary edges within each polyhedron. In both cases we provide a routing algorithm that guarantees delivery. Our algorithms need only "remember" the source and destination nodes and one (respectively, two) reference nodes used to store information about the underlying face (respectively, polyhedron) currently being traversed. The existence of the backbone is used only in proof's of correctness of the routine algorithm;the particular choice is irrelevant and does not affect the behaviour of the algorithm. Crown Copyright (C) 2008 Published by Elsevier B.V. All rights reserved.

关键词： Ad hoc network Routing Planar graph local algorithm

来源：评论

学校读者我要写书评

暂无评论

ON THE localITY OF NASH-WILLIAMS FOREST DECOMPOSITION AND STAR-FOREST DECOMPOSITION

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2023年第2期37卷 800-830页

作者： Harris, David G. Su, Hsin-Hao Vu, Hoa T. Univ Maryland Dept Comp Sci Silver Spring MD 20901 USA Boston Coll Dept Comp Sci Chestnut Hill MA 02467 USA San Diego State Univ Dept Comp Sci San Diego CA 92182 USA

Given a graph G = (V, E) with arboricity a, we study the problem of decomposing the edges of G into (1+\varepsilon)a disjoint forests in the distributed local model. Here G may be a simple graph or multigraph. While there is a polynomial time centralized algorithm for a-forest decomposition (e.g., [H. Imai, J. Oper. Res. Soc. Japan, 26 (1983), pp. 186-211]), it remains an open question how close we can get to this exact decomposition in the local model. Barenboim and Elkin [L. Barenboim and M. Elkin, Sublogarithmic distributed MIS algorithm for sparse graphs using Nash Williams decomposition, Distrib. Comput., 22 (2010), pp. 363--379] developed a local algorithm to compute a (2+\varepsilon)a-forest decomposition in O(log n \varepsilon ) rounds. Ghaffari and Su [Proc. 28th ACM-SIAM Symposium on Discrete algorithms, 2017, pp. 2505--2523] made further progress by computing a (1 + \varepsilon)a-forest decomposition in O(log3 n \varepsilon4) rounds when \varepsilon a = S2(\surda log n);i.e., the limit of their algorithm is an (a + S2 (\surda log n))-forest decomposition. This algorithm, based on a combinatorial construction of Alon, McDiarmid, and Reed [Combinatorica, 12 (1992), pp. 375--380], in fact provides a decomposition of the graph into star-forests, i.e., each forest is a collection of stars. Our main goal is to reduce the threshold of \varepsilon a in (1 +\varepsilon)a-forest decomposition. We obtain a number of results with different parameters;some notable examples are the following: (1) An O( & DBLBOND;\rho log4 n \varepsilon )-round algorithm when \varepsilon a = S2\rho(1) in multigraphs, where \rho > 0 is any arbitrary constant;(2) an O(log4 n log & DBLBOND;\varepsilon )round algorithm when \varepsilon a = S2( log & DBLBOND;log log & DBLBOND;) in multigraphs;(3) an O(log4\varepsilon n )-round algorithm when \varepsilon a = S2(logn) in multigraphs (this also covers an extension of the forest-decomposition problem to list-edge coloring);(4) an O( log3 n \vare

关键词： arboricity local algorithm star-arboricity forest decomposition

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：