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

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

来源：评论

学校读者我要写书评

暂无评论

A Quadratic Vertex Kernel for Feedback Arc Set in Bipartite Tournaments

A Quadratic Vertex Kernel for Feedback Arc Set in Bipartite ...

引用

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 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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

POLARITYSPAM: PROPAGATING CONTENT-BASED INFORMATION THROUGH A WEB-graph TO DETECT WEB-SPAM

引用

INTERNATIONAL JOURNAL OF INNOVATIVE COMPUTING INFORMATION AND CONTROL 2012年第4期8卷 2915-2928页

作者： Javier Ortega, F. Troyano, Jose A. Cruz, Fermin L. Vallejo, Carlos G. Univ Seville Dept Languages & Comp Syst E-41012 Seville Spain

Spam web pages have become a problem for Information Retrieval systems due to he negative effects that this phenomenon can cause in their results. In this work we tackle the problem of detecting these pages with a propagation algorithm that, taking as input a web graph, chooses a set of spam and not-spam web pages in order to spread their spam likelihood over the rest of the network. Thus we take advantage of the links between pages to obtain a ranking of pages according to their relevance and their span?, likelihood. Our intuition consists in giving a high reputation to those pages related to relevant ones, and giving a high spam likelihood to the pages linked to spam web pages. We introduce the novelty of including the content of the web pages in the computation of an a priori estimation of the spam likelihood of the pages, and propagate this information. Our graph-based algorithm computes two scores for each node in the graph. Intuitively, these values represent how bad or good (spam-like or not) is a web page, according to its textual content and its relations in the graph. The experimental results show that our method outperforms other techniques for spam detection.

关键词： Information retrieval Web spam detection graph algorithms PageRank Web search

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

UPPER BOUNDS FOR SORTING PERMUTATIONS WITH A TRANSPOSITION TREE (vol 5, 1350003, 2013)

引用

DISCRETE MATHEMATICS algorithms AND APPLICATIONS 2013年第3期5卷

作者： Chitturi, Bhadrachalam Amrita Vishwa Vidyapeetham Univ Dept Comp Sci Amritapuri CampusClappana PO Kollam 690525 Kerala India

An upper bound for sorting permutations with an operation estimates the diameter of the corresponding Cayley graph and an exact upper bound equals the diameter. Computing tight upper bounds for various operations is of theoretical and practical (e.g., interconnection networks, genetics) interest. Akers and Krishnamurthy gave a Ω(n! n 2 ) time method that examines n! permutations to compute an upper bound, f(Γ), to sort any permutation with a given transposition tree T, where Γ is the Cayley graph corresponding to T. We compute two intuitive upper bounds γ and δ′ each in O(n 2 ) time for the same, by working solely with the transposition tree. Recently, Ganesan computed β, an estimate of the exact upper bound for the same, in O(n 2 ) time. Our upper bounds are tighter than f(Γ) and β, on average and in most of the cases. For a class of trees, we prove that the new upper bounds are tighter than β and f(Γ).

关键词： Cayley graphs diameter graph algorithms greedy algorithms permutations sorting strings transposition trees upper bound

来源：评论

学校读者我要写书评

暂无评论

All-Pairs Shortest Paths for Unweighted Undirected graphs in o(mn) Time

引用

ACM TRANSACTIONS ON algorithms 2012年第4期8卷

作者： Chan, Timothy M. Univ Waterloo Sch Comp Sci Waterloo ON N2L 3G1 Canada

We revisit the all-pairs-shortest-paths problem for an unweighted undirected graph with n vertices and m edges. We present new algorithms with the following running times: { O(mn/log n) if m > n log n log log log n O(mn log log n/log n) if m> n log log n O(n2log2logn/logn) if m <= n log log n. These represent the best time bounds known for the problem for all m << n(1.376). We also obtain a similar type of result for the diameter problem for unweighted directed graphs.

关键词： algorithms Theory graph algorithms shortest paths word RAM

来源：评论

学校读者我要写书评

暂无评论

PARALLEL SPARSE MATRIX-MATRIX MULTIPLICATION AND INDEXING: IMPLEMENTATION AND EXPERIMENTS

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2012年第4期34卷 C170-C191页

作者： Buluc, Aydin Gilbert, John R. Univ Calif Berkeley Lawrence Berkeley Natl Lab Computat Res Div Berkeley CA 94720 USA Univ Calif Santa Barbara Dept Comp Sci Santa Barbara CA 93106 USA

Generalized sparse matrix-matrix multiplication (or SpGEMM) is a key primitive for many high performance graph algorithms as well as for some linear solvers, such as algebraic multigrid. Here we show that SpGEMM also yields efficient algorithms for general sparse-matrix indexing in distributed memory, provided that the underlying SpGEMM implementation is sufficiently flexible and scalable. We demonstrate that our parallel SpGEMM methods, which use two-dimensional block data distributions with serial hypersparse kernels, are indeed highly flexible, scalable, and memory-efficient in the general case. This algorithm is the first to yield increasing speedup on an unbounded number of processors;our experiments show scaling up to thousands of processors in a variety of test scenarios.

关键词： parallel computing numerical linear algebra sparse matrix-matrix multiplication SpGEMM sparse matrix indexing sparse matrix assignment two-dimensional data decomposition hypersparsity graph algorithms sparse SUMMA subgraph extraction graph contraction graph batch update

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：