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

local FLOW PARTITIONING FOR FASTER EDGE CONNECTIVITY

SIAM JOURNAL ON COMPUTING 2020年第1期49卷 1-36页

作者： Henzinger, Monika Rao, Satish Wang, Di Univ Vienna A-1090 Vienna Austria Univ Calif Berkeley Comp Sci Div Berkeley CA 94720 USA Georgia Inst Technol Atlanta GA 30332 USA

We study the problem of computing a minimum cut in a simple, undirected graph and give a deterministic O(m log(2) n log log(2) n) time algorithm. This improves on both the best previously known deterministic running time of O(m log(12) n) (Kawarabayashi and Thorup [J. ACM, 66 (2018), 41) and the best previously known randomized running time of O(m log(3) n) (Karger [J. ACM, 47 (2000), pp. 46-761) for this problem, though Karger's algorithm can be further applied to weighted graphs. Moreover, our result extends to balanced directed graphs, where the balance of a directed graph captures how close the graph is to being Eulerian. Our approach is using the Kawarabayashi and Thorup graph compression technique, which repeatedly finds low conductance cuts. To find these cuts they use a diffusion-based local algorithm. We use instead a flow-based local algorithm and suitably adjust their framework to work with our flow-based subroutine. Both flow-and diffusion-based methods have a long history of being applied to finding low conductance cuts. Diffusion algorithms have several variants that are naturally local, while it is more complicated to make flow methods local. Some prior work has proven nice properties for local flow-based algorithms with respect to improving or cleaning up low conductance cuts. Our flow subroutine, however, is the first that both is local and produces low conductance cuts. Thus, it may be of independent interest.

关键词： min cut graph algorithm deterministic algorithm flow edge connectivity local algorithm

来源：评论

学校读者我要写书评

暂无评论

local edge colouring of Yao-like subgraphs of Unit Disk Graphs

引用

THEORETICAL COMPUTER SCIENCE 2009年第14期410卷 1388-1400页

作者： Czyzowicz, J. Dobrev, S. Kranakis, E. Opatrny, J. Urrutia, J. Carleton Univ Sch Comp Sci Ottawa ON K1S 5B6 Canada Univ Quebec Outaouais Dept Informat Gatineau PQ J8X 3X7 Canada Univ Ottawa Sch Informat Technol & Engn Ottawa ON K1N 6N5 Canada Concordia Univ Dept Comp Sci Montreal PQ H3G 1M8 Canada Univ Nacl Autonoma Mexico Inst Matemat Area Invest Cientifica Mexico City 04510 DF Mexico

The focus of the present paper is on providing a local deterministic algorithm for colouring the edges of Yao-like subgraphs of Unit Disk Graphs. These are geometric graphs such that for some positive integers l, k the following property holds at each node nu: if we partition the unit circle centered at nu into 2k equally sized wedges then each wedge can contain at most I points different from nu. We assume that the nodes are location aware, i.e. they know their Cartesian coordinates in the plane. The algorithm presented is local in the sense that each node can receive information emanating only from nodes which are at most a constant (depending on k and l, but not on the size of the graph) number of hops (measured in the original underlying Unit Disk Graph) away from it, and hence the algorithm terminates in a constant number of steps. The number of colours used is 2kl + 1 and this is optimal for local algorithms (since the maximal degree is 2kl and a colouring with 2kl colours can only be constructed by a global algorithm), thus showing that in this class of graphs the price for locality is only one additional colour. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Edge colouring Geometric graphs Unit Disk Graphs local algorithm Location awareness Wedge Wireless network

来源：评论

学校读者我要写书评

暂无评论

local Digital algorithms Applied to Boolean Models

引用

SCANDINAVIAN JOURNAL OF STATISTICS 2017年第2期44卷 369-395页

作者： Hoerrmann, Julia Svane, Anne Marie Ruhr Univ Bochum Fac Math Bochum Germany Aarhus Univ Dept Math DK-8000 Aarhus C Denmark

We investigate the estimation of specific intrinsic volumes of stationary Boolean models by local digital algorithms;that is, by weighted sums of local configuration counts. We show that asymptotically unbiased estimators for the specific surface area or integrated mean curvature do not exist if the dimension is at least two or three, respectively. For three-dimensional stationary isotropic Boolean models, we derive asymptotically unbiased estimators for the specific surface area and integrated mean curvature. For a Boolean model with balls as grains, we even obtain an asymptotically unbiased estimator for the specific Euler characteristic.

关键词： Boolean model digital image local algorithm Miles formulae specific intrinsic volume

来源：评论

学校读者我要写书评

暂无评论

Testing of a local approach for the prediction of quality parameters in intact nectarines using a portable NIRS instrument

引用

POSTHARVEST BIOLOGY AND TECHNOLOGY 2011年第2期60卷 130-135页

作者： Sanchez, Maria-Teresa De la Haba, Maria-Jose Guerrero, Jose-Emilio 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

The nectarine sector requires rapid, economical and non-destructive methods for monitoring physical-chemical quality changes taking place not only during fruit development and at harvest, but also postharvest, thus allowing fruit quality to be evaluated at any stage in the commercial chain from grower to consumer. The use of sensors based on Near Infrared Spectroscopy (NIRS) technology, in conjunction with chemometric data treatment models, has already been studied for this quality-control purpose in nectarines. The critical challenge is to develop robust and accurate mathematic models based on hundreds of highly heterogeneous nectarine samples in order to represent the large natural variability of the fruit. This paper evaluates and compares the performance of MPLS regression and a local regression method for the prediction of major quality parameters including size (weight and diameter), flesh firmness and soluble solids content (SSC), in nectarines representing different harvests and crop practices. The results showed that the local algorithm offered no advantages over MPLS regression for the prediction of SSC and diameter, and only slight benefits in weight determination. For firmness evaluation, however, application of the local algorithm yielded a major improvement, reducing the standard error of prediction (SEP) by 27%, increasing the coefficient of determination (r(2)) by 44% (from 0.47 to 0.68), and reducing bias by 88.5% (from 6.95 N to 0.80 N). Thus, use of the local algorithm proved to be valuable in minimizing the error in NIRS models for predicting a parameter as complex as firmness. (C) 2010 Elsevier B.V. All rights reserved.

关键词： NIR spectroscopy Nectarine Portable sensor Quality parameters local algorithm

来源：评论

学校读者我要写书评

暂无评论

local and Parallel Finite Element algorithms for Eigenvalue Problems

引用

Acta Mathematicae Applicatae Sinica 2002年第2期18卷 185-200页

作者： Jinchao Xu Center for Computational Mathematics and Applications and Department of Mathematics Pennsylvania State UniversityUniversity ParkPennsylvania 16802USA

Some new local and parallel finite element algorithms are proposed and analyzed in this paper for eigenvalue problems. With these algorithms, the solution of an eigenvalue problem on a fine grid is reduced to the solution of an eigenvalue problem on a relatively coarse grid together with solutions of some linear algebraic systems on fine grid by using some local and parallel procedure. A theoretical tool for analyzing these algorithms is some local error estimate that is also obtained in this paper for finite element approximations of eigenvectors on general shape-regular grids.

关键词： Eigenvalue finite element local algorithm parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

local Stereo Matching Based on the Improved Matching Cost Function and the Adaptive Window 8

Local Stereo Matching Based on the Improved Matching Cost Fu...

引用

Proceedings 2015 8 International Congress on Image and Signal Processing (CISP)

作者： Liu, Jiling Zhang, Yong Dong, Xueguang Beijing Univ Aeronaut & Astronaut Sch Instrument Sci & Optoelect Engn Beijing Peoples R China

ISBN: (纸本)9781467390989

this paper presents a stereo matching algorithm based on the improved matching cost function and the adaptive window. First of all, AD, Census and gradient gap of left and right images are calculated. Joint bilateral filter is used for calculating weights of pixels, thereby constructing a matching cost function. Then, different aggregation window construction strategies are used for aggregating matching costs through pixel classification. One judgment of disparity computation validness is increased on the basis of using Winner-Takes-All strategy. Finally, disparity map is refined through regional voting, joint image inpainting and other optimization steps. Middlebury data sets are adopted for the experiment. The result shows that algorithm proposed in the paper has good processing result.

关键词： binocular stereo matching local algorithm matching cost function construction classification window

来源：评论

学校读者我要写书评

暂无评论

local Approximation of the Maximum Cut in Regular Graphs 1

引用

45th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)

作者： Bamas, Etienne Esperet, Louis Ecole Polytech Fed Lausanne Sch Comp & Commun Sci Lausanne Switzerland Univ Grenoble Alpes Lab G SCOP CNRS Grenoble France

ISBN: (数字)9783030307868

ISBN: (纸本)9783030307868;9783030307851

This paper is devoted to the distributed complexity of finding an approximation of the maximum cut in graphs. A classical algorithm consists in letting each vertex choose its side of the cut uniformly at random. This does not require any communication and achieves an approximation ratio of at least 1 2 in average. When the graph is d-regular and triangle-free, a slightly better approximation ratio can be achieved with a randomized algorithm running in a single round. Here, we investigate the round complexity of deterministic distributed algorithms for MAXCUT in regular graphs. We first prove that if G is d-regular, with d even and fixed, no deterministic algorithm running in a constant number of rounds can achieve a constant approximation ratio. We then give a simple one-round deterministic algorithm achieving an approximation ratio of 1/d for d-regular graphs with d odd. We show that this is best possible in several ways, and in particular no deterministic algorithm with approximation ratio 1/d + epsilon (with epsilon > 0) can run in a constant number of rounds. We also prove results of a similar flavour for the MAXDI-CUT problem in regular oriented graphs, where we want to maximize the number of arcs oriented from the left part to the right part of the cut.

关键词： Maximum cut Distributed approximation local algorithm

来源：评论

学校读者我要写书评

暂无评论

Short Paper: Structural Network Properties for local Planarization of Wireless Sensor Networks 15th

Short Paper: Structural Network Properties for Local Planari...

引用

15th International Conference on Ad-Hoc Networks and Wireless (ADHOC-NOW)

作者： Neumann, Florentin Estevao, Daniel Vivas Ockenfeld, Frank Radak, Jovan Frey, Hannes Univ Koblenz Landau Inst Comp Sci Koblenz Germany

ISBN: (纸本)9783319405094;9783319405087

Network graphs satisfying redundancy and coexistence can be planarized by means of local algorithms without making assumptions on the nodes' communication ranges. We generalize these properties to k-weak and k-strong coexistence and redundancy. Subsequently, we give empirical evidence that these properties are present in simulated wireless sensor networks as well as in actual testbed deployments, especially if looking at the graph's c-hop clustered overlay representations, for c <= 2.

关键词： WSN Planarization local algorithm Geometric graph Redundancy Coexistence Log normal shadowing Testbed measurements

来源：评论

学校读者我要写书评

暂无评论

local edge colouring of Yao-like subgraphs of Unit Disk Graphs

Local edge colouring of Yao-like subgraphs of Unit Disk Grap...

引用

14th International Colloquium on Stuctural Information and Communication Complexity

ISBN: (纸本)9783540729181

关键词： Edge colouring Geometric graphs Unit Disk Graphs local algorithm Location awareness Wedge Wireless network

来源：评论

学校读者我要写书评

暂无评论

local Construction of Connected Plane Subgraphs in Graphs Satisfying Redundancy and Coexistence 11

Local Construction of Connected Plane Subgraphs in Graphs Sa...

引用

11th Latin and American algorithms, Graphs and Optimization Symposium (LAGOS)

作者： Boeltz, Lucas Becker, Benjamin Frey, Hannes Univ Koblenz Landau Dept Comp Sci Koblenz Germany Tech Univ Darmstadt Multimedia Commun Lab Darmstadt Germany

Connected plane graphs enable many local algorithmic solutions for data communication, task coordination and network maintenance in wireless sensor networks, sensor-actuator networks and distributed robotics. We study construction of such graphs by removing edges from a given network graph. We assume redundancy and coexistence, a graph structure which holds in realistic wireless network models with high probability and which assures that a connected plane graph can always be constructed with local edge removal rules. We present a local algorithm to construct such a connected plane graph. We prove algorithm correctness under redundancy and coexistence assumption. Furthermore, we discuss how far redundancy and coexistence could be weakened while still assuring correctness of the algorithm. (C) 2021 The Authors. Published by Elsevier B.V.

关键词： Plane spanning subgraph local algorithm Redundancy Coexistence Correctness analysis

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：