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

FBSgraph: Accelerating Asynchronous graph Processing via Forward and Backward Sweeping

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2018年第5期30卷 895-907页

作者： Zhang, Yu Liao, Xiaofei Jin, Hai Gu, Lin Zhou, Bing Bing Huazhong Univ Sci & Technol Serv Comp Technol & Syst Lab Cluster & Grid Comp Lab Sch Comp Sci & Technol Wuhan 430074 Hubei Peoples R China Univ Sydney Sch Informat Technol Sydney NSW 2006 Australia

graph algorithm is pervasive in many applications ranging from targeted advertising to natural language processing. Recently, Asynchronous graph Processing (AGP) is becoming a promising model to support graph algorithm on large-scale distributed computing platforms because it enables faster convergence speed and lower synchronization cost than the synchronous model for no barrier between iterations. However, existing AGP methods still suffer from poor performance for inefficient vertex state propagation. In this paper, we propose an effective and low-cost forward and backward sweeping execution method to accelerate state propagation for AGP, based on a key observation that states in AGP can be propagated between vertices much faster when the vertices are processed sequentially along the graph path within each round. Through dividing graph into paths and asynchronously processing vertices on each path in an alternative forward and backward way according to their order on this path, vertex states in our approach can be quickly propagated to other vertices and converge in a faster way with only little additional overhead. In order to efficiently support it over distributed platforms, we also propose a scheme to reduce the communication overhead along with a static priority ordering scheme to further improve the convergence speed. Experimental results on a cluster with 1,024 cores show that our approach achieves excellent scalability for large-scale graph algorithms and the overall execution time is reduced by at least 39.8 percent, in comparison with the most cutting-edge methods.

关键词： graph algorithm synchronous/asynchronous convergence cascade effect

来源：评论

学校读者我要写书评

暂无评论

graph model for optimal OVSF code placement strategies

引用

INTERNATIONAL JOURNAL OF AD HOC AND UBIQUITOUS COMPUTING 2012年第3期9卷 133-141页

作者： Ouyang, Wen Yu, Chang Wu Liu, Meng-Ti Chang, Yu-Wei Chung Hua Univ Dept Comp Sci & Informat Engn Hsinchu 30012 Taiwan

The code utilisation of OVSF-CDMA systems are significantly impacted by the code placement and replacement schemes which have been studied by many researchers as independent problems. We formally define the placement optimality and present a novel graph model, CIDP, which is proved to be NP-complete for general graphs where the CIDP graphs reduced from the OVSF code placement problem are trivial perfect graphs. A unified algorithm UCMS-1, provided to firstly address both OVSF code placement and replacement jointly, achieves placement optimality in linear time complexity. It shows that OVSF code placement optimality problem is in P.

关键词： graph algorithm OVSF-CDMA code blocking code placement constrained independent dominating set

来源：评论

学校读者我要写书评

暂无评论

Reconfiguration of list L(2,1)-labelings in a graph

引用

THEORETICAL COMPUTER SCIENCE 2014年第C期544卷 84-97页

作者： Ito, Takehiro Kawamura, Kazuto Ono, Hirotaka Zhou, Xiao Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 9808579 Japan Kyushu Univ Fac Econ Higashi Ku Fukuoka 8128581 Japan

For an integer k >= 0, suppose that each vertex v of a graph G has a set C(v) subset of {0, 1,..., k} of labels, called a list of v. A list L(2, 1)-labeling of G is an assignment of a label in C(v) to each vertex v of G such that every two adjacent vertices receive labels which differ by at least 2 and every two vertices of distance two receive labels which differ by at least 1. In this paper, we study the problem of reconfiguring one list L(2, 1)-labeling of a graph into another list L(2, 1)-labeling of the same graph by changing only one label assignment at a time, while at all times maintaining a list L(2, 1)-labeling. First we show that this decision problem is PSPACE-complete, even for bipartite planar graphs and k >= 6. In contrast, we then show that the problem can be solved in linear time for general graphs if k <= 4. We finally consider the problem restricted to trees, and give a sufficient condition for which any two list L(2, 1)-labelings of a tree can be transformed into each other. (C) 2014 Elsevier B.V. All rights reserved.

关键词： graph algorithm L(2,1)-labeling PSPACE-complete Reachability on solution space

来源：评论

学校读者我要写书评

暂无评论

A graph theoretic approach to protein structure selection

引用

ARTIFICIAL INTELLIGENCE IN MEDICINE 2009年第2-3期45卷 229-237页

作者： Vassura, Marco Margara, Luciano Fariselli, Piero Casadio, Rita Univ Bologna Dept Comp Sci I-40127 Bologna Italy Univ Bologna Dept Biol Biocomp Grp I-40127 Bologna Italy

Objective: Protein structure prediction (PSP) aims to reconstruct the 3D structure of a given protein starting from its primary structure (chain of amino acidic residues). It is a well-known fact that the 3D structure of a protein only depends on its primary structure. PSP is one of the most important and still unsolved problems in computational biology. Protein structure selection (PSS), instead of reconstructing a 3D model for the given chain, aims to select among a given, possibly large, number of 3D structures (called decoys) those that are closer (according to a given notion of distance) to the original (unknown) one. In this paper we address PSS problem using graph theoretic techniques. Methods and materials: Existing methods for solving PSS make use of suitably defined energy functions which heavily rely on the primary structure of the protein and on protein chemistry. In this paper we present a new approach to PSS which does not take advantage of the knowledge of the primary structure of the protein but only depends on the graph theoretic properties of the decoys graphs (vertices represent residues and edges represent pairs of residues whose Euclidean distance is less than or equal to a fixed threshold). Results: Even if our methods only rely on approximate geometric information, experimental results show that some of the adopted graph properties score similarly to energy-based filtering functions in selecting the best decoys. Conclusion: Our results highlight the principal role of geometric information in PSS, setting a new starting point and filtering method for existing energy function-based techniques. (c) 2008 Elsevier B.V. All rights reserved.

关键词： Protein structure prediction Protein folding Protein structure selection Contact maps graph algorithm

来源：评论

学校读者我要写书评

暂无评论

A graph-Based Approach to Find Teleconnections in Climate Data

引用

STATISTICAL ANALYSIS AND DATA MINING 2013年第3期6卷 158-179页

作者： Kawale, Jaya Liess, Stefan Kumar, Arjun Steinbach, Michael Snyder, Peter Kumar, Vipin Ganguly, Auroop R. Samatova, Nagiza F. Semazzi, Fredrick Univ Minnesota Dept Comp Sci Minneapolis MN 55455 USA Univ Minnesota Dept Soil Water & Climate St Paul MN 55108 USA Northeastern Univ Civil & Environm Engn Boston MA 02115 USA N Carolina State Univ Dept Comp Sci Raleigh NC 27695 USA N Carolina State Univ Dept Marine Earth & Atmospher Sci Raleigh NC 27695 USA

Pressure dipoles are important long distance climate phenomena (teleconnection) characterized by pressure anomalies of the opposite polarity appearing at two different locations at the same time. Such dipoles have been proven important for understanding and explaining the variability in climate in many regions of the world, e.g. the El Nino Southern Oscillation (ENSO) climate phenomenon, which is described by opposite pressure anomalies between the west and east Pacific and is known to be responsible for precipitation and temperature anomalies worldwide. This paper presents a graph-based approach called shared reciprocal nearest neighbor approach that considers only reciprocal positive and negative edges in the shared nearest neighbor graph to find the dipoles. One crucial aspect of our approach to the analysis of such networks is a careful treatment of negative correlations, whose proper consideration is critical for finding the dipoles. Further, our work shows the importance of modeling the time-dependent patterns of the dipoles in a changing climate in order to better capture the impact of important climate phenomena on the globe. To show the utility of finding dipoles using our approach, we show that the data driven dynamic climate indices generated from our algorithm generally perform better than static indices formed from the fixed locations used by climate scientists in terms of capturing impact on global temperature and precipitation. Our approach can generate a single snapshot picture of all the dipole interconnections on the globe in a given dataset and thus makes it possible to study the changes in dipole interactions and movements. As teleconnections are crucial in the understanding of the global climate system, there is a pressing need to better understand the behavior and interactions of these atmospheric processes as well as to capture them precisely. Our systematic graph-based approach to find the teleconnections in climate data is an attempt in that

关键词： graph algorithm teleconnections dipole discovery

来源：评论

学校读者我要写书评

暂无评论

Finding a maximum-weight induced k-partite subgraph of an i-triangulated graph

引用

DISCRETE APPLIED MATHEMATICS 2010年第7期158卷 765-770页

作者： Addario-Berry, Louigi Kennedy, W. S. King, Andrew D. Li, Zhentao Reed, Bruce McGill Univ Sch Comp Sci Montreal PQ Canada

An i-triangulated graph is a graph in which every odd cycle has two non-crossing chords;i-triangulated graphs form a subfamily of perfect graphs. A slightly more general family of perfect graphs are clique-separable graphs. A graph is clique-separable precisely if every induced subgraph either has a clique cutset, or is a complete multipartite graph or a clique joined to an arbitrary bipartite graph. We exhibit a polynomial time algorithm for finding a maximum-weight induced k-partite subgraph of an i-triangulated graph, and show that the problem of finding a maximum-size bipartite induced subgraph in a clique-separable graph is NP-complete. (c) 2008 Elsevier B.V. All rights reserved.

关键词： graph algorithm Clique-separable graph i-triangulated graph Tree decomposition

来源：评论

学校读者我要写书评

暂无评论

The minimum vulnerability problem on specific graph classes

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2016年第4期32卷 1288-1304页

作者： Aoki, Yusuke Halldorsson, Bjarni V. Halldorsson, Magnus M. Ito, Takehiro Konrad, Christian Zhou, Xiao Tohoku Univ Grad Sch Informat Sci Aoba Yama 6-6-05 Sendai Miyagi 9808579 Japan JST CREST 4-1-8 Honcho Kawaguchi Saitama 3320012 Japan Reykjavik Univ Sch Comp Sci Menntavegi 1 IS-101 Reykjavik Iceland

Suppose that each edge e of an undirected graph G is associated with three nonnegative integers , and , called the cost, vulnerability and capacity of e, respectively. Then, we consider the problem of finding paths in G between two prescribed vertices with the minimum total cost;each edge e can be shared without any cost by at most paths, and can be shared by more than paths if we pay , but cannot be shared by more than paths even if we pay the cost for e. This problem generalizes the disjoint path problem, the minimum shared edges problem and the minimum edge cost flow problem for undirected graphs, and it is known to be NP-hard. In this paper, we study the problem from the viewpoint of specific graph classes, and give three results. We first show that the problem is NP-hard even for bipartite outerplanar graphs, 2-trees, graphs with pathwidth two, complete bipartite graphs, and complete graphs. We then give a pseudo-polynomial-time algorithm for bounded treewidth graphs. Finally, we give a fixed-parameter algorithm for chordal graphs when parameterized by the number of required paths.

关键词： Bounded treewidth graph Chordal graph Fixed parameter tractability graph algorithm Minimum vulnerability problem

来源：评论

学校读者我要写书评

暂无评论

Reconfiguration of cliques in a graph

引用

DISCRETE APPLIED MATHEMATICS 2023年第1期333卷 43-58页

作者： Ito, Takehiro Ono, Hirotaka Otachi, Yota Tohoku Univ Grad Sch Informat Sci 6-3-09 AobaAramaki Aza Aoba Ku Sendai 9808579 Japan Nagoya Univ Grad Sch Informat FurochoChikusa Ku Nagoya 4648601 Japan

We study reconfiguration problems for cliques in a graph, which determine whether there exists a sequence of cliques that transforms a given clique into another one in a step-by-step fashion. As one step of a transformation, we consider three different types of rules, which are defined and studied in reconfiguration problems for independent sets. We first prove that all the three rules are equivalent in cliques from the viewpoint of polynomial-time solvability. We then show that the problems are PSPACE-complete for perfect graphs, while we give polynomial-time algorithms for several classes of graphs, such as even-hole-free graphs and cographs. Furthermore, we show that the shortest variant, which computes the shortest length of a desired sequence, can be solved in polynomial time for chordal graphs, bipartite graphs, planar graphs, and bounded treewidth graphs. (c) 2023 Elsevier B.V. All rights reserved.

关键词： Combinatorial reconfiguration graph algorithm Clique

来源：评论

学校读者我要写书评

暂无评论

A TOPOLOGICAL APPROACH TO DYNAMIC graph CONNECTIVITY

引用

INFORMATION PROCESSING LETTERS 1987年第1期25卷 65-70页

作者： REIF, JH HARVARD UNIV DIV APPL SCIAIKEN COMPUTAT LABCAMBRIDGEMA 02138

A dynamic connectivity problem consists of an initial graph, and a sequence of operations consisting of graph modifications and graph connectivity tests. The size n of the problem is the sum of the maximum number of vertices and edges of the derived graph, plus the number of operations to be executed. Each graph modification is a deletion of either an edge or an isolated vertex. Each graph connectivity test is to determine if there exists a path in the current graph between two given vertices (the vertices can vary for distinct tests). The best previously known time for this dynamic connectivity problem was Ω(n 2 ). Our main result is an O(ng+n log n) time algorithm for the dynamic connectivity problem in the case of the maximum genus of the derived graph being g.

关键词： graph algorithm connectivity dynamic algorithm planar graph

来源：评论

学校读者我要写书评

暂无评论

FAST, EFFICIENT PARALLEL algorithmS FOR SOME graph PROBLEMS: 收藏
分享
引用; SIAM JOURNAL ON COMPUTING 1981年第4期10卷 682-691页; 作者： SAVAGE, C JAJA, J UNIV ILLINOIS URBANAIL 61801 UNIV TEXAS ARLINGTONTX 76019 PENN STATE UNIV DEPT COMP SCIUNIVERSITY PKPA 16802; algorithms for solving graph problems on an unbounded parallel model of computation are considered. Parallel algorithms of time complexity O(log2; algorithms for solving graph problems on an unbounded parallel model of computation are considered. Parallel algorithms of time complexity $O (\log^{2} n)$; 关键词： parallel algorithm graph algorithm minimum spanning tree biconnected component bridge fundamental cycle computational complexity graph theory multiprocessing; 来源：评论; 学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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