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

37th International Symposium on Mathematical Foundations of Computer Science, (MFCS)

作者： Xiao, Mingyu Guo, Jiong Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu 610054 Peoples R China Univ Saarland D-66123 Saarbrucken Germany

ISBN: (纸本)9783642325892;9783642325885

The k-feedback arc set problem is to determine whether there is a set F of at most k arcs in a directed graph G such that the removal of F makes G acyclic. The k-feedback arc set problems in tournaments and bipartite tournaments (k-FAST and k-FASBT) have applications in ranking aggregation and have been extensively studied from the viewpoint of parameterized complexity. Recently, Misra et al. provide a problem kernel with O(k(3)) vertices for k-FASBT. Answering an open question by Misra et al., we improve the kernel bound to O(k(2)) vertices by introducing a new concept called "bimodule."

关键词： Kernelization Feedback arc set Bipartite tournament graph algorithms Parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

A Fast Algorithm for Streaming Betweenness Centrality

A Fast Algorithm for Streaming Betweenness Centrality

引用

ASE/IEEE International Conference on Privacy, Security, Risk and Trust / ASE/IEEE International Conference on Social Computing (SocialCom/PASSAT)

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

ISBN: (纸本)9780769548487;9781467356381

Analysis of social networks is challenging due to the rapid changes of its members and their relationships. For many cases it impractical to recompute the metric of interest, therefore, streaming algorithms are used to reduce the total runtime following modifications to the graph. Centrality is often used for determining the relative importance of a vertex or edge in a graph. The vertex Betweenness Centrality is the fraction of shortest paths going through a vertex among all shortest paths in the graph. Vertices with a high betweenness centrality are usually key players in a social network or a bottleneck in a communication network. Evaluating the betweenness centrality for a graph G = (V, E) is computationally demanding and the best known algorithm for unweighted graphs has an upper bound time complexity of O(V-2 + V E). Consequently, it is desirable to find a way to avoid a full re-computation of betweenness centrality when a new edge is inserted into the graph. In this work, we give a novel algorithm that reduces computation for the insertion of an edge into the graph. This is the first algorithm for the computation of betweenness centrality in a streaming graph. While the upper bound time complexity of the new algorithm is the same as the upper bound for the static graph algorithm, we show significant speedups for both synthetic and real graphs. For synthetic graphs the speedup varies depending on the type of graph and the graph size. For synthetic graphs with 16384 vertices the average speedup is between 100X - 400X. For five different real world collaboration networks the average speedup per graph is in range of 36X - 148X.

关键词： graph algorithms social networks

来源：评论

学校读者我要写书评

暂无评论

LP can be a cure for Parameterized Problems

LP can be a cure for Parameterized Problems

引用

29th International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Narayanaswamy, N. S. Raman, Venkatesh Ramanujan, M. S. Saurabh, Saket IIT Madras Dept Comp Sci & Engn Chennai Tamil Nadu India Inst Math Sci Chennai 600113 Tamil Nadu India

ISBN: (纸本)9783939897354

We investigate the parameterized complexity of VERTEX COVER parameterized above the optimum value of the linear programming (LP) relaxation of the integer linear programming formulation of the problem. By carefully analyzing the change in the LP value in the branching steps, we argue that even the most straightforward branching algorithm (after some preprocessing) results in an O*(2.6181(r)) algorithm for the problem where r is the excess of the vertex cover size over the LP optimum. We write O*(f(k)) for a time complexity of the form O(f(k)n(O(1))), where f(k) grows exponentially with k. Then, using known and new reductions, we give O*(2.6181(k)) algorithms for the parameterized versions of ABOVE GUARANTEE VERTEX COVER, ODD CYCLE TRANSVERSAL, SPLIT VERTEX DELETION AND ALMOST 2-SAT, and an O*(1.6181(k)) algorithm for KONIG VERTEX DELETION, VERTEX COVER PARAM BY OCT and VERTEX COVER PARAM BY KVD. These algorithms significantly improve the best known bounds for these problems. The notable improvement is the bound for ODD CYCLE TRANSVERSAL for which this is the first major improvement after the first algorithm that showed it fixed-parameter tractable in 2003. We also observe that using our algorithm, one can obtain a simple kernel for the classical vertex cover problem with at most 2k - O(log k) vertices.

关键词： algorithms and data structures graph algorithms Parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Analyzing Patterns in Large-Scale graphs Using MapReduce in Hadoop

Analyzing Patterns in Large-Scale Graphs Using MapReduce in ...

引用

25th ACM/IEEE International Conference for High Performance Computing, Networking, Storage and Analysis (SC)

作者： Schultz, Joshua Vieyra, Jonathan Lu, Enyue Salisbury Univ Dept Math & Comp Sci Salisbury CT USA

ISBN: (纸本)9780769549569;9781467362184

Analyzing patterns in large-scale graphs, such as social networks (e.g. Facebook, Linkedin, Twitter) has many applications including community identification, blog analysis, intrusion and spamming detections. Currently, it is impossible to process information in large-scale graphs with millions even billions of edges with a single computer. In this paper, we take advantage of MapReduce, a programming model for processing large datasets, to detect important graph patterns using open source Hadoop on Amazon EC2. The aim of this paper is to show how MapReduce cloud computing with the application of graph pattern detection scales on real world data. We implement Cohen's MapReduce graph algorithms to enumerate patterns including triangles, rectangles, trusses and barycentric clusters using real world data taken from Snap Stanford. In addition, we create a visualization algorithm to visualize the detected graph patterns. The performance of MapReduce graph algorithms has been discussed too. © 2012 IEEE.

关键词： Cloud Computing Cohesive Components graph algorithms MapReduce Pattern Detection

来源：评论

学校读者我要写书评

暂无评论

Sensitive detection of pathway perturbations in cancers

Sensitive detection of pathway perturbations in cancers

引用

ACM Conference on Bioinformatics, Computational Biology and Biomedicine (ACM-BCB)

作者： Rivera, Corban G. Tyler, Brett M. Murali, T. M. Virginia Tech Dept Comp Sci Blacksburg VA 24061 USA Virginia Tech Virginia Bioinformat Inst Blacksburg VA USA Virginia Tech ICTAS Ctr Syst Biol Engn Tissues Blacksburg VA USA Johns Hopkins Univ Dept Biomed Engn Baltimore MD 21218 USA

ISBN: (纸本)9781450307963

Background: The normal functioning of a living cell is characterized by complex interaction networks involving many different types of molecules. Associations detected between diseases and perturbations in well-defined pathways within such interaction networks have the potential to illuminate the molecular mechanisms underlying disease progression and response to treatment. Results: In this paper, we present a computational method that compares expression profiles of genes in cancer samples to samples from normal tissues in order to detect perturbations of pre-defined pathways in the cancer. In contrast to many previous methods, our scoring function approach explicitly takes into account the interactions between the gene products in a pathway. Moreover, we compute the sub-pathway that has the highest score, as opposed to merely computing the score for the entire pathway. We use a permutation test to assess the statistical significance of the most perturbed sub-pathway. We apply our method to 20 pathways in the Netpath database and to the Global Cancer Map of gene expression in 18 cancers. We demonstrate that our method yields more sensitive results than alternatives that do not consider interactions or measure the perturbation of a pathway as a whole. We perform a sensitivity analysis to show that our approach is robust to modest changes in the input data. Our method confirms numerous well-known connections between pathways and cancers. Conclusions: Our results indicate that integrating differential gene expression with the interaction structure in a pathway is a powerful approach for detecting links between a cancer and the pathways perturbed in it. Our results also suggest that even well-studied pathways may be perturbed only partially in any given cancer. Further analysis of cancer-specific sub-pathways may shed new light on the similarities and differences between cancers.

关键词： Cancers Gene expression graph algorithms Pathway perturbation Pathways Simulated annealing

来源：评论

学校读者我要写书评

暂无评论

A GPU Implementation of Inclusion-based Points-to Analysis 12

A GPU Implementation of Inclusion-based Points-to Analysis

引用

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

作者： Mendez-Lojo, Mario Burtscher, Martin Pingali, Keshav Univ Texas Austin Inst Computat Engn & Sci Austin TX 78712 USA Texas State Univ Dept Comp Sci San Marcos TX USA Univ Texas Austin Dept Comp Sci Austin TX 78712 USA

ISBN: (纸本)9781450311601

graphics Processing Units (GPUs) have emerged as powerful accelerators for many regular algorithms that operate on dense arrays and matrices. In contrast, we know relatively little about using GPUs to accelerate highly irregular algorithms that operate on pointer-based data structures such as graphs. For the most part, research has focused on GPU implementations of graph analysis algorithms that do not modify the structure of the graph, such as algorithms for breadth-first search and strongly-connected components. In this paper, we describe a high-performance GPU implementation of an important graph algorithm used in compilers such as gcc and LLVM: Andersen-style inclusion-based points-to analysis. This algorithm is challenging to parallelize effectively on GPUs because it makes extensive modifications to the structure of the underlying graph and performs relatively little computation. In spite of this, our program, when executed on a 14 Streaming Multiprocessor GPU, achieves an average speedup of 7x compared to a sequential CPU implementation and outperforms a parallel implementation of the same algorithm running on 16 CPU cores. Our implementation provides general insights into how to produce high-performance GPU implementations of graph algorithms, and it highlights key differences between optimizing parallel programs for multicore CPUs and for GPUs.

关键词： algorithms Languages Performance Inclusion-based Points-to Analysis Irregular Programs graph algorithms GPU CUDA

来源：评论

学校读者我要写书评

暂无评论

ACYCLIC MATCHINGS IN SUBCLASSES OF BIPARTITE graphS

引用

DISCRETE MATHEMATICS algorithms AND APPLICATIONS 2012年第4期4卷 1250050页

作者： Panda, B. S. Pradhan, D. Indian Inst Technol Dept Math Comp Sci & Applicat Grp New Delhi 110016 India

A set M subset of E is called an acyclic matching of a graph G = (V, E) if no two edges in M are adjacent and the subgraph induced by the set of end vertices of the edges of M is acyclic. Given a positive integer k and a graph G = (V, E), the acyclic matching problem is to decide whether G has an acyclic matching of cardinality at least k. Goddard et al. (Discrete Math. 293(1-3) (2005) 129-138) introduced the concept of the acyclic matching problem and proved that the acyclic matching problem is NP-complete for general graphs. In this paper, we propose an O(n + m) time algorithm to find a maximum cardinality acyclic matching in a chain graph having n vertices and m edges and obtain an expression for the number of maximum cardinality acyclic matchings in a chain graph. We also propose a dynamic programming-based O(n+ m) time algorithm to find a maximum cardinality acyclic matching in a bipartite permutation graph having n vertices and m edges. Finally, we strengthen the complexity result of the acyclic matching problem by showing that this problem remains NP-complete for perfect elimination bipartite graphs.

关键词： graph algorithms acyclic matching chain graphs bipartite permutation graphs perfect elimination bipartite graphs NP-complete

来源：评论

学校读者我要写书评

暂无评论

Internally Deterministic Parallel algorithms Can Be Fast 12

Internally Deterministic Parallel Algorithms Can Be Fast

引用

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

作者： Blelloch, Guy E. Fineman, Jeremy T. Gibbons, Phillip B. Shun, Julian Carnegie Mellon Univ Pittsburgh PA 15213 USA Georgetown Univ Pittsburgh PA USA Intel Labs Pittsburgh PA USA

ISBN: (纸本)9781450311601

The virtues of deterministic parallelism have been argued for decades and many forms of deterministic parallelism have been described and analyzed. Here we are concerned with one of the strongest forms, requiring that for any input there is a unique dependence graph representing a trace of the computation annotated with every operation and value. This has been referred to as internal determinism, and implies a sequential semantics-i.e., considering any sequential traversal of the dependence graph is sufficient for analyzing the correctness of the code. In addition to returning deterministic results, internal determinism has many advantages including ease of reasoning about the code, ease of verifying correctness, ease of debugging, ease of defining invariants, ease of defining good coverage for testing, and ease of formally, informally and experimentally reasoning about performance. On the other hand one needs to consider the possible downsides of determinism, which might include making algorithms (i) more complicated, unnatural or special purpose and/or (ii) slower or less scalable. In this paper we study the effectiveness of this strong form of determinism through a broad set of benchmark problems. Our main contribution is to demonstrate that for this wide body of problems, there exist efficient internally deterministic algorithms, and moreover that these algorithms are natural to reason about and not complicated to code. We leverage an approach to determinism suggested by Steele (1990), which is to use nested parallelism with commutative operations. Our algorithms apply several diverse programming paradigms that fit within the model including (i) a strict functional style (no shared state among concurrent operations), (ii) an approach we refer to as deterministic reservations, and (iii) the use of commutative, linearizable operations on data structures. We describe algorithms for the benchmark problems that use these deterministic approaches and present performan

关键词： algorithms Experimentation Performance Parallel algorithms deterministic parallelism parallel programming commutative operations graph algorithms geometry algorithms sorting string processing

来源：评论

学校读者我要写书评

暂无评论

FlexBFS: A Parallelism-aware Implementation of Breadth-First Search on GPU 12

FlexBFS: A Parallelism-aware Implementation of Breadth-First...

引用

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

作者： Liu, Gu An, Hong Han, Wenting Li, Xiaoqiang Sun, Tao Zhou, Wei Wei, Xuechao Tang, Xulong Univ Sci & Technol China Sch Comp Sci & Technol Beijing Peoples R China

ISBN: (纸本)9781450311601

In this paper, we present FlexBFS, a parallelism-aware implementation for breadth-first search on GPU. Our implementation can adjust the computation resources according to the feedback of available parallelism dynamically. We also optimized our program in three ways: (1) a simplified two-level queue management,(2) a combined kernel strategy and (3) a high-degree vertices specialization approach. Our experimental results show that it can achieve 3 similar to 20 times speedup against the fastest serial version, and can outperform the TBB based multi-threading CPU version and the previous most effective GPU version on all types of input graphs.

关键词： algorithms Performance graph algorithms Breadth-first Search CUDA GPGPU

来源：评论

学校读者我要写书评

暂无评论

Replacement Paths and k Simple Shortest Paths in Unweighted Directed graphs

引用

ACM TRANSACTIONS ON algorithms 2012年第4期8卷 33-33页

作者： Roditty, Liam Zwick, Uri Bar Ilan Univ Dept Comp Sci IL-52900 Ramat Gan Israel Tel Aviv Univ Dept Comp Sci IL-69978 Tel Aviv Israel

Let G = (V, E) be a directed graph and let P be a shortest path from s to t in G. In the replacement paths problem, we are required to find, for every edge e on P, a shortest path from s to t in G that avoids e. The only known algorithm for solving the problem, even for unweighted directed graphs, is the trivial algorithm in which each edge on the path, in its turn, is excluded from the graph and a shortest paths tree is computed from s. The running time is O(mn + n(2) log n). The replacement paths problem is strongly motivated by two different applications: (1) The fastest algorithm to compute the k simple shortest paths between s and t in directed graphs [Yen 1971;Lawler 1972] computes the replacement paths between s and t. Its running time is O(mnk). (2) The replacement paths problem is used to compute the Vickrey pricing of edges in a distributed network. It was raised as an open problem by Nisan and Ronen [2001] whether it is possible to compute the Vickrey pricing faster than n computations of a shortest paths tree. In this article we present the first nontrivial algorithm for computing replacement paths in unweighted directed graphs (and in graphs with small integer weights). Our algorithm is Monte-Carlo and its running time is O(m root n). This result immediately improves the running time of the two applications mentioned above in a factor of root n. We also show how to reduce the problem of computing k simple shortest paths between s and t to O(k) computations of a second simple shortest path from s to t each time in a different subgraph of G. The importance of this result is that computing a second simple shortest path may turn out to be an easier problem than computing the replacement paths, thus, we can focus our efforts to improve the k simple shortest paths algorithm in obtaining a faster algorithm for the second shortest path problem.

关键词： algorithms Theory graph algorithms shortest paths k simple shortest paths

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：