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

DAG-Pathwidth: graph algorithmic Analyses of DAG-Type Blockchain Networks

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2023年第3期E106D卷 272-283页

作者： Kasahara, Shoji Kawahara, Jun Minato, Shin-ichi Mori, Jumpei Nara Inst Sci & Technol Ikoma 6300192 Japan Kyoto Univ Kyoto 6068501 Japan

This paper analyzes a blockchain network forming a directed acyclic graph (DAG), called a DAG-type blockchain, from the view-point of graph algorithm theory. To use a DAG-type blockchain, NP-hard graph optimization problems on the DAG are required to be solved. Although various problems for undirected and directed graphs can be efficiently solved by using the notions of graph parameters, these currently known parameters are meaningless for DAGs, which implies that it is hopeless to design efficient algorithms based on the parameters for such problems. In this work, we propose a novel graph parameter for directed graphs called a DAG-pathwidth, which represents the closeness to a directed path. This is an extension of the pathwidth, a well-known graph parameter for undirected graphs. We analyze the features of the DAG-pathwidth and prove that computing the DAG-pathwidth of a DAG (directed graph in general) is NP-complete. Finally, we propose an efficient algorithm for a variant of the maximum k-independent set problem for the DAG-type blockchain when the DAG-pathwidth of the input graph is small.

关键词： graph algorithm computational complexity directed acyclic graph pathwidth blockchain

来源：评论

学校读者我要写书评

暂无评论

An O(k^2n^2) algorithm to Find a k-Partition in a k-Connected graph

引用

Journal of Computer Science & Technology 1994年第1期9卷 86-91页

作者：马军马绍汉 DepartmentofComputerScience ShandongUniversityJinan250100 DepartmentofComputerScience ShandongUniver

Although there are polynomial algorithms of finding a 2-partition or a 3-partition for a simple undirected 2-connected or 3-connected graph respectively, there is no general algorithm of finding a k-partition for a k-connected graph G = (V, E), where k is the vertex connectivity of G. In this paper, an O(k2n2) general algorithm of finding a k-partition for a k-connected graph is proposed, where n = |V|.

关键词： graph algorithm graph vertex connectivity k-partition of a graph

来源：评论

学校读者我要写书评

暂无评论

PARALLEL MATRIX AND graph algorithmS

引用

SIAM JOURNAL ON COMPUTING 1981年第4期10卷 657-675页

作者： DEKEL, E NASSIMI, D SAHNI, S NORTHWESTERN UNIV DEPT ELECT ENGN & COMP SCIEVANSTONIL 60201

Matrix multiplication algorithms for cube connected and perfect shuffle computers are presented. It is shown that in both these models two n×nn×nn \times n matrices can be multiplied in <span class="... 详细信息

Matrix multiplication algorithms for cube connected and perfect shuffle computers are presented. It is shown that in both these models two

n \times n

$n \times n$ matrices can be multiplied in

O (n

来源：评论

学校读者我要写书评

暂无评论

Generic graph algorithms

Generic graph algorithms

引用

International Seminar on Generic Programming

作者： Kühl, D Claas Solutions GmbH Germany

ISBN: (纸本)3540410902

Implementing non-trivial algorithms, like many graph algorithms, is generally expensive, Thus, it is desirable to reuse such implementations whenever possible. The implementations of graph algorithms normally cannot be reused mainly because the representations of graphs differ in many ways and the implementations normally assume one specific representation. This article presents an approach to overcoming this problem which is based mainly on special iterators and special means to access data associated with objects.

关键词： graph algorithm iterator data accessor algorithm object

来源：评论

学校读者我要写书评

暂无评论

An Early Evaluation of the Scalability of graph algorithms on the Intel MIC Architecture

An Early Evaluation of the Scalability of Graph Algorithms o...

引用

26th IEEE International Parallel and Distributed Processing Symposium (IPDPS) / Workshop on High Performance Data Intensive Computing

作者： Saule, Erik Catalyuerek, Uemit V. Ohio State Univ Dept Biomed Informat Columbus OH 43210 USA

ISBN: (纸本)9780769546766

graph algorithms are notorious for not getting good speedup on parallel architectures. These algorithms tend to suffer from irregular dependencies and a high synchronization cost that prevent an efficient execution on distributed memory machines. Hence such algorithms are mostly parallelized on shared memory machines. However, current commodity shared memory machines do not typically offer enough parallelism to process these problems. In this paper, we are presenting an early investigation of the scalability of such algorithms on Intel's upcoming Many Integrated Core (Intel MIC) architecture which, when it will be released in 2012, is expected to provide more than 50 physical cores with SMT capability. The Intel MIC architecture can be programmed through many programming models, here we investigate the three most popular of these models namely OpenMP, Cilk Plus and Intel's TBB. We present scalability results of a parallel graph coloring algorithm, three variations of a breadth-first search algorithm and a microbenchmark for irregular computations using these three programming models. Our results on a prototype board show that the multi-threaded architecture of Intel MIC can be effectively used for hiding latencies in irregular applications to achieve almost perfect speedup.

关键词： graph algorithm unstructured irregular computation scalability multi-threaded architectures graph coloring breadth-first search

来源：评论

学校读者我要写书评

暂无评论

An Evaluation of graph algorithms for the Wind Farm Cable Layout Problem under Electrical Aspects 56

An Evaluation of Graph Algorithms for the Wind Farm Cable La...

引用

56th International Universities Power Engineering Conference (UPEC) - Powering Net Zero Emissions

作者： Gritzbach, Sascha Cakmak, Hueseyin Mehnert, Pascal Ueckerdt, Torsten Hagenmeyer, Veit Karlsruhe Inst Technol Inst Theoret Informat Karlsruhe Germany Karlsruhe Inst Technol Inst Automat & Appl Informat Karlsruhe Germany Karlsruhe Inst Technol Dept Informat Karlsruhe Germany

ISBN: (纸本)9781665443890

The task of the Wind Farm Cable Layout Problem is to design a cable system between turbines and substations such that all turbine output can be transmitted to the substations. This problem can be modelled with different levels of complexity. While a higher level of complexity yields solutions that can be implemented in a real-world setting more readily, problem instances also become more difficult to solve or even remain intractable. More simplistic models are easier to solve but their usability could be inhibited. One such more simplistic model for installation cost minimization contains a network flow and a suitable minimum-cost flow algorithm provides good cable layouts on instances with up to 500 turbines within tens of seconds. The question remains whether those cable layouts are suitable for electrical implementation as well. We propose a workflow to evaluate the cable layouts generated from such algorithms under electrical aspects. This workflow converts the output of cable layout optimization algorithms to power flow models. The power flow models are simulated using the simulation framework eASiMOV. The evaluation of the power flow simulations under electrical metrics shows that output from the minimum-cost flow algorithm and from an approach solving a Mixed-Integer Linear Program perform very well under electrical aspects on a vast majority of input instances. For the remaining minority we are able to identify structures in the solutions that result in a worse performance. These observations can be used by the algorithm engineers as possible directions for future improvements.

关键词： Wind Farm Cable Layout graph algorithm Network Flow Power Flow Analysis

来源：评论

学校读者我要写书评

暂无评论

Human-Centric Community Detection in Hybrid Metaverse Networks with Integrated AI Entities 34

Human-Centric Community Detection in Hybrid Metaverse Networ...

引用

34th ACM Web Conference, WWW 2025

作者： Chiu, Shih-Hsuan Teng, Ya-Wen Yang, De-Nian Chen, Ming-Syan National Taiwan University Taipei Taiwan Academia Sinica Taipei Taiwan

ISBN: (纸本)9798400712746

Community detection is a cornerstone problem in social network analysis (SNA), aimed at identifying cohesive communities with minimal external links. However, the rise of generative AI and Metaverse introduce complexities by creating hybrid human-AI social networks (denoted by HASNs), where traditional methods fall short, especially in human-centric settings. This paper introduces a novel community detection problem in HASNs (denoted by MetaCD), which seeks to enhance human connectivity within communities while reducing the presence of AI nodes. Effective processing of MetaCD poses challenges due to the delicate trade-off between excluding certain AI nodes and maintaining community structure. To address this, we propose CUSA, an innovative framework incorporating AI-aware clustering techniques that navigate this trade-off by selectively retaining AI nodes that contribute to community integrity. Furthermore, given the scarcity of real-world HASNs, we devise four strategies for synthesizing these networks under various hypothetical scenarios. Empirical evaluations on real social networks, reconfigured as HASNs, demonstrate the effectiveness and practicality of our approach compared to traditional non-deep learning and graph neural network (GNN)-based methods. © 2025 Copyright held by the owner/author(s).

关键词： Clustering Community Detection graph algorithm Human-Centric Metaverse Social Networks

来源：评论

学校读者我要写书评

暂无评论

An Optimal O(nm) algorithm for Enumerating All Walks Common to All Closed Edge-covering Walks of a graph

引用

ACM TRANSACTIONS ON algorithmS 2019年第4期15卷 48-48页

作者： Cairo, Massimo Medvedev, Paul Acosta, Nidia Obscura Rizzi, Romeo Tomescu, Alexandru, I Univ Trento Dept Math Via Sommarive 14 I-38123 Povo Italy Penn State Univ Dept Comp Sci & Engn W316 Westgate Bldg University Pk PA 16802 USA Aalto Univ Aalto SCI Comp Sci Konemiehentie 2 Espoo 02150 Finland Univ Verona Dept Comp Sci CaVignal 2Str Grazie 15 I-37134 Verona Italy Univ Helsinki Dept Comp Sci POB 68 FI-00014 Helsinki Finland

In this article, we consider the following problem. Given a directed graph G, output all walks of G that are sub-walks of all closed edge-covering walks of G. This problem was first considered by Tomescu and Medvedev (RECOMB 2016), who characterized these walks through the notion of omnitig. Omnitigs were shown to be relevant for the genome assembly problem from bioinformatics, where a genome sequence must be assembled from a set of reads from a sequencing experiment. Tomescu and Medvedev (RECOMB 2016) also proposed an algorithm for listing all maximal omnitigs, by launching an exhaustive visit from every edge. In this article, we prove new insights about the structure of omnitigs and solve several open questions about them. We combine these to achieve an O(nm)-time algorithm for outputting all the maximal omnitigs of a graph (with n nodes and m edges). This is also optimal, as we show families of graphs whose total omnitig length is Omega(nm). We implement this algorithm arid show that it is 9-12 times faster in practice than the one of Tomescu and Medvedev (RECOMB 2016).

关键词： Genome assembly safe and complete algorithm graph algorithm edge-covering walk strong bridge

来源：评论

学校读者我要写书评

暂无评论

Spatial Hardware Implementation for Sparse graph algorithms in graphStep

引用

ACM TRANSACTIONS ON AUTONOMOUS AND ADAPTIVE SYSTEMS 2011年第3期6卷 17-17页

作者： Delorimier, Michael Kapre, Nachiket Mehta, Nikil Dehon, Andre Univ Penn Dept Elect & Syst Engn Philadelphia PA 19104 USA

How do we develop programs that are easy to express, easy to reason about, and able to achieve high performance on massively parallel machines? To address this problem, we introduce graph Step, a domain-specific compute model that captures algorithms that act on static, irregular, sparse graphs. In graph Step, algorithms are expressed directly without requiring the programmer to explicitly manage parallel synchronization, operation ordering, placement, or scheduling details. Problems in the sparse graph domain are usually highly concurrent and communicate along graph edges. Exposing concurrency and communication structure allows scheduling of parallel operations and management of communication that is necessary for performance on a spatial computer. We study the performance of a semantic network application, a shortest-path application, and a max-flow/min-cut application. We introduce a language syntax for graphStep applications. The total speedup over sequential versions of the applications studied ranges from a factor of 19 to a factor of 15,000. Spatially-aware graph optimizations (e.g., node decomposition, placement and route scheduling) delivered speedups from 3 to 30 times over a spatially-oblivious mapping.

关键词： Languages algorithms Performance Spatial computing compute model parallel programming graph algorithm graphStep

来源：评论

学校读者我要写书评

暂无评论

Realization of two graph algorithms and design of the operational platform of graph algorithms

引用

Yi Qi Yi Biao Xue Bao/Chinese Journal of Scientific Instrument 2007年第SUPP. 4期28卷 378-380+387页

作者： Wu, Jun Liu, Xiulan College of Electronic Information and Control Engineering Beijing University of Technology Beijing 100022 China

Two graph algorithms which derive from bread-first search were implemented by using C language in this paper. One algorithm is a replacement method for finding out a graph's all spanning tree, the other is the Paton algorithm for finding out all essential circuit of a graph. This paper mainly introduced the flow of the two graph algorithms. An illustrative example was presented. Also, a practical operational platform of graph algorithm was designed and realized in this paper.

关键词： All spanning tree graph algorithm Operational platform design Paton algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：