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

Approximating optimum branchings in linear time

INFORMATION PROCESSING LETTERS 2009年第3期109卷 175-178页

作者： Ziegler, Valentin Humboldt Univ Inst Informat D-10099 Berlin Germany

We prove that maximum weight branchings in directed graphs can be approximated in time O(m) tip to a factor of 1 - epsilon. where epsilon > 0 is an arbitrary constant. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Approximation algorithm graph algorithm Branching

来源：评论

学校读者我要写书评

暂无评论

AN IMPROVED algorithm FOR HIERARCHICAL-CLUSTERING USING STRONG COMPONENTS

引用

INFORMATION PROCESSING LETTERS 1983年第1期17卷 37-41页

作者： TARJAN, RE Bell Laboratories Murray Hill NJ 07974 U.S.A.

Tarjan (1982) proposed a time algorithm for computing decomposition trees. That algorithm achieved its speed by combining 3 techniques: 1. the O(m) time algorithm for locating strong components, 2. divide-and-conquer, and 3. binary search. A simpler algorithm with a faster O(m log n) running time is presented. The simplification is obtained by dropping the use of binary search; the improved running time bound is obtained from a more careful analysis. It is also shown that the problems of sorting and of computing a minimum spanning tree in an undirected graph are linear-time reducible to the decomposition tree problem.

关键词： Cluster analysis divide-and-conquer graph algorithm hierarchical decomposition strong components

来源：评论

学校读者我要写书评

暂无评论

AN OPTIMAL algorithm FOR SINK-FINDING

引用

INFORMATION PROCESSING LETTERS 1982年第3期14卷 109-111页

作者： KING, KN SMITHTHOMAS, B School of Information and Computer Science Georgia Institute of Technology Atlanta GA 30332 U.S.A.

The problem of sink-finding in a directed graph represented by an adjacency matrix, was first introduced as a counterexample to an early version of the Anderaa-Rosenberg (1973) conjecture, which stated that, for P a ''natural'' property of graphs, the problem of ascertaining whether P holds for a graph with n vertices, represented by its adjacency matrix, necessitates the examination of 0(n2) matrix entries in the worst case. Anderaa disproved this conjecture by demonstrating that sink-finding can be accomplished using only about 3n matrix accesses. The problem of ascertaining whether a graph has a sink utilizing only 0(n) matrix accesses has since been introduced as an exercise in 2 texts on algorithms. Although it is not difficult to construct an algorithm that performs at most 3n-4 matrix accesses, this algorithm is not optimal. It is demonstrated that the optimal number of matrix accesses is actually 3n-(log n)-3.

关键词： graph algorithm sink Anderaa-Rosenberg conjecture tournament oracle

来源：评论

学校读者我要写书评

暂无评论

graph BLAST: A High-Performance Linear Algebra-based graph Framework on the GPU

引用

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE 2022年第1期48卷 1-1页

作者： Yang, Carl Buluc, Aydin Owens, John D. Univ Calif Davis 1 Shields Ave Davis CA 95616 USA Lawrence Berkeley Natl Lab Dept Elect & Comp Engn 1 Shields Ave Davis CA 95616 USA Lawrence Berkeley Natl Lab 1 Cyclotron Rd Berkeley CA 94720 USA Univ Calif Berkeley 1 Cyclotron Rd Berkeley CA 94720 USA Univ Calif Davis Dept Elect & Comp Engn 1 Shields Ave Davis CA 95616 USA

High-performance implementations of graph algorithms are challenging to implement on new parallel hardware such as GPUs because of three challenges: (1) the difficulty of coming up with graph building blocks, (2) load imbalance on parallel hardware, and (3) graph problems having low arithmetic intensity. To address some of these challenges, graphBLAS is an innovative, on-going effort by the graph analytics community to propose building blocks based on sparse linear algebra, which allow graph algorithms to be expressed in a performant, succinct, composable, and portable manner. In this paper, we examine the performance challenges of a linear-algebra-based approach to building graph frameworks and describe new design principles for overcoming these bottlenecks. Among the new design principles is exploiting input sparsity, which allows users to write graph algorithms without specifying push and pull direction. Exploiting output sparsity allows users to tell the backend which values of the output in a single vectorized computation they do not want computed. Load-balancing is an important feature for balancing work amongst parallel workers. We describe the important load-balancing features for handling graphs with different characteristics. The design principles described in this paper have been implemented in "graphBLAST", the first high-performance linear algebra-based graph framework on NVIDIA GPUs that is open-source. The results show that on a single GPU, graphBLAST has on average at least an order of magnitude speedup over previous graphBLAS implementations SuiteSparse and GBTL, comparable performance to the fastest GPU hardwired primitives and shared-memory graph frameworks Ligra and Gunrock, and better performance than any other GPU graph framework, while offering a simpler and more concise programming model.

关键词： graph algorithm GPU sparse linear algebra matrix multiply

来源：评论

学校读者我要写书评

暂无评论

algorithms for GA-H reduced graphs

引用

JOURNAL OF DISCRETE algorithmS 2015年 35卷 17-26页

作者： Gavril, Fanica Technion Dept Comp Sci IL-32000 Haifa Israel

Let GA be a hereditary family of graphs and Ha hereditary family of acyclically directed family of graphs. A graph G(V, E) is a GA-H reduced graph if it can be obtained from a graph GA(V, D) is an element of GA by deleting the edges of an edge subgraph H(V, E') is an element of H. The GA-H reduced graphs are a generalization of the complements of the H-mixed graphs. Examples of such families of GA-H reduced graphs are the interval filament graphs, the subtree filament graphs, the circular-arc filament graphs, the cactus subtree filament graphs, the 3D-interval-filament graphs and the subgraph overlap graphs. We describe polynomial time algorithms for various problems on GA-H reduced graphs, when the families GA and H have specific properties. The algorithms are to find maximum independent sets, maximum K-packings, maximum cliques, maximum induced complete bipartite subgraphs, maximum weight holes of a given parity and antiholes of a given parity. (C) 2015 Elsevier B.V. All rights reserved.

关键词： graph algorithm GA-H reduced graph H-mixed graph Subgraph overlap graph Subtree filament graph Maximum independent set

来源：评论

学校读者我要写书评

暂无评论

Use of reconstituted metabolic networks to assist in metabolomic data visualization and mining

引用

METABOLOMICS 2010年第2期6卷 312-321页

作者： Jourdan, Fabien Cottret, Ludovic Huc, Laurence Wildridge, David Scheltema, Richard Hillenweck, Anne Barrett, Michael P. Zalko, Daniel Watson, David G. Debrauwer, Laurent Xenobiot INRA ENVT UMR1089 F-31000 Toulouse 3 France Univ Glasgow Div Infect & Immun Glasgow Biomed Res Ctr Glasgow Lanark Scotland Univ Glasgow Wellcome Trust Ctr Mol Parasitol Glasgow Biomed Res Ctr Glasgow Lanark Scotland Univ Groningen Groningen Bioinformat Ctr Groningen Netherlands Univ Strathclyde Strathclyde Inst Pharm & Biomed Sci Glasgow Lanark Scotland

Metabolomics experiments seldom achieve their aim of comprehensively covering the entire metabolome. However, important information can be gleaned even from sparse datasets, which can be facilitated by placing the results within the context of known metabolic networks. Here we present a method that allows the automatic assignment of identified metabolites to positions within known metabolic networks, and, furthermore, allows automated extraction of sub-networks of biological significance. This latter feature is possible by use of a gap-filling algorithm. The utility of the algorithm in reconstructing and mining of metabolomics data is shown on two independent datasets generated with LC-MS LTQ-Orbitrap mass spectrometry. Biologically relevant metabolic sub-networks were extracted from both datasets. Moreover, a number of metabolites, whose presence eluded automatic selection within mass spectra, could be identified retrospectively by virtue of their inferred presence through gap filling.

关键词： Metabolic network graph algorithm Gap-filling Metabolomics

来源：评论

学校读者我要写书评

暂无评论

Greedy approximation for the source location problem with vertex-connectivity requirements in undirected graphs

引用

JOURNAL OF DISCRETE algorithmS 2009年第4期7卷 570-578页

作者： Ishii, Toshimasa Otaru Univ Dept Informat & Management Sci Otaru Hokkaido 0478501 Japan

Let G = (V, E) be a simple undirected graph with a set V of vertices and a set E of edges. Each vertex v is an element of V has a demand d(v) is an element of Z(+), and a cost c(v) is an element of R+, where Z(+) and R+ denote the set of nonnegative integers and the set of nonnegative reals, respectively. The source location problem with vertex-connectivity requirements in a given graph G asks to find a set S of vertices minimizing Sigma(v is an element of S) c(v) such that there are at least d(v) pairwise vertex-disjoint paths from S to v for each vertex v is an element of V-S. It is known that the problem is not approximable within a ratio of O(ln Sigma(v is an element of V) d(v)), unless NP has an O(N-loglogN)-time deterministic algorithm. Also, it is known that even if every vertex has a uniform cost and d* = 4 holds, then the problem is NP-hard, where d* = max{d(v) vertical bar v is an element of V}. In this paper, we consider the problem in the case where every vertex has uniform cost. We propose a simple greedy algorithm for providing a max{d*, 2d* - 6}-approximate solution to the problem in O(min{d*, root vertical bar V vertical bar d*vertical bar V vertical bar(2)) time, while we also show that there exists an instance for which it provides no better than a (d* - 1)-approximate solution. Especially, in the case of d* <= 4, we give a tight analysis to show that it achieves an approximation ratio of 3. We also show the APX-hardness of the problem even restricted to d* <= 4. (C) 2009 Elsevier B.V. All rights reserved.

关键词： graph algorithm Greedy algorithm Undirected graph Location problem Vertex-connectivity

来源：评论

学校读者我要写书评

暂无评论

Extracting research communities from bibliographic data

引用

INTERNATIONAL JOURNAL OF KNOWLEDGE-BASED AND INTELLIGENT ENGINEERING SYSTEMS 2012年第1期16卷 25-34页

作者： Nakamura, Yushi Horiike, Toshihiko Kuboyama, Tetsuji Sakamoto, Hiroshi Kyushu Inst Technol 680-4 Kawazu Iizuka Fukuoka 8208502 Japan Gakushuin Univ Tokyo Japan JST PRESTO Kawaguchi Saitama Japan

We develop a research community extraction algorithm from large bibliographic data, which was preliminarily reported in Horiike et al. [10] and Nakamura et al. [18]. A research community in bibliographic data is considered to be a set of the linked texts holding a common topic, in other words, it is a dense subgraph embedded in the directed graph. Our method is based on the maximum flow algorithm for finding web communities by Flake et al. [5]. We propose improvements of the algorithm to select community nodes and initial seeds taking account of the restriction that any directed graph is acyclic. We examine the improved algorithm for the list of keywords frequently appearing in the bibliographic data. In addition we propose a simple method to extract characteristic keywords for deciding initial seed nodes. This method is also evaluated by experiments.

关键词： Community extraction graph algorithm information extraction

来源：评论

学校读者我要写书评

暂无评论

TREE SPANNERS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 1995年第3期8卷 359-387页

作者： CAI, LZ CORNEIL, DG UNIV TORONTO DEPT COMP SCITORONTOON M5S 1A4CANADA

A tree t-spanner T of a graph G is a spanning tree in which the distance between every pair of vertices is at most t times their distance in G. This notion is motivated by applications in communication networks, distributed systems, and network design. This paper studies graph-theoretic, algorithmic, and complexity issues about tree spanners. It is shown that a tree 1-spanner, if it exists, in a weighted graph with m edges and n vertices is a minimum spanning tree and can be found in O(m log beta(m, n)) time, where beta(m, n) = min{iota\log((iota)) n less than or equal to m/n}. On the other hand, for any fixed t > 1, the problem of determining the existence of a tree t-spanner in a weighted graph is proven to be NP-complete. For unweighted graphs, it is shown that constructing a tree t-spanner takes linear time, whereas determining the existence of a tree t-spanner is NP-complete for any fixed t greater than or equal to 4. A theorem that captures the structure of tree 2-spanners is presented for unweighted graphs. For digraphs, an O((m + n)alpha(m, n)) algorithm is provided for finding a tree t-spanner with t as small as possible, where alpha(m, n) is a functional inverse of Ackerman's function. The results for tree spanners on undirected graphs are extended to ''quasi-tree spanners'' on digraphs. Furthermore, linear-time algorithms are derived for verifying tree spanners and quasi-tree spanners.

关键词： graph algorithm NP-COMPLETE TREE SPANNER SPANNING TREE DISTANCE

来源：评论

学校读者我要写书评

暂无评论

Finding Islands on Encrypted graphs 31

Finding Islands on Encrypted Graphs

引用

31st IEEE Conference on Signal Processing and Communications Applications (SIU)

作者： Acir, Berker Onur, Ertan Onur, Cansu Betin ODTU Bilgisayar Muhendisligi Bolumu Ankara Turkiye ODTU Kriptografi Bolumu Uygulamali Matemat Enstitusu Ankara Turkiye Univ Waterloo David R Cheriton Sch Comp Sci Waterloo ON Canada

ISBN: (纸本)9798350343557

Cloud computing services have found widespread use recently. Offloading computations to public clouds has many benefits albeit harming the privacy of users and data. Homomorphic encryption facilitates cloud computing services that can do computations over encrypted data without requiring decryption and this enables privacy-preserving applications. In this paper, we propose an approach for confidentially finding islands (connected components) in a graph. We present various performance evaluation results and show that privacy-preservation can be achieved with a cost of computation overhead.

关键词： connected components graph algorithm homomorphic encryption privacy preservation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：