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

EFFICIENT EDGE SPLITTING-OFF algorithms MAINTAINING ALL-PAIRS EDGE-CONNECTIVITIES

SIAM JOURNAL ON COMPUTING 2013年第3期42卷 1185-1200页

作者： Lau, Lap Chi Yung, Chun Kong Chinese Univ Hong Kong Dept Comp Sci & Engn Hong Kong Hong Kong Peoples R China Univ Toronto Dept Comp Sci Toronto ON Canada

We present new edge splitting-off results maintaining all-pairs edge-connectivities of an undirected graph. We first give an alternate proof of Mader's theorem, and use it to obtain a deterministic (O) over tilde (m + r(max)(2) . n(2))-time complete edge splitting-off algorithm for unweighted graphs, where r(max) denotes the maximum edge-connectivity requirement. This improves upon the best known algorithm by Gabow by a factor of (Omega) over tilde (n). We then prove a new structural property, and use it to further speed up the algorithm to obtain a randomized (O) over tilde (m+ r(max)(3) . n)-time algorithm. These edge splitting-off algorithms can be used directly to speed up various graph algorithms.

关键词： graph algorithms edge connectivity splitting off

来源：评论

学校读者我要写书评

暂无评论

PERFECT MATCHINGS IN O(n log n) TIME IN REGULAR BIPARTITE graphS

引用

SIAM JOURNAL ON COMPUTING 2013年第3期42卷 1392-1404页

作者： Goel, Ashish Kapralov, Michael Khanna, Sanjeev Stanford Univ Dept Management Sci & Engn Stanford CA 94305 USA Stanford Univ Dept Comp Sci Stanford CA 94305 USA Stanford Univ Inst Computat & Math Engn Stanford CA 94305 USA Univ Penn Dept Comp & Informat Sci Philadelphia PA 19104 USA

In this paper we consider the well-studied problem of finding a perfect matching in a d-regular bipartite graph on 2n nodes with m = nd edges. The best known algorithm for general bipartite graphs (due to Hopcroft and Karp) takes time O(m root n). In regular bipartite graphs, however, a matching is known to be computable in O(m) time (due to Cole, Ost, and Schirra). In a recent line of work by Goel, Kapralov, and Khanna the O(m) time bound was improved first to (O) over tilde (min{m, n(2.5)/d}) and then to (O) over tilde (min{m, n(2)/d}). In this paper, we give a randomized algorithm that finds a perfect matching in a d-regular graph and runs in O(n log n) time (both in expectation and with high probability). The algorithm performs an appropriately truncated alternating random walk to successively find augmenting paths. Our algorithm may be viewed as using adaptive uniform sampling, and is thus able to bypass the limitations of (nonadaptive) uniform sampling established in earlier work. Our techniques also give an algorithm that successively finds a matching in the support of a doubly stochastic matrix in expected time O(n log(2) n), with O(m) preprocessing time;this gives a simple O(m+mnlog(2) n) time algorithm for finding the Birkhoff-von Neumann decomposition of a doubly stochastic matrix. We show that randomization is crucial for obtaining o(nd) time algorithms by establishing an Omega(nd) lower bound for deterministic algorithms. We also show that there does not exist a randomized algorithm that finds a matching in a regular bipartite multigraph and takes o(n log n) time with high probability.

关键词： graph algorithms matchings bipartite regular graphs Birkhoff-von Neumann decomposition

来源：评论

学校读者我要写书评

暂无评论

An O(n²)-time algorithm for the minimal interval completion problem

引用

THEORETICAL COMPUTER SCIENCE 2013年 494卷 75-85页

作者： Crespelle, Christophe Todinca, Loan Univ Lyon 1 D NET INRIA LIP CNRSENS Lyon F-69622 Villeurbanne France Univ Orleans LIFO F-45067 Orleans 2 France

An interval completion of an arbitrary graph G is an interval graph H, on the same vertex set, obtained from G by adding new edges. If the set of newly added edges is inclusion-minimal among all possibilities, we say that H is a minimal interval completion of G. We give an O(n(2))-time algorithm to obtain a minimal interval completion of an arbitrary graph. This improves the previous O(nm) time bound for the problem and lowers this bound for the first time below the best known bound for minimal chordal completion. (c) 2013 Elsevier B.V. All rights reserved.

关键词： graph algorithms Interval graphs Minimal interval completions

来源：评论

学校读者我要写书评

暂无评论

Direction-optimizing breadth-first search

引用

SCIENTIFIC PROGRAMMING 2013年第3-4期21卷 137-148页

作者： Beamer, Scott Asanovic, Krste Patterson, David Univ Calif Berkeley Dept Elect Engn & Comp Sci Berkeley CA 94720 USA

Breadth-First Search is an important kernel used by many graph-processing applications. In many of these emerging applications of BFS, such as analyzing social networks, the input graphs are low-diameter and scale-free. We propose a hybrid approach that is advantageous for low-diameter graphs, which combines a conventional top-down algorithm along with a novel bottom-up algorithm. The bottom-up algorithm can dramatically reduce the number of edges examined, which in turn accelerates the search as a whole. On a multi-socket server, our hybrid approach demonstrates speedups of 3.3-7.8 on a range of standard synthetic graphs and speedups of 2.4-4.6 on graphs from real social networks when compared to a strong baseline. We also typically double the performance of prior leading shared memory (multicore and GPU) implementations.

关键词： graph algorithms breadth-first search

来源：评论

学校读者我要写书评

暂无评论

STEINER FOREST ORIENTATION PROBLEMS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2013年第3期27卷 1503-1513页

作者： Cygan, Marek Kortsarz, Guy Nutov, Zeev Univ Lugano IDSIA CH-6900 Lugano Switzerland Rutgers State Univ Dept Comp Sci Camden NJ 08102 USA Open Univ Israel Raanana Israel

We consider connectivity problems with orientation constraints. Given a directed graph D and a collection of ordered node pairs P let P[D] = {(u, v) is an element of P : D contains a uv-path}. In the Steiner Forest Orientation problem we are given an undirected graph G = (V, E) with edge-costs and a set P subset of V x V of ordered node pairs. The goal is to find a minimum-cost subgraph H of G and an orientation D of H such that P[D] = P. We give a 4-approximation algorithm for this problem. In the Maximum Pairs Orientation problem we are given a graph G and a multicollection of ordered node pairs P on V. The goal is to find an orientation D of G such that P[D] is maximum. Generalizing the result of Arkin and Hassin [Discrete Appl. Math., 116 (2002), pp. 271-278] for vertical bar P vertical bar = 2, we will show that for a mixed graph G (that may have both directed and undirected edges), one can decide in n(O(|P|)) time whether G has an orientation D with P[D] = P. (For undirected graphs this problem admits a polynomial time algorithm for any P, but it is NP-complete on mixed graphs.) For undirected graphs, we will show that one can decide whether G admits an orientation D with vertical bar P[D]vertical bar >= k in O(n + m) + 2(O(k . log log k)) time;hence this decision problem is fixed-parameter tractable, which answers an open question from Dorn et al. [algorithms Molecular Biol., 6 (2011)]. We also show that Maximum Pairs Orientation admits ratio O(log vertical bar P vertical bar/log log vertical bar P vertical bar), which is better than the ratio O(log n/log log n) of Gamzu, Segev, and Sharan [Proceedings of WABI 2010, pp. 215-225] when vertical bar P vertical bar < n.

关键词： approximation algorithms graph algorithms graph orientation parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Preprocess, Set, Query!

引用

ALGORITHMICA 2013年第4期67卷 516-528页

作者： Porat, Ely Roditty, Liam Bar Ilan Univ Dept Comp Sci Ramat Gan Israel

Thorup and Zwick (J. ACM 52(1):1-24, 2005 and STOC'01) in their seminal work introduced the notion of distance oracles. Given an n-vertex weighted undirected graph with m edges, they show that for any integer ka parts per thousand yen1 it is possible to preprocess the graph in time and generate a compact data structure of size O(kn (1+1/k) ). For each pair of vertices, it is then possible to retrieve an estimated distance with multiplicative stretch 2k-1 in O(k) time. For k=2 this gives an oracle of O(n (1.5)) size that produces in constant time estimated distances with stretch 3. Recently, PCZtraAYcu and Roditty (In: Proc. of 51st FOCS, 2010) broke the theoretical status-quo in the field of distance oracles and obtained a distance oracle for sparse unweighted graphs of O(n (5/3)) size that produces in constant time estimated distances with stretch 2. In this paper we show that it is possible to break the stretch 2 barrier at the price of non-constant query time in unweighted undirected graphs. We present a data structure that produces estimated distances with 1+epsilon stretch. The size of the data structure is O(nm (1-epsilon')) and the query time is . Using it for sparse unweighted graphs we can get a data structure of size O(n (1.87)) that can supply in O(n (0.87)) time estimated distances with multiplicative stretch 1.75.

关键词： graph algorithms Distance oracles Data structures

来源：评论

学校读者我要写书评

暂无评论

Faster Clustering Coefficient Using Vertex Covers

Faster Clustering Coefficient Using Vertex Covers

引用

ASE/IEEE International Conference on Social Computing (SocialCom)

作者： Green, Oded Bader, David A. Georgia Inst Technol Coll Comp Atlanta GA 30332 USA

ISBN: (纸本)9780769551371

Clustering coefficients, also called triangle counting, is a widely-used graph analytic for measuring the closeness in which vertices cluster together. Intuitively, clustering coefficients can be thought of as the ratio of common friends versus all possible connections a person might have in a social network. The best known time complexity for computing clustering coefficients uses adjacency list intersection and is O(V . d(max)(2)), where d(max) is the size of the largest adjacency list of all the vertices in the graph. In this work, we show a novel approach for computing the clustering coefficients in an undirected and unweighted graphs by exploiting the use of a vertex cover, (V) over cap subset of V. This new approach reduces the number of times that a triangle is counted by as many as 3 times per triangle. The complexity of the new algorithm is O((V) over cap . (d) over cap (2)(max) + t(VC)) where (d) over cap (max) is the size of the largest adjacency list in the vertex cover and t(VC) is the time needed for finding the vertex cover. Even for a simple vertex cover algorithm this can reduce the execution time 10%-30% while counting the exact number of triangles (3-circuits). We extend the use of the vertex cover to support counting squares (4-circuits) and clustering coefficients for dynamic graphs.

关键词： graph algorithms Social Network Analysis Network Science

来源：评论

学校读者我要写书评

暂无评论

On Fast Parallel Detection of Strongly Connected Components (SCC) in Small-World graphs 13

On Fast Parallel Detection of Strongly Connected Components ...

引用

International Conference for High Performance Computing, Networking, Storage and Analysis (SC)

作者： Hong, Sungpack Rodia, Nicole C. Olukotun, Kunle Oracle Labs Redwood Shores CA 94065 USA Stanford Univ Pervas Parallelism Lab Stanford CA USA

ISBN: (纸本)9781450323789

Detecting strongly connected components (SCCs) in a directed graph is a fundamental graph analysis algorithm that is used in many science and engineering domains. Traditional approaches in parallel SCC detection, however, show limited performance and poor scaling behavior when applied to large real-world graph instances. In this paper, we investigate the shortcomings of the conventional approach and propose a series of extensions that consider the fundamental properties of real-world graphs, e.g. the small-world property. Our scalable implementation offers excellent performance on diverse, small-world graphs resulting in a 5.01x to 29.41x parallel speedup over the optimal sequential algorithm with 16 cores and 32 hardware threads.

关键词： strongly connected components (SCC) multicore parallel algorithms graph algorithms small-world graphs

来源：评论

学校读者我要写书评

暂无评论

Detecting Dynamic and Static Geo-Social Communities

Detecting Dynamic and Static Geo-Social Communities

引用

4th International Conference on Computing for Geospatial Research and Application (COM.Geo)

作者： Lin, Frank Renner, Ray Northrop Grumman Informat Syst Mclean VA 22102 USA Northrop Grumman Informat Syst Chantilly VA USA

ISBN: (纸本)9780769550121

How communities form can depend on the geospatial location of people within a social network. Here, we investigated the implementation of the label propagation algorithm (LPA) and LabelRankT community detection algorithm in Gephi, a graph visualization tool. We researched extending these community detection algorithms to incorporate the geospatial distance between nodes in a network as a limiting factor for the automatic detection of community formation.

关键词： graph algorithms Social Network Analysis Geo-Social Community Detection Label Propagation Algorithm

来源：评论

学校读者我要写书评

暂无评论

Morph algorithms on GPUs 13

Morph Algorithms on GPUs

引用

18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

作者： Nasre, Rupesh Burtscher, Martin Pingali, Keshav Univ Texas Austin Inst Computat Engn & Sci Austin TX 78712 USA SW Texas State Univ Dept Comp Sci San Marcos TX 78666 USA Univ Texas Austin Dept Comp Sci Austin TX 78712 USA

ISBN: (纸本)9781450319225

There is growing interest in using GPUs to accelerate graph algorithms such as breadth-first search, computing page-ranks, and finding shortest paths. However, these algorithms do not modify the graph structure, so their implementation is relatively easy compared to general graph algorithms like mesh generation and refinement, which morph the underlying graph in non-trivial ways by adding and removing nodes and edges. We know relatively little about how to implement morph algorithms efficiently on GPUs. In this paper, we present and study four morph algorithms: (i) a computational geometry algorithm called Delaunay Mesh Refinement (DMR), (ii) an approximate SAT solver called Survey Propagation (SP), (iii) a compiler analysis called Points-to Analysis (PTA), and (iv) Boruvka's Minimum Spanning Tree algorithm (MST). Each of these algorithms modifies the graph data structure in different ways and thus poses interesting challenges. We overcome these challenges using algorithmic and GPU-specific optimizations. We propose efficient techniques to perform concurrent subgraph addition, subgraph deletion, conflict detection and several optimizations to improve the scalability of morph algorithms. For an input mesh with 10 million triangles, our DMR code achieves an 80x speedup over the highly optimized serial Triangle program and a 2.3x speedup over a multicore implementation running with 48 threads. Our SP code is 3x faster than a multicore implementation with 48 threads on an input with 1 million literals. The PTA implementation is able to analyze six SPEC 2000 benchmark programs in just 74 milliseconds, achieving a geometric mean speedup of 9.3x over a 48-thread multicore version. Our MST code is slower than a multicore version with 48 threads for sparse graphs but significantly faster for denser graphs. This work provides several insights into how other morph algorithms can be efficiently implemented on GPUs.

关键词： algorithms Languages Performance Morph algorithms graph algorithms Irregular Programs GPU CUDA Delaunay Mesh Refinement Survey Propagation Minimum Spanning Tree Boruvka Points-to Analysis

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：