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

Computing bounded-degree phylogenetic roots of disconnected graphs

30th International Workshop on graph-Theoretic Concepts in Computer Science

作者： Chen, Zhi-Zhong Tsukiji, Tatsuie Tokyo Denki Univ Dept Math Sci Hatoyama Saitama 3500394 Japan Tokyo Denki Univ Dept Informat Sci Hatoyama Saitama 3500394 Japan

ISBN: (纸本)9783540241324

The Phylogenetic kth Root Problem (PRk) is the problem of finding a (phylogenetic) tree T from a given graph G = (V, E) such that (1) T has no degree-2 internal nodes, (2) the external nodes (i.e., leaves) of T are exactly the elements of V, and (3) (u, v) is an element of E if and only if the distance between it and v in tree T is at most k, where k is some fixed threshold k. Such a tree T, if exists. is called a phylogenetic kth root of graph G. The computational complexity of PRk is open, except for k <= 4. Recently, Chen et al. investigated PRk under a natural restriction that the maximum degree of the phylogenetic root is bounded from above by a constant. They presented a linear-time algorithm that determines if a given connected G has such a phylogenetic kth root, and if so. demonstrates one. In this paper, we supplement their work by presenting a linear-time algorithm for disconnected graphs. (c) 2005 Elsevier Inc. All rights reserved.

关键词： phylogeny phylogenetic root computational biology graph power tree power graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Distributed Triangle Counting algorithms in Simple graph Stream

Distributed Triangle Counting Algorithms in Simple Graph Str...

引用

International Conference on Parallel and Distributed Systems (ICPADS)

作者： Mengdi Yu Chao Song Jiqing Gu Ming Liu School of Computer Science and Engineering University of Electronic Science and Technology of China CHINA Big Data Research Center University of Electronic Science and Technology of China CHINA

ISBN: (纸本)9781728125848

Recently, the counting algorithm of local topology structures, such as triangles, has been widely used in social network analysis, recommendation systems, user portraits and other fields. At present, one-pass streaming algorithm for counting global and local triangles has been widely studied, and most researches focus on the single-machine streaming algorithm in a 'offline+batch processing' mode. However, researches on distributed online algorithm on multiple machines are still in its infancy, and this stage has not been thoroughly studied. In this paper, we investigate the triangle counting problem in large-scale simple undirected graphs whose edges arrive as a stream. We propose two distributed online streaming algorithms to estimate the global number of triangles, which are based on the current best performance sampling-based streaming algorithm. We mainly realize the reasonable partition of the graph stream, so that each worker independently estimates the number of triangles in a subgraph of the graph stream. Experimental results show that our algorithms reduce the estimation error and are several times more accurate than state-of-the-art streaming algorithms.

关键词： Approximate algorithm Distributed streaming algorithm graph algorithm graph stream Triangle counting algorithm Triangle graph algorithms algorithms Streaming streams Line graph

来源：评论

学校读者我要写书评

暂无评论

Performance Evaluation of Fault Tolerant Routing algorithm in Data Center Networks 7th

Performance Evaluation of Fault Tolerant Routing Algorithm i...

引用

7th International Symposium on Security and Privacy in Social Networks and Big Data, SocialSec 2021

作者： Liu, Ningning Fan, Weibei Fan, Jianxi Suzhou Vocational University Suzhou215104 China Nanjing University of Posts and Telecommunications Nanjing210003 China Soochow University Suzhou215031 China

ISBN: (纸本)9789811679124

Nowdays, the vigorous development of cloud computing technology has brought great changes to the development of the whole information industry. The traditional data center network topology construction method and the operation mechanism of the network layer control plane are solidified, which have been difficult to meet the increasing demand for high performance and high cost performance under the new situation. Researchers map the topology of the data center network to an undirected graph, and use graph algorithms to implement fault-tolerant routing in complex networks. However, the shortest path algorithm of some early graphs cannot be applied to all topological graphs. In this paper, we analyze the advantages and disadvantages of related algorithms, and propose a fault-tolerant routing algorithm for all networks, which can dynamically call different algorithms according to the current number of nodes and links. The experimental results show that it can effectively improve the accuracy and fault tolerance of the algorithm and reduce the consumption of time and memory. © 2021, Springer Nature Singapore Pte Ltd.

关键词： Data center network Fault tolerant routing graph algorithm Performance evaluation

来源：评论

学校读者我要写书评

暂无评论

A novel method for deployment of distributed network monitors

A novel method for deployment of distributed network monitor...

引用

4th International Conference on Information Management, Innovation Management and Industrial Engineering, ICIII 2011

作者： Ou, Peng Li, Zhishu Lin, Xun School of Computer Science Sichuan University Chengdu China School of Economic Information Engineering Southwest University of Finance and Economy Chengdu China

ISBN: (纸本)9780769545233

The requirement of increasing the deployment of a distributed monitoring system as the network expanding is becoming a new research focus. The problem is where to put those monitors and by how much to put. This paper analyses the monitors adding mechanism and present a novel algorithm for finding candidate locations for additional deployment in the network. The algorithm is based on Apriori search method that combines with the link weight change algorithm. We also develop the greedy algorithm with Group Betweenness Centrality(GBC) involved for the purpose of comparing. The result shows that the new algorithm need less additional monitors than greedy algorithm, thus is useful for network monitors deployment. © 2011 IEEE.

关键词： algorithm design and analysis Apriori search method Distributed System Educational institutions graph algorithm Greedy algorithms Group Betweenness Inference algorithms Measurement Monitoring Network Centrality Routing distributed monitoring system distri

来源：评论

学校读者我要写书评

暂无评论

MM-Width: Observations, algorithms and Approximations

MM-Width: Observations, Algorithms and Approximations

引用

作者： Sebastiaan F. A. M. Brouwer Utrecht University

学位级别：硕士

In this thesis we investigate maximum matching-width (MM-width) fur- ther. MM-width is a graph width parameter similar to treewidth, related to the number of maximum matchings made in an induced bipartite graph made from partitions over the vertices of a graph. We improve the link between the value of maximum matching-width and the value of treewidth of a graph to MM(G) ≤ tw(G). We also give a bounded dynamic programming algo- rithm BMMDP to calculate the MM-width of a graph exactly. In addition to the exact algorithm we look into approximating the MM-width of graphs from above by using optimization algorithms based on local search and evolutionary algorithms. In the thesis we also make general observations about maximum matching- width, investigate the MM-width of standard graphs and come up with a set of safe kernelization rules to improve the performance of our algorithms. We also use the link between maximum matching-width and the other width parameters, the MM-widths of standard graphs and widths found during run time to add upper and lower bounds to the exact algorithm.

关键词： maximum matching-width graph decomposition width parameter graph algorithm treewidth approximation

来源：评论

学校读者我要写书评

暂无评论

Evoluční resyntéza kombinačních obvodů

Evoluční resyntéza kombinačních obvodů

引用

作者： Kocnová, Jitka Brno University of Technology

Diplomová práce se zabývá resyntézou kombinačních obvodů pomocí evolučních principů. První část se zabývá logickou syntézou a jejími problémy,... 详细信息

Diplomová práce se zabývá resyntézou kombinačních obvodů pomocí evolučních principů. První část se zabývá logickou syntézou a jejími problémy, evoluční syntézou a výhodami evolučního přístupu, a taktéž jsou zmíněny některé existující syntézní nástroje. V druhé části jsou pak přiblíženy vybrané grafové algoritmy a jejich možné využití v navrhovaném programovém rozšíření pro vybraný syntézní nástroj. Zde je také popsán návrh rozšíření a jeho samotná implementace. Třetí část se zabývá testováním vzniklého rozšíření. Čtvrtou částí je závěr shrnující získané poznatky a dosažené výsledky.

关键词： kombinační obvod syntéza resyntéza evoluční syntéza evoluce řez graf grafový algoritmus combinational circuit synthesis resynthesis evolutional synthesis evolution cut graph graph algorithm Text

来源：评论

学校读者我要写书评

暂无评论

Workload prediction and balance for distributed reachability processing for large-scale attribute graphs

引用

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE 2018年第6期30卷

作者： Ho, Li-Yung Wu, Jan-Jan Liu, Pangfeng Acad Sinica Inst Informat Sci 128Sect 2Acad Rd Taipei 11529 Taiwan Natl Taiwan Univ Dept Comp Sci & Informat Engn 1Sect 4Roosevelt Rd Taipei 10617 Taiwan Acad Sinica Res Ctr Informat Technol 128Sect 2Acad Rd Taipei 11529 Taiwan Natl Taiwan Univ Grad Inst Networking & Multimedia 1Sect 4Roosevelt Rd Taipei 10617 Taiwan

Reachability query with label constraint in an attribute graph is one of the most fundamental and important operations in semantic network analysis. However, ever-growing graph size has resulted in intractable reachability problems on single machines. This work aims to devise efficient solutions for the reachability with label constraint problem in an attribute graph in a distributed environment. We focus on two issues in distributed processingdata locality and workload balancingsince data locality reduces communication overhead and workload balancing improves the efficiency of cluster use. We propose three novel techniques to address the two issues: (1) a partition replication method that improves data locality while conserving community property, (2) a workload-prediction method that accurately predicts machine workloads for a given quer, and (3) a workload balancing method that uses these predictions to shift partial workloads among machines to produce a balanced workload. Experimental results suggest that these techniques significantly improve performance and reduce total execution time by 40%.

关键词： attribute graph bulk synchronization distributed reachability graph algorithm workload balance workload prediction

来源：评论

学校读者我要写书评

暂无评论

Optimal Algebraic Breadth-First Search for Sparse graphs

引用

ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA 2021年第5期15卷 77-77页

作者： Burkhardt, Paul Natl Secur Agcy Res Directorate Ft George G Meade MD 20755 USA

There has been a rise in the popularity of algebraic methods for graph algorithms given the development of the graphBLAS library and other sparse matrix methods. An exemplar for these approaches is BreadthFirst Search (BFS). The algebraic BFS algorithm is simply a recurrence of matrix-vector multiplications with the n x n adjacency matrix, but the many redundant operations over nonzeros ultimately lead to suboptimal performance. Therefore an optimal algebraic BFS should be of keen interest especially if it is easily integrated with existing matrix methods. Current methods, notably in the graphBLAS, use a Sparse Matrix masked-Sparse Vector multiplication in which the input vector is kept in a sparse representation in each step of the BFS, and nonzeros in the vector are masked in subsequent steps. This has been an area of recent research in graphBLAS and other libraries. While in theory, these masking methods are asymptotically optimal on sparse graphs, many add work that leads to suboptimal runtime. We give a new optimal, algebraic BFS for sparse graphs, thus closing a gap in the literature. Our method multiplies progressively smaller submatrices of the adjacency matrix at each step. Let n and m refer to the number of vertices and edges, respectively. On a sparse graph, our method takes O(n) algebraic operations as opposed to O(m) operations needed by theoretically optimal sparse matrix approaches. Thus, for sparse graphs, it matches the bounds of the best-known sequential algorithm, and on a Parallel Random Access Machine, it is work-optimal. Our result holds for both directed and undirected graphs. Compared to a leading graphBLAS library, our method achieves up to 24x faster sequential time, and for parallel computation, it can be 17x faster on large graphs and 12x faster on large-diameter graphs.

关键词： Breadth-first search graph algorithm sparse matrix linear algebra

来源：评论

学校读者我要写书评

暂无评论

Orienting undirected phylogenetic networks

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2024年 140卷

作者： Huber, Katharina T. van Iersel, Leo Janssen, Remie Jones, Mark Moulton, Vincent Murakami, Yukihiro Semple, Charles Univ East Anglia Sch Comp Sci Norwich NR4 7TJ England Delft Univ Technol Delft Inst Appl Math Van Mourik Broekmanweg 6 NL-2628 XE Delft Netherlands Univ Canterbury Sch Math & Stat Private Bag 4800 Christchurch 8140 New Zealand

This paper studies the relationship between undirected (unrooted) and directed (rooted) phylogenetic networks. We describe a polynomial-time algorithm for deciding whether an undirected nonbinary phylogenetic network, given the locations of the root and reticulation vertices, can be oriented as a directed nonbinary phylogenetic network. Moreover, we characterize when this is possible and show that, in such instances, the resulting directed nonbinary phylogenetic network is unique. In addition, without being given the location of the root and the reticulation vertices, we describe an algorithm for deciding whether an undirected binary phylogenetic network N can be oriented as a directed binary phylogenetic network of a certain class. The algorithm is fixed-parameter tractable (FPT) when the parameter is the level of N and is applicable to classes of directed phylogenetic networks that satisfy certain conditions. As an example, we show that the well-studied class of binary tree-child networks satisfies these conditions.(c) 2023 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).

关键词： Phylogenetic network graph orientation graph algorithm Fixed-parameter tractability Polynomial-time algorithm Characterization Computational biology Phylogenetics

来源：评论

学校读者我要写书评

暂无评论

Burnability of double spiders and path forests

引用

APPLIED MATHEMATICS AND COMPUTATION 2023年 438卷

作者： Tan, Ta Sheng Teh, Wen Chean Univ Malaya Inst Math Sci Fac Sci Kuala Lumpur 50603 Malaysia Univ Sains Malaysia USM Sch Math Sci George Town 11800 Malaysia

The burning number of a graph can be used to measure the spreading speed of contagion in a network. The burning number conjecture is arguably the main unresolved conjecture related to this graph parameter, which can be settled by showing that every tree of order m(2) has burning number at most m. This is known to hold for many classes of trees, including spiders - trees with exactly one vertex of degree greater than two. In fact, it has been verified that certain spiders of order slightly larger than m(2) also have burning numbers at most m, a result that has then been conjectured to be true for all trees. The first focus of this paper is to verify this slightly stronger conjecture for double spiders - trees with two vertices of degrees at least three and they are adjacent. Our other focus concerns the burning numbers of path forests, a class of graphs in which their burning numbers are naturally related to that of spiders and double spiders. Here, our main result shows that a path forest of order m(2) with a sufficiently long shortest path has burning number exactly m, the smallest possible for any path forest of the same order. (C) 2022 Elsevier Inc. All rights reserved.

关键词： Spread of social contagion Burning number conjecture graph algorithm Double spider Path forest

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：