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

Weighted Matching in the Semi-Streaming Model

algorithmICA 2012年第1-2期62卷 1-20页

作者： Zelke, Mariano Goethe Univ Frankfurt Inst Informat D-60054 Frankfurt Germany

We present an approximation algorithm to find a weighted matching of a graph in the one-pass semi-streaming model. The semi-streaming model forbids random access to the input graph and restricts the memory to O(*** n) bits where n denotes the number of the vertices of the input graph. We obtain an approximation ratio of 5.58 while the previously best algorithm achieves a ratio of 5.82.

关键词： Semi-streaming algorithm Approximation algorithm Matching graph algorithm

来源：评论

学校读者我要写书评

暂无评论

A HIERARCHICAL-CLUSTERING algorithm USING STRONG COMPONENTS

引用

INFORMATION PROCESSING LETTERS 1982年第1期14卷 26-29页

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

In a strongly connected digraph whose edges have distinct non-negative weights, the hierarchy of vertex partitions may be represented by means of a rooted tree. This tree is called the strong component decomposition tree. The strong component decomposition tree has been proposed as a clustering method suitable for asymmetric similarity matrices. An especially fast algorithm has been devised to find strong component decomposition trees. The algorithm, which is recursive, consists of several steps. It can be adapted to handle non-distinct edge weights. A different adaptation will cause it to return the edges defining the strong components as well as the vertex sets. Figures.

关键词： Cluster analysis graph decomposition graph algorithm strong components

来源：评论

学校读者我要写书评

暂无评论

Why blockchain needs graph: A survey on studies, scenarios, and solutions

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2023年第1期180卷

作者： Song, Jie Zhang, Pengyi Qu, Qiang Bai, Yongjie Gu, Yu Yu, Ge Northeastern Univ Software Coll Shenyang 110819 Peoples R China Chinese Acad Sci Shenzhen Inst Adv Technol Shenzhen 518055 Peoples R China Huawei Cloud Tech Co Ltd Blockchain Lab Shenzhen 518101 Peoples R China Northeastern Univ Sch Comp Sci & Engn Shenyang 110819 Peoples R China

The popularity of blockchain platforms and their applications in industry and academia keeps rising. The multifarious requirements stimulate another technique, graph data and algorithms, to join the blockchains;thus, studies, scenarios, and solutions about graph-related blockchains have emerged. This paper aims to see whether the state-of-the-art studies satisfy the applications through a comprehensive survey on graph-related blockchains. To answer why a blockchain needs graphs in general, we analyze literature about blockchain and graph, as well as use cases on the application-oriented and graph related scenarios collected from practical blockchain projects. The paper summarizes three graph-related blockchain studies: graph algorithms for blockchains, graph data in blockchains, and graph applications on blockchains. Based on these summarization, it figures out the gaps between the studies and the applications, that is, few of studies natively integrate graph computing into a blockchain. Here, the "graph integration" means processing on-chain graph data, which contains blockchain information, in a realtime, distributed, and consensual manner. We propose the prospect of the graph-integrated Blockchain Platform (GiBP for short), and explain why a GiBP is inevitable, the challenges of a GiBP, and the GiBPs' main functions and features people expect for future research. & COPY;2023 Elsevier Inc. All rights reserved.

关键词： Blockchain Blockchain applications Blockchain platform graph algorithm graph computing

来源：评论

学校读者我要写书评

暂无评论

Maximum bipartite flow in networks with adaptive channel width

引用

THEORETICAL COMPUTER SCIENCE 2011年第24期412卷 2577-2587页

作者： Azar, Yossi Madry, Aleksander Moscibroda, Thomas Panigrahi, Debmalya Srinivasan, Aravind MIT Comp Sci & Artificial Intelligence Lab Stata Ctr Cambridge MA 02139 USA Tel Aviv Univ Sch Comp Sci IL-69978 Tel Aviv Israel Univ Maryland Dept Comp Sci College Pk MD 20742 USA Univ Maryland Inst Adv Comp Studies College Pk MD 20742 USA Microsoft Res Redmond WA 98052 USA

Traditionally, network optimization problems assume that each link in the network has a fixed capacity. Recent research in wireless networking has shown that it is possible to design networks where the capacity of the links can be changed adaptively to suit the needs of specific applications. In particular, one gets a choice of having a few high capacity outgoing links or many low capacity ones at any node of the network. This motivates us to have a re-look at classical network optimization problems and design algorithms to solve them in this new framework. In particular, we consider the problem of maximum bipartite flow, which has been studied extensively in the fixed-capacity network model. One of the motivations for studying this problem arises from the need to maximize the throughput of an infrastructure wireless network comprising base-stations (one set of vertices in the bipartition) and clients (the other set of vertices in the bipartition). We show that this problem has a significantly different combinatorial structure in this new network model from the fixed-capacity one. While there are several polynomial time algorithms for the maximum bipartite flow problem in traditional networks, we show that the problem is NP-hard in the new model. In fact, our proof extends to showing that the problem is APX-hard. we complement our lower bound by giving two algorithms for solving the problem approximately. The first algorithm is deterministic and achieves an approximation factor of O(log N), where N is the number of nodes in the network, while the second algorithm is randomized and achieves an approximation factor of e/e-1. (C) 2010 Elsevier B.V. All rights reserved.

关键词： graph algorithm Maximum flow Linear program rounding Wireless networks Adaptive channel width

来源：评论

学校读者我要写书评

暂无评论

EBOARST: An Efficient Edge-Based Obstacle-Avoiding Rectilinear Steiner Tree Construction algorithm

引用

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 2008年第12期27卷 2169-2182页

作者： Long, Jieyi Zhou, Hai Memik, Seda Ogrenci Northwestern Univ Dept Elect Engn & Comp Engn Evanston IL 60208 USA

Obstacle-avoiding Steiner routing has arisen as a fundamental problem in the physical design of modern VLSI chips. In this paper, we present EBOARST, an efficient four-step algorithm to construct a rectilinear obstacle-avoiding Steiner tree for a given set of pins and a given set of rectilinear obstacles. Our contributions are fourfold. First, we propose a novel algorithm, which generates sparse obstacle-avoiding spanning graphs efficiently. Second, we present a fast algorithm for the minimum terminal spanning tree construction step, which dominates the running time of several existing approaches. Third, we present an edge-based heuristic, which enables us to perform both local and global refinements, leading to Steiner trees with small lengths. Finally, we discuss a refinement technique called segment translation to further enhance the quality of the trees. The time complexity of our algorithm is O(n log n). Experimental results on various benchmarks show that our algorithm achieves 16.56 times speedup on average, while the average length of the resulting obstacle-avoiding rectilinear Steiner trees is only 0.46% larger than the best existing solution.

关键词： graph algorithm obstacle-avoiding routing Steiner tree

来源：评论

学校读者我要写书评

暂无评论

On treewidth approximations

引用

DISCRETE APPLIED MATHEMATICS 2004年第2-3期136卷 183-196页

作者： Bouchitté, V Kratsch, D Müller, H Todinca, I Ecole Normale Super Lyon LIP F-69364 Lyon 07 France Univ Metz LITA F-57045 Metz 01 France Univ Leeds Sch Comp Leeds LS2 9JT W Yorkshire England Univ Orleans LIFO F-45067 Orleans 2 France

We introduce a natural heuristic for approximating the treewidth of graphs. We prove that this heuristic gives a constant factor approximation for the treewidth of graphs with bounded asteroidal number. Using a different technique, we give a O(logk) approximation algorithm for the treewidth of arbitrary graphs, where k is the treewidth of the input graph. (C) 2003 Elsevier B.V. All rights reserved.

关键词： treewidth asteroidal number minimal separator graph algorithm approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

An algorithm for 1-bend embeddings of plane graphs in the two-dimensional grid

引用

DISCRETE APPLIED MATHEMATICS 2004年第1-3期141卷 225-241页

作者： Morgana, A de Mello, CP Sontacchi, G Univ Rome 1 Dipartimento Matemat I-000185 Rome Italy Univ Estadual Campinas Inst Computacao BR-3081970 Campinas SP Brazil

In this paper we characterize the class of plane graphs that can be embedded on the two-dimensional grid with at most one bend on each edge. In addition, we provide an algorithm that either detects a forbidden configu... 详细信息

关键词： planar embedding grid bend graph algorithm VLSI design

来源：评论

学校读者我要写书评

暂无评论

Finding and listing induced paths and cycles

引用

DISCRETE APPLIED MATHEMATICS 2013年第4-5期161卷 633-641页

作者： Hoang, Chinh T. Kaminski, Marcin Sawada, Joe Sritharan, R. Wilfrid Laurier Univ Waterloo ON N2L 3C5 Canada Univ Libre Bruxelles Dept Informat Algorithms Res Grp B-1050 Brussels Belgium Univ Guelph Sch Comp Sci Guelph ON N1G 2W1 Canada Univ Dayton Dept Comp Sci Dayton OH 45469 USA

Many recognition problems for special classes of graphs and cycles can be reduced to finding and listing induced paths and cycles in a graph. We design algorithms to list all P-3's in O(m(1.5) + p(3)(G)) time, and for k >= 4 all P-k's in O(n(k-1) + p(k)(G) + k.c(k)(G)) time, where p(k)(G), respectively, c(k)(G), are the number of P-k's, respectively, C-k's, of a graph G. We also provide an algorithm to find a P-k, k >= 5, in time O(k!! . m((k-1)/2)) if k is odd, and O(k!! . nm((k/2)-1)) if k is even. As applications of our findings, we give algorithms to recognize quasi-triangulated graphs and brittle graphs. Our algorithms' time bounds are incomparable with previously known algorithms. (C) 2012 Elsevier B.V. All rights reserved.

关键词： graph algorithm Induced path Induced cycle

来源：评论

学校读者我要写书评

暂无评论

AN APPLICATION OF ST-NUMBERING TO SECRET KEY AGREEMENT

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2011年第5期22卷 1211-1227页

作者： Mizuki, Takaaki Nakayama, Satoru Sone, Hideaki Tohoku Univ Cybersci Ctr Aoba Ku Sendai Miyagi 9808578 Japan Tohoku Univ Grad Sch Informat Sci Sone Lab Aoba Ku Sendai Miyagi 9808578 Japan

Assume that there are players and an eavesdropper Eve, where several pairs of players have shared secret keys beforehand. We regard each player as a vertex of a graph and regard each pair of players sharing a key as an edge. Consider the case where Eve knows some of the keys according to a certain probability distribution. In this paper, applying the technique of st-numbering, we propose a protocol which allows any two designated players to agree on a secret key through such a "partially leaked key exchange graph." Our protocol is optimal in the sense that Eve's knowledge about the secret key agreed on by the two players is as small as possible.

关键词： graph algorithm st-numbering Key sharing graph Key agreement protocol Information-theoretic secrecy

来源：评论

学校读者我要写书评

暂无评论

Efficient Dispersion of Mobile Robots on graphs 19

Efficient Dispersion of Mobile Robots on Graphs

引用

20th International Conference on Distributed Computing and Networking (ICDCN)

作者： Kshemkalyani, Ajay D. Ali, Faizan Univ Illinois Chicago IL 60612 USA

ISBN: (纸本)9781450360944

The dispersion problem on graphs requires k robots placed arbitrarily at the n nodes of an anonymous graph, where k <= n, to coordinate with each other to reach a final configuration in which each robot is at a distinct node of the graph. The dispersion problem is important due to its relationship to graph exploration by mobile robots, scattering on a graph, and load balancing on a graph. In addition, an intrinsic application of dispersion has been shown to be the relocation of self-driven electric cars (robots) to recharge stations (nodes). We propose five algorithms to solve dispersion on graphs. The first three algorithms require O(k log Delta) bits at each robot andO(m) steps running time, wherem is the number of edges and Delta is the degree of the graph. The algorithms differ in whether they address the synchronous or the asynchronous system model, and in what, where, and how data structures are maintained. The fourth algorithm, for the asynchronous model, has a space usage of O(D log Delta) bits at each robot and uses O(Delta(D)) steps, where D is the graph diameter. The fifth algorithm, for the asynchronous model, has a space usage of O(max(log k, log Delta)) bits at each robot and uses O((m - n) k) steps.

关键词： distributed algorithm dispersion graph algorithm graph exploration mobile robot collective robot exploration

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：