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

2011 International Conference on Frontiers in Computer Education(ICFCE 2011)

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

The traditional network flow estimation requires monitoring on every node which consumes too much resourceSo how to increase the deployment of new distributed monitors as the network expanding is becoming a new research focusThis paper analyses the monitors adding mechanism and present a novel algorithm for finding candidate locations for additional deployment in the networkThe algorithm is based on Apriori search method that combines with the link weight change algorithm that aims to facilitate origin-destination flow computationWe also develop the greedy algorithm with Group Betweenness Centrality(GBC) involved for the purpose of comparingThe result shows that the new algorithm need less additional monitors than greedy algorithm.

关键词： Group Betweenness flow estimation Network Centrality graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Finding a maximum-weight induced k-partite subgraph of an i-triangulated graph

引用

DISCRETE APPLIED MATHEMATICS 2010年第7期158卷 765-770页

作者： Addario-Berry, Louigi Kennedy, W. S. King, Andrew D. Li, Zhentao Reed, Bruce McGill Univ Sch Comp Sci Montreal PQ Canada

An i-triangulated graph is a graph in which every odd cycle has two non-crossing chords;i-triangulated graphs form a subfamily of perfect graphs. A slightly more general family of perfect graphs are clique-separable graphs. A graph is clique-separable precisely if every induced subgraph either has a clique cutset, or is a complete multipartite graph or a clique joined to an arbitrary bipartite graph. We exhibit a polynomial time algorithm for finding a maximum-weight induced k-partite subgraph of an i-triangulated graph, and show that the problem of finding a maximum-size bipartite induced subgraph in a clique-separable graph is NP-complete. (c) 2008 Elsevier B.V. All rights reserved.

关键词： graph algorithm Clique-separable graph i-triangulated graph Tree decomposition

来源：评论

学校读者我要写书评

暂无评论

Greedy algorithms for generalized k-rankings of paths

引用

INFORMATION PROCESSING LETTERS 2010年第22期110卷 979-985页

作者： Zemke, Andrew James, Sandra Narayan, Darren A. Rochester Inst Technol Sch Math Sci Rochester NY 14623 USA Concordia Univ Dept Math St Paul MN 55104 USA

A k-ranking of a graph is a labeling of the vertices with positive integers 1,2, ..., k so that every path connecting two vertices with the same label contains a vertex of larger label. An optimal ranking is one in which k is minimized. Let P-n, be a path with n vertices. A greedy algorithm can be used to successively label each vertex with the smallest possible label that preserves the ranking property. We seek to show that when a greedy algorithm is used to label the vertices successively from left to right, we obtain an optimal ranking. A greedy algorithm of this type was given by Bodlaender et al. in 1998 [1] which generates an optimal k-ranking of P-n. In this paper we investigate two generalizations of rankings. We first consider bounded (k, s)-rankings in which the number of times a label can be used is bounded by a predetermined integer s. We then consider k(t)-rankings where any path connecting two vertices with the same label contains t vertices with larger labels. We show for both generalizations that when G is a path, the analogous greedy algorithms generate optimal k-rankings. We then proceed to quantify the minimum number of labels that can be used in these rankings. We define the bounded rank number (r,s)(G) to be the smallest number of labels that can be used in a (k, s)-ranking and show for n 2, (r,s)(P-n) = [ ((n (2 1))/s)] + i where i = [log(2)(s)] + 1. We define the k(t)-rank number, (t)(r)(G) to be the smallest number of labels that can be used in a k(t)-ranking. We present a recursive formula that gives the k(t)-rank numbers for paths, showing 1;.(P-j) n for all a(n-1) < j <= a(n) where {a(n)) is defined as follows: a(l) = 1 and a(n) = a(n) = [((t + 1)/t)a(n-1)] + 1. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Rank number Ordered coloring Minimal ranking Vertex coloring Greedy algorithm graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Approximation to the Minimum Cost Edge Installation Problem

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2010年第4期E93A卷 778-786页

作者： Morsy, Ehab Nagamochi, Hiroshi Kyoto Univ Dept Appl Math & Phys Grad Sch Informat Kyoto 6068501 Japan

We consider the minimum cost edge installation problem (MCEI) in a graph G = (V, E) with edge weight w(e) >= 0. e is an element of E We are given a vertex s is an element of V designated as a sink, an edge capacity lambda > 0. and a source set S subset of V with demand q(v) is an element of |0,lambda|, v is an element of S For each edge e is an element of E. we are allowed to install an integer number h(e) of copies of e MCEI asks to send demand q(v) from each source v is an element of S along a single path P-v to the sink without splitting the demand of any source v is an element of S For each edge e is an element of E. a set of such paths can pass through a single copy of e in C as long as the total demand along the paths does not exceed the edge capacity lambda The objective is to find a set P = {P-v | v is an element of S} of paths of G that minimizes the installing cost Sigma(eCE) h(e)w(e) In this paper. we propose a (15/8 + rho(ST))-approximation algorithm to MCEI. where rho(SI) is any approximation ratio achievable tor the Steiner tree problem

关键词： approximation algorithm graph algorithm routing problem network optimization

来源：评论

学校读者我要写书评

暂无评论

Solving path problems on the GPU

引用

PARALLEL COMPUTING 2010年第5-6期36卷 241-253页

作者： Buluc, Aydin Gilbert, John R. Budak, Ceren Univ Calif Santa Barbara Dept Comp Sci Santa Barbara CA 93106 USA

We consider the computation of shortest paths on graphic Processing Units (GPUs). The blocked recursive elimination strategy we use is applicable to a class of algorithms (such as all-pairs shortest-paths, transitive closure, and LU decomposition without pivoting) having similar data access patterns. Using the all-pairs shortest-paths problem as an example, we uncover potential gains over this class of algorithms. The impressive computational power and memory bandwidth of the CPU make it an attractive platform to run such computationally intensive algorithms. Although improvements over CPU implementations have previously been achieved for those algorithms in terms of raw speed, the utilization of the underlying computational resources was quite low. We implemented a recursively partitioned all-pairs shortest-paths algorithm that harnesses the power of GPUs better than existing implementations. The alternate schedule of path computations allowed us to cast almost all operations into matrix-matrix multiplications on a semiring. Since matrix-matrix multiplication is highly optimized and has a high ratio of computation to communication, our implementation does not suffer from the premature saturation of bandwidth resources as iterative algorithms do. By increasing temporal locality, our implementation runs more than two orders of magnitude faster on an NVIDIA 8800 CPU than on an Opteron. Our work provides evidence that programmers should rethink algorithms instead of directly porting them to CPU. (C) 2009 Elsevier By. All rights reserved.

关键词： All-pairs shortest-paths Gaussian elimination graphical processing unit Semiring Matrix multiplication graph algorithm Shortest path Linear algebra

来源：评论

学校读者我要写书评

暂无评论

Crossing minimization in extended level drawings of graphs

引用

DISCRETE APPLIED MATHEMATICS 2010年第3期158卷 159-179页

作者： Bachmaier, Christian Buchner, Hedi Forster, Michael Hong, Seok-Hee Univ Passau Fac Inf & Math D-94030 Passau Germany Natl ICT Australia IMAGEN Program Eveleigh NSW 1430 Australia Univ Sydney Sch Informat Technol Sydney NSW 2006 Australia

The most popular method of drawing directed graphs is to place vertices on a set of horizontal or concentric levels, known as level drawings. Level drawings are well studied in graph Drawing due to their strong application for the visualization of hierarchy in graphs. There are two drawing conventions: Horizontal drawings use a set of parallel lines and radial drawings use a set of concentric circles. In level drawings, edges are only allowed between vertices on different levels. However, many real world graphs exhibit hierarchies with edges between vertices on the same level. In this paper, we initiate the new problem of extended level drawings of graphs, which was addressed as one of the open problems in social network visualization, in particular, displaying centrality values of actors. More specifically, we study minimizing the number of edge crossings in extended level drawings of graphs. The main problem can be formulated as the extended one-sided crossing minimization problem between two adjacent levels, as it is folklore with the one-sided crossing minimization problem in horizontal drawings. We first show that the extended one-sided crossing minimization problem is N P-hard for both horizontal and radial drawings, and then present efficient heuristics for minimizing edge crossings in extended level drawings. Our extensive experimental results show that our new methods reduce up to 30% of edge crossings. (C) 2009 Elsevier B.V. All rights reserved.

关键词： (Radial) level graph Crossing minimization Intra-level edges Hierarchy Level/layered drawing Visualization of social networks graph algorithm

来源：评论

学校读者我要写书评

暂无评论

A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2010年第4期70卷 406-415页

作者： Guellati, Nabil Kheddouci, Hamamache Univ Abderrahmane Mira Dept Comp Sci Bejaia Algeria Univ Lyon 1 LIESP Lab F-69365 Lyon France

Dijkstra defined a distributed system to be self-stabilizing if, regardless of the initial state, the system is guaranteed to reach a legitimate (correct) state in a finite time. Even though the concept of self-stabilization received little attention when it was introduced, it has become one of the most popular fault tolerance approaches. On the other hand, graph algorithms form the basis of many network protocols. They are used in routing, clustering, multicasting and many other tasks. The objective of this paper is to survey the self-stabilizing algorithms for dominating and independent set problems, colorings, and matchings. These graph theoretic problems are well studied in the context of self-stabilization and a large number of algorithms have been proposed for them. (C) 2009 Elsevier Inc. All rights reserved.

关键词： Distributed algorithm Self-stabilization graph algorithm Independence Domination Coloring Matching

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Approximation algorithms for Minimizing Edge Crossings in Radial Drawings

引用

algorithmICA 2010年第2期58卷 478-497页

作者： Hong, Seok-Hee Nagamochi, Hiroshi Kyoto Univ Dept Appl Math & Phys Kyoto 606 Japan Univ Sydney Sch Informat Technol Sydney NSW 2006 Australia

We study a crossing minimization problem of drawing a bipartite graph with a radial drawing of two orbits. Radial drawings are one of well-known drawing conventions in social network analysis and visualization, in particular, displaying centrality indices of actors (Wasserman and Faust, Social Network Analysis: Methods and Applications. Cambridge University Press, Cambridge, 1994). The main problem in this paper is called the one-sided radial crossing minimization, if the positions of vertices in the outer orbit are fixed. The problem is known to be NP-hard (Bachmaier, IEEE Trans. Vis. Comput. graph. 13, 583-594, 2007), and a number of heuristics are available (Bachmaier, IEEE Trans. Vis. Comput. graph. 13, 583-594, 2007). However, there is no approximation algorithm for the crossing minimization problem in radial drawings. We present the first polynomial time constant-factor approximation algorithm for the one-sided radial crossing minimization problem.

关键词： graph drawing Layered drawing Level drawing Hierarchical drawing Radial drawing Crossing minimization Approximation algorithm graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Complexity of the packing coloring problem for trees

引用

DISCRETE APPLIED MATHEMATICS 2010年第7期158卷 771-778页

作者： Fiala, Jiri Golovach, Petr A. Univ Bergen Dept Informat N-5020 Bergen Norway Charles Univ Prague Dept Appl Math CR-11800 Prague Czech Republic Charles Univ Prague Inst Theoret Comp Sci ITI CR-11800 Prague Czech Republic

Packing coloring is a partitioning of the vertex set of a graph with the property that vertices in the i-th class have pairwise distance greater than i. The main result of this paper is a solution of an open problem of Goddard et al. showing that the decision whether a tree allows a packing coloring with at most k classes is NP-complete. We further discuss specific cases when this problem allows an efficient algorithm. Namely, we show that it is decideable in polynomial time for graphs of bounded treewidth and diameter, and fixed parameter tractable for chordal graphs. We accompany these results by several observations on a closely related variant of the packing coloring problem, where the lower bounds on the distances between vertices inside color classes are determined by an infinite nondecreasing sequence of bounded integers. (c) 2008 Elsevier B.V. All rights reserved.

关键词： Packing coloring Computational complexity graph algorithm Chordal graph

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：