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

AN O(LOG N) algorithm FOR PARALLEL UPDATE OF MINIMUM SPANNING-TREES

INFORMATION PROCESSING LETTERS 1986年第5期22卷 223-229页

作者： PAWAGI, S RAMAKRISHNAN, IV Department of Computer Science University of Maryland College Park MD 20742 U.S.A.

Incremental graph algorithms deal with recomputing properties of a graph after an incremental change is made to that graph, such as adding and deleting vertices and edges. Such recomputations are ''updating'' graph properties. Efficient parallel algorithms are presented for edge and vertex insertion updating in a minimum spanning tree (MST) due to changes in edge costs or in vertex insertion, when a new node is inserted in the underlying graph. The algorithms are derived from a computational model of an unbounded parallel random access machine where simultaneous reads, but not simultaneous writes, are allowed into the same memory location. They are shown to be more efficient than previously proposed algorithms for the MST updating problem, requiring only O(log n) time and certain processors. Main features of the algorithms are that they: 1. solve MST updating problems based on the use of an inverted tree, and 2. exploit a certain MST property that allows novel solution for vertex updating.

关键词： Spanning tree graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Enumerating All Rooted Trees Including k Leaves

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2012年第3期E95D卷 763-768页

作者： Ishikawa, Masanobu Yamanaka, Katsuhisa Otachi, Yota Nakano, Shin-ichi Gunma Univ Dept Comp Sci Kiryu Gunma 3768515 Japan Iwate Univ Dept Elect Engn & Comp Sci Morioka Iwate 0208551 Japan Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 9808579 Japan

This paper presents an efficient algorithm to generate all (unordered) rooted trees with exactly vertices including exactly k leaves. There are known results on efficient enumerations of some classes of graphs embedded on a plane, for instance, biconnected and triconnected triangulations [3], [6], and floorplans [4]. On the other hand, it is difficult to enumerate a class of graphs without a fixed embedding. The paper is on enumeration of rooted trees without a fixed embedding. We already proposed an algorithm to generate all "ordered" trees with 17 vertices including k leaves [11], while the algorithm cannot seem to efficiently generate all (unordered) rooted trees with it vertices including k leaves. We design a simple tree structure among such trees, then by traversing the tree structure we generate all such trees in constant time per tree in the worst case. By repeatedly applying the algorithm for each k = 1, 2, . . . , n - 1, we can also generate all rooted trees with exactly n vertices.

关键词： graph algorithm enumeration rooted tree family tree

来源：评论

学校读者我要写书评

暂无评论

Multicast Routing Using Delay Intervals for Collaborative and Competitive Applications

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2018年第12期66卷 6329-6338页

作者： Andrus, James Banik, Shankar M. Swart, Breeanne Baker Verdicchio, Michael The Citadel Dept Math & Comp Sci Charleston SC 29409 USA

Collaborative and competitive applications require that participants receive messages almost simultaneously and before a specified time. These requirements have been addressed by the delay variation-bounded multicasting tree (DVBMT) problem. In this paper, we propose the interval multicast subgraph (IMS) problem to address these requirements. IMS addresses these constraints with an interval of acceptable delay values for paths as user input from a source to a destination, eliminating the need to optimize delays for a variation value. By solving IMS rather than DVBMT and other variants of DVBMT, we are able to find solutions for larger graphs more efficiently. Our proposed interval multicast algorithm (IMA) accounts for an interval of acceptable delay as user input and guarantees the weight of each path from the source to a distinct destination is within the given interval if that path exists. We provide proofs of correctness and complexity of IMA, as well as simulation experiments, to illustrate the effects of various parameters on our algorithm. Simulations show that IMS is significantly less costly than finding the minimum variation for the average and best case. By remodeling the DVBMT problem to IMS, we have created a new problem that addresses the quality of service requirements of multicasting and is able to be solved efficiently for the average case for relatively large graphs.

关键词： QoS graph algorithm multicast routing delay interval collaborative applications

来源：评论

学校读者我要写书评

暂无评论

Efficient community detection with additive constrains on large networks

引用

KNOWLEDGE-BASED SYSTEMS 2013年 52卷 268-278页

作者： Li, Yakun Wang, Hongzhi Li, Jianzhong Gao, Hong Harbin Inst Technol Dept Comp Sci & Technol Harbin 150001 Peoples R China

The community structure is one of the most important patterns in network. Since finding the communities in the network can significantly improve our understanding of the complex relations, lots of work has been done in recent years. Yet it still lies vacant on the exact definition and practical algorithms for community detection. This paper proposes a novel definition for community which overcomes the drawbacks of existing methods. With the new definition, efficient community detection algorithms are developed, which take advantage of additive topological and other constrains to discover communities in arbitrary shape based on the feedback. The algorithm has a linear run time with the size of graph. Experimental results demonstrate that the community definition in this paper is effective and the algorithm is scalable for large graphs. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Community detection Feedback control Additive constrains Large networks Scale-free network graph algorithm

来源：评论

学校读者我要写书评

暂无评论

FAST algorithmS FOR FINDING NEAREST COMMON ANCESTORS: 收藏
分享
引用; SIAM JOURNAL ON COMPUTING 1984年第2期13卷 338-355页; 作者： HAREL, D TARJAN, RE UNIV NEW HAMPSHIRE DURHAMNH 03824 BELL TEL LABS INC MURRAY HILLNJ 07974; We consider the following problem: Given a collection of rooted trees, answer on-line queries of the form, “What is the nearest common ancester of vertices x and y?” We show that any pointer machine that solves this... 详细信息; We consider the following problem: Given a collection of rooted trees, answer on-line queries of the form, “What is the nearest common ancester of vertices x and y?” We show that any pointer machine that solves this problem requires $Ω (\log \log n)$; 来源：评论; 学校读者我要写书评

暂无评论

Approximating capacitated tree-routings in networks

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2011年第2期21卷 254-267页

作者： Morsy, Ehab Nagamochi, Hiroshi Kyoto Univ Dept Appl Math & Phys Grad Sch Informat Sakyo Ku Kyoto 6068501 Japan Suez Canal Univ Dept Math Fac Sci Ismailia Egypt

Let G = (V, E) be a connected graph such that each edge e is an element of E is weighted by a nonnegative real w(e). Let s be a vertex designated as a sink, M subset of V be a set of terminals with a demand function q : M -> R+, kappa > 0 be a routing capacity, and lambda >= 1 be an integer edge capacity. The capacitated tree-routing problem (CTR) asks to find a partition M = {Z(1), Z(2), ... , Z(l)} of M and a set tau = {T-1, T-2, ... , T-l} of trees of G such that each T-i contains Z(i) boolean OR {s} and satisfies Sigma(upsilon is an element of Zi) q(upsilon) <= kappa. A single copy of an edge e is an element of E can be shared by at most lambda trees in tau;any integer number of copies of e are allowed to be installed, where the cost of installing a copy of e is w(e). The objective is to find a solution (M, T) that minimizes the total installing cost. In this paper, we propose a (2+rho(ST))-approximation algorithm to CTR, where rho(ST) is any approximation ratio achievable for the Steiner tree problem.

关键词： Approximation algorithm graph algorithm Routing problems Network optimization Tree cover

来源：评论

学校读者我要写书评

暂无评论

A genetic algorithm with path-relinking for operation sequencing in CAPP

引用

INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY 2023年第7-8期125卷 3667-3690页

作者： Dou, Jianping Wang, Shuai Zhang, Canran Shi, Yunde Southeast Univ Sch Mech Engn 1 Rd Dongnan Daxue Nanjing 211189 Peoples R China Huazhong Univ Sci & Technol State Key Lab Digital Mfg Equipment & Technol Wuhan 430074 Peoples R China

Due to the rapid change of customized products in Industry 4.0, the operation sequencing (OS) as a core function of CAPP system is frequently needed. In this paper, a novel path-relinking genetic algorithm (PR-GA) is proposed to find the minimal-cost solution of the OS problem. In the PR-GA, the chromosome records the feasible operation sequence (FOS) satisfying the precedence constraints of operations via a permutation, and the designed crossover and mutation involve chromosomes and ensure their feasibility. For a given FOS, the optimal manufacturing resources for every operation are identified by a polynomial-time graph algorithm including a graph building procedure and a dynamic programing procedure. Thus, the PR-GA focuses on searching promising FOSs, and uses path-relinking as a local search around paths between elitists. Moreover, a new framework of GA is established and is characterized by avoiding tuning crossover and mutation rates of the common GA. The PR-GA is compared with state-of-the-art metaheuristic algorithms (MAs) including ant colony optimization, particle swarm optimization, two recent GAs, and a recent exact method to verify its effectiveness and efficiency. The comparison results show that the PR-GA outperforms existing MAs for solution quality, and illustrates the PR-GA's promising efficiency and robust global search ability.

关键词： Operation sequencing Genetic algorithm Path-relinking graph algorithm Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

New approximation algorithms for the rooted Budgeted Cycle Cover problem

引用

THEORETICAL COMPUTER SCIENCE 2023年第PartA期940卷 283-295页

作者： Li, Jiangkun Zhang, Peng Shandong Univ Sch Software Jinan 250101 Shandong Peoples R China

The rooted Budgeted Cycle Cover (BCC) problem is a fundamental optimization problem arising in wireless sensor networks and vehicle routing. Given a metric space (V, w) with vertex set V consisting of two parts D (containing depots) and V \ D (containing nodes), and a budget B >= 0, the rooted BCC problem asks to find a minimum number of cycles to cover all the nodes in V \ D, satisfying that each cycle has length at most B and each cycle must contain a depot in D. In this paper, we give new approximation algorithms for the rooted BCC problem. For the rooted BCC problem with single depot, we give an O (logB mu )-approximation algorithm, where mu is the minimum difference of any two different distances between the vertices in V and the root. For the rooted BCC problem with multiple depots, we give an O (log n)-approximation algorithm, where n is the number of vertices. We also test our algorithms on the randomly generated instances. The experimental results show that the algorithms have good performance in practice. (c) 2022 Elsevier B.V. All rights reserved.

关键词： Budgeted Cycle Cover Wireless sensor network graph algorithm Approximation algorithm Combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

Reconfiguration of colorable sets in classes of perfect graphs

引用

THEORETICAL COMPUTER SCIENCE 2019年 772卷 111-122页

作者： Ito, Takehiro Otachi, Yota Tohoku Univ Grad Sch Informat Sci Aoba Yama 6-6-05 Sendai Miyagi 9808579 Japan Kumamoto Univ Fac Adv Sci & Technol Chuo Ku 2-39-1 Kurokami Kumamoto 8608555 Japan

A set of vertices in a graph is c-colorable if the subgraph induced by the set has a proper c-coloring. In this paper, we study the problem of finding a step-by-step transformation (called a reconfiguration sequence) between two c-colorable sets in the same graph. This problem generalizes the well-studied INDEPENDENT SET RECONFIGURATION problem. As the first step toward a systematic understanding of the complexity of this general problem, we study the problem on classes of perfect graphs. We first focus on interval graphs and give a combinatorial characterization of the distance between two c-colorable sets. This gives a linear-time algorithm for finding an actual shortest reconfiguration sequence for interval graphs. Since interval graphs are exactly the graphs that are simultaneously chordal and co-comparability, we then complement the positive result by showing that even deciding reachability is PSPACE-complete for chordal graphs and for co-comparability graphs. The hardness for chordal graphs holds even for split graphs. We also consider the case where c is a fixed constant and show that in such a case the reachability problem is polynomial time solvable for split graphs but still PSPACE-complete for co-comparability graphs. The complexity of this case for chordal graphs remains unsettled. As by-products, our positive results give the first polynomial-time solvable cases (split graphs and interval graphs) for FEEDBACK VERTEX SET RECONFIGURATION. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Combinatorial reconfiguration graph algorithm Colorable set Perfect graph

来源：评论

学校读者我要写书评

暂无评论

Simple and Improved Parameterized algorithms for Multiterminal Cuts

引用

THEORY OF COMPUTING SYSTEMS 2010年第4期46卷 723-736页

作者： Xiao, Mingyu Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu 610054 Peoples R China

Given a graph G = (V, E) with n vertices and m edges, and a subset T of k vertices called terminals, the Edge (respectively, Vertex) Multiterminal Cut problem is to find a set of at most l edges (non-terminal vertices), whose removal from G separates each terminal from all the others. These two problems are NP-hard for k = 3 but well-known to be polynomial-time solvable for k = 2 by the flow technique. In this paper, based on a notion farthest minimum isolating cut, we design several simple and improved algorithms for Multiterminal Cut. We show that Edge Multiterminal Cut can be solved in O(2(l)kT (n, m)) time and Vertex Multiterminal Cut can be solved in O(k(l)T (n, m)) time, where T (n, m) = O(min(n(2/3), m(1/2)) m) is the running time of finding a minimum (s, t) cut in an unweighted graph. Furthermore, the running time bounds of our algorithms can be further reduced for small values of k: Edge 3-Terminal Cut can be solved in O(1.415(l)T (n, m)) time, and Vertex {3, 4, 5, 6}-Terminal Cuts can be solved in O(2.059(l)T (n, m)), O(2.772(l)T (n, m)), O(3.349(l)T (n, m)) and O(3.857(l)T (n, m)) time respectively. Our results on Multiterminal Cut can also be used to obtain faster algorithms for Multicut: O((min(root 2k, l) + 1)(2k)2(l)T (n, m))-time algorithm for Edge Multicut and O((2k)Tk+l/2 (n, m))-time algorithm for Vertex Multicut.

关键词： graph algorithm Parameterized algorithm Multiterminal cut Multicut

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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