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

AVERAGE SENSITIVITY OF graph algorithms

SIAM JOURNAL ON COMPUTING 2023年第4期52卷 1039-1081页

作者： Varma, Nithin Yoshida, Yuichi Chennai Math Inst Chennai 603103 Tamil Nadu India Natl Inst Informat Chiyoda Ku Tokyo 1018430 Japan

Modern applications of graph algorithms often involve the use of the output sets (usually, a subset of edges or vertices of the input graph) as inputs to other algorithms. Since the input graphs of interest are large and dynamic, it is desirable for an algorithm's output to not change drastically when a few random edges are removed from the input graph, so as to prevent issues in postprocessing. Alternately, having such a guarantee also means that one can revise the solution obtained by running the algorithm on the original graph in just a few places in order to obtain a solution for the new graph. We formalize this feature by introducing the notion of average sensitivity of graph algorithms, which is the average earth mover's distance between the output distributions of an algorithm on a graph and its subgraph obtained by removing an edge, where the average is over the edges removed and the distance between two outputs is the Hamming distance. In this work, we initiate a systematic study of average sensitivity of graph algorithms. After deriving basic properties of average sensitivity such as composition, we provide efficient approximation algorithms with low average sensitivities for concrete graph problems, including the minimum spanning forest problem, the global minimum cut problem, the minimum s-t cut problem, and the maximum matching problem. In addition, we prove that the average sensitivity of our global minimum cut algorithm is almost optimal, by showing a nearly matching lower bound. We also show that every algorithm for the 2-coloring problem has average sensitivity linear in the number of vertices. One of the main ideas involved in designing our algorithms with low average sensitivity is the following fact: if the presence of a vertex or an edge in the solution output by an algorithm can be decided locally, then the algorithm has a low average sensitivity, allowing us to reuse the analyses of known sublineartime algorithms and local computation algorith

关键词： average sensitivity graph algorithms sublinear algorithms approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Algorithm 1000: SuiteSparse:graphBLAS: graph algorithms in the Language of Sparse Linear Algebra

引用

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE 2019年第4期45卷 1–25页

作者： Davis, Timothy A. Texas A&M Univ 3112 TAMU College Stn TX 77845 USA

SuiteSparse:graphBLAS is a full implementation of the graphBLAS standard, which defines a set of sparse matrix operations on an extended algebra of semirings using an almost unlimited variety of operators and types. When applied to sparse adjacency matrices, these algebraic operations are equivalent to computations on graphs. graphBLAS provides a powerful and expressive framework for creating graph algorithms based on the elegant mathematics of sparse matrix operations on a semiring. An overview of the graphBLAS specification is given, followed by a description of the key features and performance of its implementation in the SuiteSparse:graphBLAS package.

关键词： graph algorithms sparse matrices graphBLAS

来源：评论

学校读者我要写书评

暂无评论

Efficient parallel graph algorithms for coarse-grained multicomputers and BSP

引用

ALGORITHMICA 2002年第2期33卷 183-200页

作者： Dehne, F Ferreira, A Cáceres, E Song, SW Roncato, A Carleton Univ Sch Comp Sci Ottawa ON K1S 5B6 Canada INRIA CNRS I3S Sophia Antipolis France Univ Fed Mato Grosso do Sul Campo Grande Brazil Univ Sao Paulo Sao Paulo Brazil Fac Sci Mat Fis & Nat Venice Italy

In this paper we present deterministic parallel algorithms for the coarse-grained multicomputer (CGM) and bulk synchronous parallel (BSP) models for solving the following well-known graph problems: (1) list ranking, (2) Euler tour construction in a tree, (3) computing the connected components and spanning forest, (4) lowest common ancestor preprocessing, (5) tree contraction and expression tree evaluation, (6) computing an ear decomposition or open ear decomposition, and (7) 2-edge connectivity and biconnectivity (testing and component computation). The algorithms require 0 (log p) communication rounds with linear sequential work per round (p = no. processors, N = total input size). Each processor creates, during the entire algorithm, messages of total size O(log(p)(N/p)). The algorithms assume that the local memory per processor (i,e,, N/p) is larger than p(epsilon), for some fixed epsilon > 0. Our results imply BSP algorithms with O(log p) supersteps, O(g log(p)(N/p)) communication time, and O(log(p)(N/p)) local computation time. It is important to observe that the number of communication rounds/supersteps obtained in this paper is independent of the problem size, and grows only logarithmically with respect to p. With growing problem size, only the sizes of the messages grow but the total number of messages remains unchanged. Due to the considerable protocol overhead associated with each message transmission, this is an important property. The result for Problem (1) is a considerable improvement over those previously reported, The algorithms for Problems (2)-(7) are the first practically relevant parallel algorithms for these standard graph problems.

关键词： coarse grained parallel computing graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Application of graph algorithms for Computing Mechanical Properties of Fullerene C₇₀ Nanoparticle

引用

JOURNAL OF COMPUTATIONAL AND THEORETICAL NANOSCIENCE 2012年第1期9卷 23-30页

作者： Khataee, H. R. Aris, T. N. Mohd Sulaiman, M. N. Univ Putra Malaysia Fac Comp Sci & Informat Technol Dept Comp Sci Upm Serdang 43400 Selangor Malaysia

Computational nanotechnology conceptualizes the basis of bottom-up approaches for constructing potential nanosystems. This paper introduces a new methodology of computational nanotechnology to calculate a set of optimal mechanical properties of the fullerene C-70 nanoparticle using graph algorithms which employ the real experimental data of C-70's structure. C-70 nanoparticle is composed of 70 equivalent carbon atoms arranged as a hollow cage in the form of a rugby-ball, egg-shaped structure which has some potential applications in relation with nanorobotic and bio-nanorobotic systems. In this work, at first, Wiener (W), hyper-Wiener (WW), Harary (Ha) and reciprocal Wiener (RW) indices were computed using dynamic programming and presented as: W (C-70) = 17749.9, WW (C-70) = 85448.4, Ha (C-70) = 120.9, and RW (C-70) = 435.6. The Hosoya and hyper-Hosoya polynomials of C-70, which are in relationship with C-70's indices, have been also computed and results revealed a good agreement with mathematical equations between indices and polynomials. Also, a graph algorithm based on greedy methods was employed to find a set of optimal electronic aspects of C-70's structure via computing the Minimum Weight Spanning Tree (MWST) of C-70. The computed MWST indicated that for connecting seventy carbon atoms of C-70 the minimum number of: (1) double bonds was 20, (2) intermediate bonds was 25, and (3) single bonds was 24. These results also showed good agreement with the principles of employed greedy algorithm.

关键词： C-70 Nanoparticle graph algorithms Dynamic Programming Greedy algorithms Computational Nanotechnology Bio-nanorobotic Systems Nanomechanical Systems

来源：评论

学校读者我要写书评

暂无评论

A functional approach to external graph algorithms

引用

ALGORITHMICA 2002年第3期32卷 437-458页

作者： Abello, J Buchsbaum, AL Westbrook, JR AT&T Labs Res Shannon Lab Florham Pk NJ 07932 USA 20th Century Televis Los Angeles CA 90025 USA

We present a new approach for designing external graph algorithms and use it to design simple, deterministic and randomized external algorithms for computing connected components, minimum spanning forests, bottleneck minimum spanning forests, maximal independent sets (randomized only), and maximal matchings in undirected graphs. Our I/O bounds compete with those of previous approaches. We also introduce a semi-external model, in which the vertex set but not the edge set of a graph fits in main memory. In this model we give an improved connected components algorithm, using new results for external grouping and sorting with duplicates. Unlike previous approaches, ours is purely functional-without side effects-and is thus amenable to standard checkpointing and pro.-ramming language optimization techniques. This is an important practical consideration for applications that may take hours to run.

关键词： connected components external memory algorithms graph algorithms maximal matchings maximal independent sets minimum spanning trees functional programming

来源：评论

学校读者我要写书评

暂无评论

MapReduce in MPI for Large-scale graph algorithms

引用

PARALLEL COMPUTING 2011年第9期37卷 610-632页

作者： Plimpton, Steven J. Devine, Karen D. Sandia Natl Labs Albuquerque NM 87185 USA

We describe a parallel library written with message-passing (MPI) calls that allows algorithms to be expressed in the Map Reduce paradigm. This means the calling program does not need to include explicit parallel code, but instead provides "map" and "reduce" functions that operate independently on elements of a data set distributed across processors. The library performs needed data movement between processors. We describe how typical Map Reduce functionality can be implemented in an MPI context, and also in an out-of-core manner for data sets that do not fit within the aggregate memory of a parallel machine. Our motivation for creating this library was to enable graph algorithms to be written as MapReduce operations, allowing processing of terabyte-scale data sets on traditional MPI-based clusters. We outline MapReduce versions of several such algorithms: vertex ranking via PageRank, triangle finding, connected component identification, Luby's algorithm for maximally independent sets, and single-source shortest-path calculation. To test the algorithms on arbitrarily large artificial graphs we generate randomized R-MAT matrices in parallel;a MapReduce version of this operation is also described. Performance and scalability results for the various algorithms are presented for varying size graphs on a distributed-memory cluster. For some cases, we compare the results with non-MapReduce algorithms, different machines, and different MapReduce software, namely Hadoop. Our open-source library is written in C++, is callable from C++, C, Fortran, or scripting languages such as Python, and can run on any parallel platform that supports MPI. (C) 2011 Elsevier B.V. All rights reserved.

关键词： MapReduce Message-passing MPI graph algorithms R-MAT matrices

来源：评论

学校读者我要写书评

暂无评论

Relaxing the Irrevocability Requirement for Online graph algorithms

引用

ALGORITHMICA 2022年第7期84卷 1916-1951页

作者： Boyar, Joan Favrholdt, Lene M. Kotrbcik, Michal Larsen, Kim S. Univ Southern Denmark Dept Math & Comp Sci Campusvej 55 DK-5230 Odense M Denmark Univ Queensland Sch Math & Phys Brisbane Qld 4072 Australia

Online graph problems are considered in models where the irrevocability requirement is relaxed. We consider the Late Accept model, where a request can be accepted at a later point, but any acceptance is irrevocable. Similarly, we consider a Late Reject model, where an accepted request can later be rejected, but any rejection is irrevocable (this is sometimes called preemption). Finally, we consider the Late Accept/Reject model, where late accepts and rejects are both allowed, but any late reject is irrevocable. We consider four classical graph problems: For Maximum Independent Set, the Late Accept/Reject model is necessary to obtain a constant competitive ratio, for Minimum Vertex Cover the Late Accept model is sufficient, and for Minimum Spanning Forest the Late Reject model is sufficient. The Maximum Matching problem admits constant competitive ratios in all cases. We also consider Maximum Acyclic Subgraph and Maximum Planar Subgraph, which exhibit patterns similar to Maximum Independent Set.

关键词： Online algorithms graph algorithms Competitive analysis Preemption Recourse

来源：评论

学校读者我要写书评

暂无评论

Automated building layout generation using deep learning and graph algorithms

引用

AUTOMATION IN CONSTRUCTION 2023年第1期154卷

作者： Wang, Lufeng Liu, Jiepeng Zeng, Yan Cheng, Guozhong Hu, Huifeng Hu, Jiahao Huang, Xuesi Chongqing Univ Key Lab New Technol Construct Cities Mt Area Minist Educ Chongqing 400045 Peoples R China Chongqing Univ Sch Civil Engn Chongqing 400045 Peoples R China

Designing architectural layouts is a complex task that has garnered significant attention in the research community. While automated site layout design and flat layout design have been extensively studied, automated building layout design has been relatively overlooked. This paper describes an approach for generating automated building layouts using deep learning and graph algorithms. A unique building layout dataset is created to support the proposed approach. Euclidean distance, Dice coefficient, and a force-directed graph algorithm are employed for layout selection and fine-tuning. The Input-controlled Spatial Attention U-Net model accurately segments the building region, and the resulting layout is refined through image operations, leading to comprehensive BIM models for designers. Through two generative case studies and a comparative experiment with neural networks, this paper demonstrates the effectiveness of the approach that can assist designers during the initial stages of design and enable a rapid generation of complete layouts for individual buildings.

关键词： Layout plan Deep learning graph algorithms Building layout AI-generated content

来源：评论

学校读者我要写书评

暂无评论

Leaf-sequencing for intensity-modulated arc therapy using graph algorithms

引用

MEDICAL PHYSICS 2008年第1期35卷 61-69页

作者： Luan, Shuang Wang, Chao Cao, Daliang Chen, Danny Z. Shepard, David M. Yu, Cedric X. Univ New Mexico Dept Comp Sci Albuquerque NM 87131 USA Univ Notre Dame Dept Comp Sci & Engn Notre Dame IN 46556 USA Swedish Canc Inst Seattle WA 98104 USA Univ Maryland Sch Med Dept Radiat Oncol Baltimore MD 21201 USA

Intensity-modulated arc therapy (IMAT) is a rotational IMRT technique. It uses a set of overlapping or nonoverlapping arcs to create a prescribed dose distribution. Despite its numerous advantages, IMAT has not gained widespread clinical applications. This is mainly due to the lack of an effective IMAT leaf-sequencing algorithm that can convert the optimized intensity patterns for all beam directions into IMAT treatment arcs. To address this problem, we have developed an IMAT leaf-sequencing algorithm and software using graph algorithms in computer science. The input to our leaf-sequencing software includes (1) a set of (continuous) intensity patterns optimized by a treatment planning system at a sequence of equally spaced beam angles (typically 10 degrees apart), (2) a maximum leaf motion constraint, and (3) the number of desired arcs, k. The output is a set of treatment arcs that best approximates the set of optimized intensity patterns at all beam angles with guaranteed smooth delivery without violating the maximum leaf motion constraint. The new algorithm consists of the following key steps. First, the optimized intensity patterns are segmented into intensity profiles that are aligned with individual MLC leaf pairs. Then each intensity profile is segmented into k MLC leaf openings using a k-link shortest path algorithm. The leaf openings for all beam angles are subsequently connected together to form 1D IMAT arcs under the maximum leaf motion constraint using a shortest path algorithm. Finally, the 1D IMAT arcs are combined to form IMAT treatment arcs of MLC apertures. The performance of the implemented leaf-sequencing software has been tested for four treatment sites (prostate, breast, head and neck, and lung). In all cases, our leaf-sequencing algorithm produces efficient and highly conformal IMAT plans that rival their counterpart, the tomotherapy plans, and significantly improve the IMRT plans. Algorithm execution times ranging from a few seconds to 2 min ar

关键词： IMAT intensity-modulated arc therapy leaf sequencing graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Filmification of methods: A visual language for graph algorithms

引用

JOURNAL OF VISUAL LANGUAGES AND COMPUTING 2008年第1期19卷 123-150页

作者： Watanobe, Yutaka Mirenkov, Nikolay N. Yoshioka, Rentaro Monakhov, Oleg Univ Aizu Grad Dept Informat Syst Fukushima 9658580 Japan Russian Acad Sci Inst Computat Math & Math Geophys Siberian Div R-630090 Novosibirsk Russia

A novel approach for using the filmification of methods concept in the graph algorithm representation, specification, and programming is considered. it is based on a "cyberFilm" format, where a set of multimedia frames represents algorithmic features. A brief description of the cyberFilm concept and an observation of graph algorithm features are presented. A number of cyberFilms related to Prim's and Dijkstra's algorithms have been developed and used to explain the basic ideas of the approach. Several versions of the algorithm visualization are demonstrated by corresponding examples of cyberFilm frames and icon language representations. In addition, a method for program generation from the cyberFilm specification is provided with explanations of program templates supporting the cyberFilm frames. (c) 2006 Published by Elsevier Ltd.

关键词： visual programming languages CyberFilm graph algorithms program templates

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：