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

Random access to abstract data types 8th

8th International Conference on Algebraic Methodology and Software Technology (AMAST)

作者： Erwig, M Fern Univ Hagen D-58084 Hagen Germany

ISBN: (纸本)3540675302

We show how to define recursion operators for random access data types, that is, ADTs that offer random access to their elements, and how algorithms on arrays and on graphs can be expressed by these operators. The approach is essentially based on a representation of ADTs as bialgebras that allows catamorphisms between ADTs to be defined by composing one ADT's algebra with the other ADT's coalgebra. The extension to indexed data types enables the development of specific recursion schemes, which are, in particular, suited to express a large class of graph algorithms.

关键词： category theory ADT catamorphism graph algorithm

来源：评论

学校读者我要写书评

暂无评论

An Efficient Implementation of Edmonds' algorithm for Maximum Matching on graphs

引用

Journal of the ACM (JACM) 1976年第2期23卷 221-234页

作者： Gabow, Harold N. Department of Computer Science University of Colorado Boulder CO 80302 United States

A matching on a graph is a set of edges, no two of which share a vertex. A maximum matching contains the greatest number of edges possible. This paper presents an efficient implementation of Edmonds’ algorithm for finding a maximum matching. The computation time is proportional to V₃, where V is the number of vertices;previous implementations of Edmonds’ algorithm have computation time proportional to V₄. The implementation is based on a system of labels that encodes the structure of alternating paths. © 1976, ACM. All rights reserved.

关键词： augmenting path graph algorithm labeling technique matching on a graph maximum matching

来源：评论

学校读者我要写书评

暂无评论

PTE: Enumerating Trillion Triangles On Distributed Systems 16

PTE: Enumerating Trillion Triangles On Distributed Systems

引用

22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD)

作者： Park, Ha-Myung Myaeng, Sung-Hyon Kang, U. Korea Adv Inst Sci & Technol Daejeon South Korea Seoul Natl Univ Seoul South Korea

ISBN: (纸本)9781450342322

How can we enumerate triangles from an enormous graph with billions of vertices and edges? Triangle enumeration is an important task for graph data analysis with many applications including identifying suspicious users in social networks, detecting web spams, finding communities, etc. However, recent networks are so large that most of the previous algorithms fail to process them. Recently, several MapReduce algorithms have been proposed to address such large networks;however, they suffer from the massive shuffled data resulting in a very long processing time. In this paper, we propose PTE (Pre-partitioned Triangle Enumeration), a new distributed algorithm for enumerating triangles in enormous graphs by resolving the structural inefficiency of the previous MapReduce algorithms. PTE enumerates trillions of triangles in a billion scale graph by decreasing three factors: the amount of shuffled data, total work, and network read. Experimental results show that PTE provides up to 47x faster performance than recent distributed algorithms on real world graphs, and succeeds in enumerating more than 3 trillion triangles on the ClueWeb12 graph with 6.3 billion vertices and 72 billion edges, which any previous triangle computation algorithm fail to process.

关键词： triangle enumeration big data graph algorithm scalable algorithm distributed algorithm network analysis

来源：评论

学校读者我要写书评

暂无评论

An Efficient Greedy Minimum Spanning Tree algorithm Based on Vertex Associative Cycle Detection Method 2

An Efficient Greedy Minimum Spanning Tree Algorithm Based on...

引用

2nd International Conference on Intelligent Computing, Communication & Convergence (ICCC)

作者： Biswas, Prantik Goel, Mansi Negi, Harshita Datta, Megha Natl Inst Technol Kurukshetra 136119 Haryana India

The minimal spanning tree problem is a popular problem of discrete optimization. Numerous algorithms have been developed using the traditional approach but with the emergence of modern-day complex data structures, new algorithms have been proposed which are more complex yet asymptotically efficient. In this paper we present a cycle detection based greedy algorithm, to obtain a minimal spanning tree of a given input weighted undirected graph. The algorithm operates on the idea that every connected graph without any cycle is a tree. At successive iterations, the algorithm selects and tests if the highest degree vertex is a member of any cycle to remove the most expensive edge from the cycle associated with it. The iteration continues until all the cycles are eliminated to obtain the resultant minimal spanning tree. The simplicity of the algorithm makes it easier to understand and implement in any high-level languages. The proposed approach will be beneficial in analyzing certain class of problems in science and engineering. (C) 2016 The Authors. Published by Elsevier B.V.

关键词： Discrete Optimization Minimal Spanning Tree Greedy algorithm Cycle Detection graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Triangle Counting on Large graphs

Triangle Counting on Large Graphs

引用

作者： Hu, Yang The George Washington University

学位级别：Ph.D., Doctor of Philosophy

Triangle counting is a fundamental graph algorithm. It is also used in a wide range of applications such as thematic structures, link recommendation, social network analysis, spam detection, and e-commerce. In addition, it is used as a building block in other graph related problems, such as graph isomorphism (subgraph matching), k-truss, and clustering coefficient. Various triangle counting algorithms are studied for decades. However, the conventional algorithms are designed for sequential execution and have difficulties to scale to high volume of parallelism device such as GPUs or distributed systems. Since the worst case time complexity of this algorithm is high, it takes a long time to execute for big graphs. Also, as graph size increases, external execution takes a large amount of disk I/O operations which as a result is slow. Existing solutions face several drawbacks of suboptimal I/O complexity, limited parallelism, and low scalability. My dissertation research strives to provide high performance solutions of fast triangle counting on big graphs. We identify the most emerging needs for fast triangle counting on large graphs which are two folds. First, scalable parallel triangle counting algorithm designed for GPUs and distributed systems is a key for fast processing on large graphs. Second, external memory algorithm to minimize disk I/Os for the graphs larger than memory size is also important for many large datasets. As a consequence, my dissertation research aims to solve the challenges described above. My first project TriCore is a new GPU based high-performance and scalable triangle counting system that consists of three main techniques. First, we designed a binary search based counting algorithm that tremendously increases both thread parallelism and memory performance. Second, TriCore exploits a 2-D partition method to distribute the CSR representation across multiple GPUs, combined with a new streaming buffer to load the edge list from outside of GPUs.

关键词： Triangle counting graph algorithm Subgraph matching

来源：评论

学校读者我要写书评

暂无评论

Towards a Formalisation of Expert's Knowledge for an Automatic Construction of a Vulnerability Model of a Cyberphysical System 7th

Towards a Formalisation of Expert's Knowledge for an Automat...

引用

7th International Conference on Information Systems Security and Privacy (ICISSP)

作者： Klaudel, Witold Rataj, Artur IRT SystemX Palaiseau France

ISBN: (纸本)9789897584916

We present a method for a quantitative formulation of the knowledge of security experts, to be used in an evaluation of attack costs in a cyberphysical system. In order to make the formulation practical, we classify the attacker forms and its attack positions. Applying boiler-plate patterns, like that of an operating system, is also possible. The obtained cost model may allow an exhaustive analysis of hypothetical weaknesses, employed in the design phase of a critical system.

关键词： Security Modelling Cyberphysical System Attack graph graph algorithm Probability

来源：评论

学校读者我要写书评

暂无评论

Efficient optimal surface detection: Theory, implementation and experimental validation

Efficient optimal surface detection: Theory, implementation ...

引用

Medical Imaging 2004 Conference

作者： Li, K Wu, XD Chen, DZ Sonka, M Sonka, M Univ Iowa Dept Elect & Comp Engn Iowa City IA USA

ISBN: (纸本)0819452831

In this paper, a novel polynomial-time algorithm is described for solving the optimal net surface detection problem on proper ordered multi-column graphs in N-D space (N greater than or equal to 3). The method is applied to searching for optimal object boundaries with arbitrary smoothness constraints in volumetric medical images. By simple transformations, such optimal surface detection problems can be simplified to a problem of computing the minimum s-t cuts in the transformed graphs. An efficient implementation for the 3-D case that can achieve near real-time performance on moderate-sized datasets is presented. We further examine our technique in experiments by segmenting the cylindrical surfaces of human airways from pulmonary volumetric CT images, and compare the results to those produced by previous methods. By allowing full specifications of the cost-function and smoothness constraints without degrading the performance, the new algorithm is more flexible than traditional methods and guarantees global optimality. The multi-dimensional nature of the algorithm maintains continuity in higher dimensions.

关键词： optimal surface surface segmentation minimum s-t cut graph algorithm CT

来源：评论

学校读者我要写书评

暂无评论

An O(n^1.75) algorithm for L(2,1)-labeling of trees

引用

11th Scandinavian Workshop on algorithm Theory (SWAT 2008)

作者： Hasunuma, Toru Ishii, Toshimasa Ono, Hirotaka Uno, Yushi Kyushu Univ Dept Comp Sci & Commun Engn Fukuoka 8128581 Japan Univ Tokushima Dept Math & Nat Sci Tokushima 7708502 Japan Otaru Univ Dept Informat & Management Sci Otaru Hokkaido 0478501 Japan Osaka Prefecture Univ Grad Sch Sci Dept Math & Informat Sci Sakai Osaka 5998531 Japan

ISBN: (纸本)3540699007

An L(2, 1)-labeling of a graph G is an assignment f from the vertex set V(G) to the set of nonnegative integers such that [f (x) - f (y)] >= 2 if x and y are adjacent and [f (x) - f (y)] >= 1 if x and y are at distance 2 for all x and y in V(G). A k-L(2, 1)-labeling is an L(2, 1)-labeling f : V(G) -> {0, ... , k}, and the L(2, 1)-labeling problem asks the minimum k, which we denote by lambda(G), among all possible L(2, 1)-labelings. It is known that this problem is NP-hard even for graphs of treewidth 2. Tree is one of a few classes for which the problem is polynomially solvable, but still only an O(Delta(4.5)n) time algorithm for a tree T has been known so far, where Delta is the maximum degree of T and n = vertical bar V(T)vertical bar. In this paper, we first show that an existent necessary condition for lambda(T) = Delta + 1 is also sufficient for a tree T with Delta = Omega(root n), which leads to a linear time algorithm for computing lambda(T) under this condition. We then show that lambda(T) can be computed in O(Delta(1.5)n) time for any tree T. Combining these, we finally obtain an O(n(1.75)) time algorithm, which substantially improves upon previously known results. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Frequency/channel assignment graph algorithm L(2,1)-labeling Vertex coloring

来源：评论

学校读者我要写书评

暂无评论

Anomaly Detection in the Dynamics of Web and Social Networks Using Associative Memory 19

Anomaly Detection in the Dynamics of Web and Social Networks...

引用

World Wide Web Conference (WWW)

作者： Miz, Volodymyr Ricaud, Benjamin Benzi, Kirell Vandergheynst, Pierre Ecole Polytech Fed Lausanne Lausanne Switzerland

ISBN: (纸本)9781450366748

In this work, we propose a new, fast and scalable method for anomaly detection in large time-evolving graphs. It may be a static graph with dynamic node attributes (e.g. time-series), or a graph evolving in time, such as a temporal network. We define an anomaly as a localized increase in temporal activity in a cluster of nodes. The algorithm is unsupervised. It is able to detect and track anomalous activity in a dynamic network despite the noise from multiple interfering sources. We use the Hopfield network model of memory to combine the graph and time information. We show that anomalies can be spotted with good precision using a memory network. The presented approach is scalable and we provide a distributed implementation of the algorithm. To demonstrate its efficiency, we apply it to two datasets: Enron Email dataset and Wikipedia page views. We show that the anomalous spikes are triggered by the real-world events that impact the network dynamics. Besides, the structure of the clusters and the analysis of the time evolution associated with the detected events reveals interesting facts on how humans interact, exchange and search for information, opening the door to new quantitative studies on collective and social behavior on large and dynamic datasets.

关键词： Anomaly Detection Dynamic Network graph algorithm Hopfield Network Wikipedia Web Logs Analysis

来源：评论

学校读者我要写书评

暂无评论

The Shortest Path Reconfiguration Problem Based on Relaxation of Reconfiguration Rules 1

引用

18th International Conference and Workshops on algorithms and Computation (WALCOM)

作者： Domon, Naoki Suzuki, Akira Tamura, Yuma Zhou, Xiao Tohoku Univ Grad Sch Informat Sci Sendai Miyagi Japan

ISBN: (数字)9789819705665

ISBN: (纸本)9789819705658;9789819705665

The shortest path problem is the most classical and fundamental problem in the field of graph algorithm. Recently, its reconfiguration variant, namely the Shortest Path Reconfiguration problem, has received a lot of attention. In this paper, we study the complexity of k-SPR, which generalizes the Shortest Path Reconfiguration problem, with respect to k. In k-SPR, we are allowed to replace at most k consecutive vertices of the current shortest path at a time. We first show that, for any fixed rational numbers c and epsilon such that c > 0 and 0 < epsilon <= 1, k-SPR with k = cn(1-epsilon) is polynomially solvable if epsilon = 1 and c < 1;otherwise, PSPACE-complete. This intractability holds even when given graphs are restricted to bipartite graphs and r-th power graphs, where r is any positive integer. Furthermore, when we restrict 0 < epsilon < 1, the PSPACE-completeness holds for graphs with maximum degree 3. Then, we design an FPT algorithm parameterized by mu = n/2 - k >= 0 that runs in O(m + 6.730(mu) mu(4) n) time. Finally, we show that, for any k, k-SPR can be solved in linear time for K-2,K-3-minor-free graphs.

关键词： Reconfiguration problem graph algorithm Parameterized complexity Shortest path

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：