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

Distributed approximate minimal Steiner trees with millions of seed vertices on billion-edge graphs

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2023年第1期181卷

作者： Reza, Tahsin Steil, Trevor Sanders, Geoffrey Pearce, Roger Lawrence Livermore Natl Lab Ctr Appl Sci Comp 7000 East Ave Livermore CA 94550 USA

In this paper, we present a parallel 2-approximation Steiner minimal tree algorithm and its MPI-based distributed implementation. In place of expensive distance computations between all pairs of seed vertices, the solution we employ exploits a cheaper Voronoi cell computation. Our design leverages asynchronous processing and message prioritization to accelerate convergence of distance computations, and harnesses vertex and edge centric processing to offer fast time-to-solution. We demonstrate scalability and performance using real-world graphs with up to 128 billion edges and 512 compute nodes, and show the ability to find Steiner trees with up to one million seed vertices. Using 12 data instances, we present comparison with the state-of-the-art exact solver, SCIP-Jack, and two sequential 2-approximate algorithms. We empirically show that, on average, the total distance of the Steiner tree identified by our solution is 1.1290 times greater than the Steiner minimal tree - well within the theoretical approximation bound of 2.& COPY;2023 Elsevier Inc. All rights reserved.

关键词： graph algorithm Steiner tree Distributed computing hpc Asynchronous processing

来源：评论

学校读者我要写书评

暂无评论

I/O-Efficient algorithms for Topological Sort and Related Problems

引用

ACM TRANSACTIONS ON algorithmS 2022年第1期18卷 5-5页

作者： Cao, Nairen Fineman, Jeremy T. Russell, Katina Yang, Eugene Georgetown Univ Dept Comp Sci St Marys Hall37th & O St NW Washington DC 20057 USA

This article presents I/O-efficient algorithms for topologically sorting a directed acyclic graph and for the more general problem identifying and topologically sorting the strongly connected components of a directed graph G = (V, E). Both algorithms are randomized and have I/O-costs O(sort (E) center dot poly(log V)), with high probability, where sort (E) = O(E/B log(M/B) (E/B)) is the I/O cost of sorting an |E|-element array on a machine with size-B blocks and size-M cache/internal memory. These are the first algorithms for these problems that do not incur at least one I/O per vertex, and as such these are the first I/O-efficient algorithms for sparse graphs. By applying the technique of time-forward processing, these algorithms also imply I/O-efficient algorithms for most problems on directed acyclic graphs, such as shortest paths, as well as the single-source reachability problem on arbitrary directed graphs.

关键词： I/O efficient graph algorithm topological sort external memory strongly connected components

来源：评论

学校读者我要写书评

暂无评论

Eigenvector centrality based algorithm for finding a maximal common connected vertex induced molecular substructure of two chemical graphs

引用

JOURNAL OF MOLECULAR STRUCTURE 2021年 1244卷 130980-130980页

作者： Parisutham, Nirmala Rethnasamy, Nadarajan PSG Coll Technol Dept Appl Math & Computat Sci Coimbatore 641004 Tamil Nadu India

The physical and biological properties of a chemical molecule entity are related to its structure. One of the basic widely accepted principles in chemistry is that compounds with similar structures frequently share similar physicochemical properties and biological activities. The process of finding structural similarities between chemical structures of molecules helps to identify the common behavior of these molecules. A familiar approach to capture the structural similarity between two chemical compounds is to detect a maximal Common Connected vertex induced Subgraph (CCS) in their molecular chemical graphs. The proposed algorithm detects a maximal CCS by checking the induced property of the vertices which are collected by performing a DFS search on the tensor product graph of two input molecular chemical graphs. The DFS search will start from the node which has the highest eigenvector centrality in the tensor product graph. The significance of the proposed work is that it uses eigenvector centrality to predict the root node of the DFS search tree, so that the resulting sugraph gets more number of nodes (i.e. large size maximal CCS). The experimental results on synthetic and real chemical database, further ensure the competence of the proposed algorithm when compared with the existing works. (c) 2021 Elsevier B.V. All rights reserved.

关键词： Maximal common subgraph Substructure mining graph algorithm Molecular similarity search

来源：评论

学校读者我要写书评

暂无评论

Approximation algorithms for multicast routings in a network with multi-sources

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2007年第5期E90A卷 900-906页

作者： Mosry, Ehab Nagamochi, Hiroshi Kyoto Univ Grad Sch Informat Dept Appl Math & Phys Kyoto 6068501 Japan

We consider the capacitated multi-source multicast tree routing problem (CMMTR) in an undirected graph G = (V,E) with a vertex set V, an edge set E and an edge weight w(e) >= 0, e epsilon E. We are given a source set S epsilon V with a weight g(e) >= 0, e epsilon S, a terminal set M subset of V - S with a demand function q : M -> R+, and a real number K > 0, where g(s) means the cost for opening a vertex s is an element of S as a source in a multicast tree. Then the CMMTR asks to find a subset S' subset of S, a partition {Z(1), Z(2),..., Z(l)) of M, and a set of subtrees T-1, T-2,..., T-l of G such that, for each i, Sigma(l is an element of Zi) q(t) <= K and T-i spans Z(i) boolean OR {s} for some s epsilon S'. The objective is to minimize the sum of the opening cost of S' and the constructing cost of (T-i), i.e., Sigma(s epsilon S') g(s) + Sigma(l)(i)=1 w(T-i), where w(T-i) denotes the sum of weights of all edges in Ti. In this paper, we propose a (2puFL + PST)-approximation algorithm to the CMMTR, where puFL and PST are any approximation ratios achievable for the uncapacitated facility location and the Steiner tree problems, respectively. When all terminals have unit demands, we give a ((3/2)rho(UFL) + (4/3)rho(ST)) -approximation algorithm.

关键词： approximation algorithm facility location problem graph algorithm multicast routing problem network optimization tree cover

来源：评论

学校读者我要写书评

暂无评论

Grafy, grafové algoritmy a jejich užití

Grafy, grafové algoritmy a jejich užití

引用

作者： Venerová, Lenka Brno University of Technology

Bakalářská práce se primárně zabývá problematikou grafů a grafových algoritmů. Jedná se především o vysvětlení a rozšíření daného tématu. Velice ... 详细信息

Bakalářská práce se primárně zabývá problematikou grafů a grafových algoritmů. Jedná se především o vysvětlení a rozšíření daného tématu. Velice často jsou před nás kladeny problémy, které, ač nevědomky, řešíme využitím znalostí grafových algoritmů. Dílčím cílem mojí práce je proto demonstrovat aplikaci některých těchto metod v oblasti řešení distribučních úloh.

关键词： Graf neorientovaný graf orientovaný graf grafový algoritmus cesta strom kostra grafu dopravní problém metoda řešení graph undirected graph directed graph graph algorithm path tree graph framework itinerary problem solution method Text

来源：评论

学校读者我要写书评

暂无评论

LazyFox: fast and parallelized overlapping community detection in large graphs

引用

PEERJ COMPUTER SCIENCE 2023年 9卷 e1291页

作者： Garrels, Tim Khodabakhsh, Athar Renard, Bernhard Y. Baum, Katharina Hasso Plattner Inst Digital Engn gGmbH Potsdam Germany Univ Potsdam Digital Engn Fac Potsdam Germany Free Univ Berlin Dept Math & Comp Sci Berlin Germany Icahn Sch Med Mt Sinai Windreich Dept Artificial Intelligence & Human He New York NY USA Icahn Sch Med Mt Sinai Hasso Plattner Inst Digital Hlth Mt Sinai New York NY USA

The detection of communities in graph datasets provides insight about a graph's underlying structure and is an important tool for various domains such as social sciences, marketing, traffic forecast, and drug discovery. While most existing algorithms provide fast approaches for community detection, their results usually contain strictly separated communities. However, most datasets would semantically allow for or even require overlapping communities that can only be determined at much higher computational cost. We build on an efficient algorithm, FOX, that detects such overlapping communities. FOX measures the closeness of a node to a community by approximating the count of triangles which that node forms with that community. We propose LAZYFOX, a multi-threaded adaptation of the FOX algorithm, which provides even faster detection without an impact on community quality. This allows for the analyses of significantly larger and more complex datasets. LAZYFOX enables overlapping community detection on complex graph datasets with millions of nodes and billions of edges in days instead of weeks. As part of this work, LAZYFOX's implementation was published and is available as a tool under an MIT licence at https://***/TimGarrels/LazyFox.

关键词： Overlapping community detection Large networks Weighted clustering coefficient Heuristic triangle estimation Parallelized algorithm C++ tool Runtime improvement Open source graph algorithm Community analysis

来源：评论

学校读者我要写书评

暂无评论

Maintaining minimum spanning forests in dynamic graphs

引用

SIAM JOURNAL ON COMPUTING 2001年第2期31卷 364-374页

作者： Henzinger, MR King, V Google Inc Mt View CA 94043 USA Univ Victoria Dept Comp Sci Victoria BC V8W 3P4 Canada

We present the rst fully dynamic algorithm for maintaining a minimum spanning forest in time o(rootn) per operation. To be precise, the algorithm uses O(n(1/3) log n) amortized time per update operation. The algorithm is fairly simple and deterministic. An immediate consequence is the first fully dynamic deterministic algorithm for maintaining connectivity and bipartiteness in amortized time O(n(1/3) log n) per update, with O(1) worst case time per query.

关键词： dynamic graph graph algorithm minimum spanning tree data structure

来源：评论

学校读者我要写书评

暂无评论

The design and evaluation of data-dependent hardware for subgraph isomorphism problem

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2004年第8期E87D卷 2038-2047页

作者： Yamamoto, S Ichikawa, S Yamamoto, H Toyohashi Univ Technol Dept Knowledgebased Informat Engn Toyohashi Aichi 4418580 Japan

Subgraph isomorphism problems have various important applications, while generally being NP-complete. Though Ullmann and Konishi proposed the custom circuit designs to accelerate subgraph isomorphism problem, they require many hardware resources for large problems. This study describes the design of data-dependent circuits for subgraph isomorphism problem with evaluation results on an actual FPGA platform. Data-dependent circuits are logic circuits specialized in specific input data. Such circuits are smaller and faster than the original circuit, although it is not reusable and involves circuit generation for each input. In the present study, the circuits were implemented on Xilinx XC2V3000 FPGA, and they successfully operated at a clock frequency 25 MHz. In the case of graphs with 16 vertices, the average execution time is about 7.0% of the software executed on an up-to-date microprocessor (Athlon XP 2600+ of 2.1 GHz clock). Even if the circuit generation time is included, data-dependent circuits are about 14.4 times faster than the software (for random graphs with 16 vertices). This performance advantage becomes larger for larger graphs. Two algorithms (Ullmann's and Konishi's) were examined, and the data-dependent approach was found to be equally effective for both algorithms. We also examined two types of input graph sets, and found that the data-dependent approach shows advantage in both cases.

关键词： FPGA custom circuit graph algorithm NP-complete partial evaluation

来源：评论

学校读者我要写书评

暂无评论

PARALLEL COMPLEXITY OF MAXIMAL PATH COVER PROBLEMS FOR DIRECTED ACYCLIC graphS

引用

SYSTEMS AND COMPUTERS IN JAPAN 1994年第12期25卷 23-32页

作者： YAMAGAMI, K YAKU, T UEMURA, K TOKYO DENKI UNIV DEPT INFORMAT SCITOKYOSAITAMA 350JAPAN TSURU UNIV TSURU 402JAPAN

The problem of covering an acyclic directed graph (DAG) with node disjoint paths is discussed. Such a ''path cover'' is called ''maximal'' if the number of paths is minimum. The parallel computational complexity for the problem of finding a maximal path cover for a DAG [3-7, 9, 13, 17] is studied and the problem is shown to belong to class NC when either in-degree or out-degree is at most 2. From this result it can be shown that the maximal bipartite matching problem is also in class NC when the degree of one of the node sets is at most 2.

关键词： A PATH COVER graph algorithm PARALLEL COMPLEXITY ALTERNATE graph BIPARTITE graph

来源：评论

学校读者我要写书评

暂无评论

Entropy promotes charge separation in bulk heterojunction organic photovoltaics

引用

JOURNAL OF PHOTOCHEMISTRY AND PHOTOBIOLOGY A-CHEMISTRY 2019年第0期382卷 111875-000页

作者： Kawashima, Eisuke Fujii, Mikiya Yamashita, Koichi Univ Tokyo Grad Sch Engn Dept Chem Syst Engn Bunkyo Ku 7-3-1 Hongo Tokyo Japan

Charge separation is one of the crucial processes in the photoelectric conversion of organic photovoltaics. It is considered that organic photovoltaics have low performances because of strong Coulomb attraction. In this work, an entropy-driven charge-separation mechanism was elucidated using a graph algorithm and dynamic Monte Carlo simulations. Helmholtz energies were decreased by entropies, and had a barrier (240-270 meV) at an electron-hole distance of 6 nm;separation efficiencies at interfaces of large donor: small acceptor domains were lower than those at large donor: large acceptor domains, which can be attributed to their higher barrier-separation was promoted by a decreased barrier.

关键词： Organic photovoltaics Morphology Entropy graph algorithm Dynamic Monte Carlo

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：