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

Efficient algorithms for Variants of Weighted Matching and Assignment Problems

MATHEMATICS IN COMPUTER SCIENCE 2008年第4期1卷 673-688页

作者： Banerjee, Satyajit Chowdhury, Atish Datta Ghosh, Subhas Kumar Honeywell Technol Solut 151-1 DoraisanipalyaBannerghatta Rd Bangalore 560076 Karnataka India

Obtaining a matching in a graph satisfying a certain objective is an important class of graph problems. Matching algorithms have received attention for several decades. However, while there are efficient algorithms to obtain a maximum weight matching, not much is known about the maximum weight maximum cardinality, and maximum cardinality maximum weight matching problems for general graphs. Our contribution in this work is to show that for bounded weight input graphs one can obtain an algorithm for both maximum weight maximum cardinality (for real weights), and maximum cardinality maximum weight matching (for integer weights) by modifying the input and running the existing maximum weight matching algorithm. Also, given the current state of the art in maximum weight matching algorithms, we show that, for bounded weight input graphs, both maximum weight maximum cardinality, and maximum cardinality maximum weight matching have algorithms of similar complexities to that of maximum weight matching. Subsequently, we also obtain approximation algorithms for maximum weight maximum cardinality, and maximum cardinality maximum weight matching.

关键词： Maximum weight maximum cardinality matching approximation algorithm graph algorithm reduction

来源：评论

学校读者我要写书评

暂无评论

Fast Sparse Matrix and Sparse Vector Multiplication algorithm on the GPU 29

Fast Sparse Matrix and Sparse Vector Multiplication Algorith...

引用

29th IEEE International Parallel and Distributed Processing Symposium (IPDPS)

作者： Yang, Carl Wang, Yangzihao Owens, John D. Univ Calif Davis Dept Elect & Comp Engn Davis CA 95616 USA

ISBN: (纸本)9781467376846

We implement a promising algorithm for sparse-matrix sparse-vector multiplication (SpMSpV) on the GPU. An efficient k-way merge lies at the heart of finding a fast parallel SpMSpV algorithm. We examine the scalability of three approaches-no sorting, merge sorting, and radix sorting-in solving this problem. For breadth-first search (BFS), we achieve a 1.26x speedup over state-of-the-art sparse-matrix dense-vector (SpMV) implementations. The algorithm seems generalizeable for single-source shortest path (SSSP) and sparse-matrix sparse-matrix multiplication, and other core graph primitives such as maximal independent set and bipartite matching.

关键词： parallel GPU graph algorithm sparse matrix multiplication

来源：评论

学校读者我要写书评

暂无评论

pTrans: A Scalable algorithm for Reservation Guarantees in Distributed Systems 20

pTrans: A Scalable Algorithm for Reservation Guarantees in D...

引用

32nd ACM Symposium on Parallelism in algorithms and Architectures (SPAA)

作者： Peng, Yuhan Varman, Peter Rice Univ Houston TX 77005 USA

ISBN: (纸本)9781450369350

Providing performance QoS (Quality-of-Service) guarantees in a distributed data center environment poses unique challenges. In a typical setting, a client must be guaranteed a minimum amount of service (its contractual reservation) aggregated over all servers on which it has demand for service. A server may receive service demands from multiple clients, which may in aggregate exceed its service capacity. The system must decide how much service to provide to each client on each server that it has demand, in order to satisfy all clients' reservations. In case there is no feasible allocation of the service, the amount of reservation that is fulfilled must be maximized. In practice, the number of clients is several orders of magnitude larger than the number of servers. We describe a simple iterative algorithm called pTrans for reservation allocation based on a directed graph model;servers are vertices and edges are characterized by a vector of feasible service transfers between adjacent servers. We provide formal proofs that the algorithm converges to the global optimal and has a polynomial worst-case running time. Moreover, pTrans can be easily parallelized using multiple threads. Empirical evaluation results show pTrans has low runtime overheads.

关键词： distributed system reservation guarantee QoS graph algorithm

来源：评论

学校读者我要写书评

暂无评论

On treewidth approximations

On treewidth approximations

引用

1st CologneTwente Workshop on graphs and Combinatorial Optimization (CTW2001)

作者： 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

来源：评论

学校读者我要写书评

暂无评论

Minimizing Polarization in Noisy Leader-Follower Opinion Dynamics 23

Minimizing Polarization in Noisy Leader-Follower Opinion Dyn...

引用

32nd ACM International Conference on Information and Knowledge Management (CIKM)

作者： Xu, Wanyue Zhang, Zhongzhi Fudan Univ Shanghai Peoples R China

ISBN: (纸本)9798400701245

The operation of creating edges has been widely applied to optimize relevant quantities of opinion dynamics. In this paper, we consider a problem of polarization optimization for the leader-follower opinion dynamics in a noisy social network with n nodes and m edges, where a group Q of q nodes are leaders, and the remaining n - q nodes are followers. We adopt the popular leader-follower DeGroot model, where the opinion of every leader is identical and remains unchanged, while the opinion of every follower is subject to white noise. The polarization is defined as the steady-state variance of the deviation of each node's opinion from leaders' opinion, which equals one half of the effective resistance R-Q between the node group Q and all other nodes. Concretely, we propose and study the problem of minimizing R-Q by adding k new edges with each incident to a node in Q. We showthat the objective function is monotone and supermodular. We then propose a simple greedy algorithm with an approximation factor 1 - 1/e that approximately solves the problem in O ((n - q)(3)) time. To speed up the computation, we also provide a fast algorithm to compute (1 - 1/ e - c)-approximate effective resistance R-Q, the running time of which is (O) over tilde (mk epsilon(-2)) for any c > 0, where the (O) over tilde(center dot) notation suppresses the poly(log n) factors. Extensive experiment results show that our second algorithm is both effective and efficient.

关键词： Opinion dynamics graph algorithm data mining discrete optimization

来源：评论

学校读者我要写书评

暂无评论

Efficient Cohesive Subgraphs Detection in Parallel 14

Efficient Cohesive Subgraphs Detection in Parallel

引用

ACM SIGMOD International Conference on Management of Data

作者： Shao, Yingxia Chen, Lei Cui, Bin Peking Univ Sch EECS MOE Key Lab High Confidence Software Technol Beijing Peoples R China HKUST Dept Comp Sci & Engn Hong Kong Hong Kong Peoples R China

ISBN: (纸本)9781450323765

A cohesive subgraph is a primary vehicle for massive graph analysis, and a newly introduced cohesive subgraph, k-truss, which is motivated by a natural observation of social cohesion, has attracted more and more attention. However, the existing parallel solutions to identify the k-truss are inefficient for very large graphs, as they still suffer from huge communication cost and large number of iterations during the computation. In this paper, we propose a novel parallel and efficient truss detection algorithm, called PETA. The PETA produces a triangle complete subgraph (TC-subgraph) for every computing node. Based on the TC-subgraphs, PETA can detect the local k-truss in parallel within a few iterations. We theoretically prove, within this new paradigm, the communication cost of PETA is bounded by three times of the number of triangles, the total computation complexity of PETA is the same order as the best known serial algorithm and the number of iterations for a given partition scheme is minimized as well. Furthermore, we present a subgraph-oriented model to efficiently express PETA in parallel graph computing systems. The results of comprehensive experiments demonstrate, compared with the existing solutions, PETA saves 2X to 19X in communication cost, reduces 80% to 95% number of iterations and improves the overall performance by 80% across various real-world graphs.

关键词： graph algorithm Cohesive Subgraph Truss Subgraph-Oriented

来源：评论

学校读者我要写书评

暂无评论

A quantum procedure for map generation

A quantum procedure for map generation

引用

IEEE Conference on Games (IEEE CoG)

作者： Wootton, James R. IBM Res Zurich IBM Quantum Zurich Switzerland

ISBN: (纸本)9781728145334

Quantum computation is an emerging technology that promises a wide range of possible use cases. This promise is primarily based on algorithms that are unlikely to be viable over the coming decade. For near-term applications, quantum software needs to be carefully tailored to the hardware available. In this paper, we begin to explore whether near-term quantum computers could provide tools that are useful in the creation and implementation of computer games. The procedural generation of geopolitical maps and their associated history is considered as a motivating example. This is performed by encoding a rudimentary decision making process for the nations within a quantum procedure that is well-suited to near-term devices. Given the novelty of quantum computing within the field of procedural generation, we also provide an introduction to the basic concepts involved.

关键词： Quantum computing Procedural content generation game development graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Directed convergence heuristic: A fast & novel approach to Steiner tree construction

Directed convergence heuristic: A fast & novel approach to S...

引用

International Conference on Very Large Scale Integration and System-on-Chip

作者： Chakraverty, Shampa Batra, Arvind Rathi, Aman Univ Delhi Dept Comp Engn Netaji Subhas Inst Technol New Delhi 110075 India

ISBN: (纸本)9783901882197

One of the fundamental problems encountered during the VLSI design flow is to find minimum length nets that connect specific nodes on the chip. The challenge lies in finding an efficient solution to the Steiner tree Problem in graphs (SPG) that not only maximizes the routing efficiency but also lends itself well for fast implementation. In this paper, we propose a new and innovative approach for solving the Steiner tree problem, called the "Directed Convergence Heuristic (DCH)". In essence, the DCH based algorithm places entities called pawns on nodes that need to be connected. These pawns move towards each other in a directed fashion and while doing so, leave trails for constructing a Steiner tree between the nodes. When all the pawns converge at a node, the trails merge to create a Steiner tree. Experimental results on benchmark Steiner trees show that DCH is robust and converges faster while yielding competitive near optimal solutions. The algorithm is amenable for implementation on parallel computing architectures.

关键词： SPG Steiner Tree global routing graph algorithm Convergence

来源：评论

学校读者我要写书评

暂无评论

Coordinated Navigation of Multi-Robot Systems with Binary Constraints

Coordinated Navigation of Multi-Robot Systems with Binary Co...

引用

IEEE/RSJ International Conference on Intelligent Robots and Systems

作者： Brueggemann, Bernd Schulz, Dirk Fraunhofer FKIE Unmanned Syst Grp D-53343 Wachtberg Germany

ISBN: (纸本)9781424466757

In this paper we present a method for navigating a multi-robot system through an environment while additionally maintaining a predefined set of constraints. Possible constraints are the requirement to keep up the direct line-of-sight between robots or to ensure that robots stay within a certain distance. Our approach is based on graph structures that model movements and constraints separately, in order to cover different robots and a large class of possible constraints. Additionally, the partition of movement and constraint graph allows us to use known graph algorithms like Steiner trees to solve the problem of finding a target configuration for the robots. We construct so called separated distance graphs from the Steiner tree and the underlying roadmap graph, which allow assembling valid navigation plans fast.

关键词： Sterner tree binary constraint coordinated navigation graph algorithm line-of-sight multi-robot systems multirobot system path planning roadmap graph robot vision separated distance graph trees (mathematics)

来源：评论

学校读者我要写书评

暂无评论

A Faster algorithm for Vertex Cover Parameterized by Solution Size 41

A Faster Algorithm for Vertex Cover Parameterized by Solutio...

引用

41st International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Harris, David G. Narayanaswamy, N. S. Univ Maryland Dept Comp Sci College Pk MD 20742 USA Indian Inst Technol Madras Dept Comp Sci & Engn Chennai Tamil Nadu India

ISBN: (纸本)9783959773119

We describe a new algorithm for vertex cover with runtime O* (1.25284(k)), where k is the size of the desired solution and 0* hides polynomial factors in the input size. This improves over the previous runtime of 0*(1.2738(k)) due to Chen, Kanj, & Xia (2010) standing for more than a decade. The key to our algorithm is to use a measure which simultaneously tracks k as well as the optimal value lambda of the vertex cover LP relaxation. This allows us to make use of prior algorithms for Maximum Independent Set in bounded-degree graphs and Above-Guarantee Vertex Cover. The main step in the algorithm is to branch on high-degree vertices, while ensuring that both k and mu = k - lambda are decreased at each step. There can be local obstructions in the graph that prevent it from decreasing in this process;we develop a number of novel branching steps to handle these situations.

关键词： Vertex cover FPT graph algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：