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

Collective additive tree spanners for circle graphs and polygonal graphs

DISCRETE APPLIED MATHEMATICS 2012年第12期160卷 1717-1729页

作者： Dragan, Feodor F. Corneil, Derek G. Koehler, Ekkehard Xiang, Yang Kent State Univ Algorithm Res Lab Dept Comp Sci Kent OH 44242 USA Univ Toronto Dept Comp Sci Toronto ON M5S 3G4 Canada Brandenburg Tech Univ Cottbus Math Inst D-03013 Cottbus Germany Ohio State Univ Dept Biomed Informat Columbus OH 43210 USA Ohio State Univ OSUCCC Biomed Informat Shared Resource Columbus OH 43210 USA

A graph G = (V, E) is said to admit a system of mu collective additive tree r-spanners if there is a system J (G) of at most it spanning trees of G such that for any two vertices u, v of G a spanning tree T is an element of J (G) exists such that the distance in T between u and v is at most r plus their distance in G. In this paper, we examine the problem of finding "small" systems of collective additive tree r-spanners for small values of r on circle graphs and on polygonal graphs. Among other results, we show that every n-vertex circle graph admits a system of at most 2 log 3/2 n collective additive tree 2-spanners and every n-vertex k-polygonal graph admits a system of at most 2 log 3/2 k + 7 collective additive tree 2-spanners. Moreover, we show that every n-vertex k-polygonal graph admits an additive (k + 6)-spanner with at most 6n - 6 edges and every n-vertex 3-polygonal graph admits a system of at most three collective additive tree 2-spanners and an additive tree 6-spanner. All our collective tree spanners as well as all sparse spanners are constructible in polynomial time. (C) 2012 Elsevier B.V. All rights reserved.

关键词： graph algorithms Collective additive tree spanners Circle graphs Polygonal graphs Balanced separators

来源：评论

学校读者我要写书评

暂无评论

ITERATED ROUNDING algorithms FOR THE SMALLEST k-EDGE CONNECTED SPANNING SUBgraph

引用

SIAM JOURNAL ON COMPUTING 2012年第1期41卷 61-103页

作者： Gabow, Harold N. Gallagher, Suzanne R. Univ Colorado Dept Comp Sci Boulder CO 80309 USA

We present the best known algorithms for approximating the minimum-size undirected k-edge connected spanning subgraph. For simple graphs our approximation ratio is 1 + 1/(2k) + O(1/k(2)). The more precise version of this bound requires k >= 7, and for all such k it improves the long-standing performance ratio of Cheriyan and Thurimella [SIAM J. Comput., 30 (2000), pp. 528-560], 1 + 2/(k + 1). The improvement comes in two steps. First we show that for simple k-edge connected graphs, any laminar family of degree k sets is smaller than the general bound (n(1 + 3/k + O(1/k root k)) versus 2n). This immediately implies that iterated rounding improves the performance ratio of Cheriyan and Thurimella. The second step carefully chooses good edges for rounding. For multigraphs our approximation ratio is 1+(21/11)k < 1 + 1.91/k for any k > 1. This improves the previous ratio 1 + 2/k [H. N. Gabow, M. X. Goemans, E. Tardos, and D. P. Williamson, Networks, 53 (2009), pp. 345-357]. It is of interest since it is known that for some constant c > 0, an approximation ratio <= 1 + c/k implies P = NP. Our approximation ratio extends to the minimum-size Steiner network problem, where k denotes the average vertex demand. The algorithm exploits rounding properties of the first two linear programs in iterated rounding.

关键词： approximation algorithms network design linear programming graph algorithms graph connectivity edge connectivity

来源：评论

学校读者我要写书评

暂无评论

Approximate weighted matching on emerging manycore and multithreaded architectures

引用

INTERNATIONAL JOURNAL OF HIGH PERFORMANCE COMPUTING APPLICATIONS 2012年第4期26卷 413-430页

作者： Halappanavar, Mahantesh Feo, John Villa, Oreste Tumeo, Antonino Pothen, Alex Pacific NW Natl Lab Computat Sci & Math Div Richland WA 99352 USA Purdue Univ W Lafayette IN 47907 USA

graph matching is a prototypical combinatorial problem with many applications in high-performance scientific computing. Optimal algorithms for computing matchings are challenging to parallelize. Approximation algorithms are amenable to parallelization and are therefore important to compute matchings for large-scale problems. Approximation algorithms also generate nearly optimal solutions that are sufficient for many applications. In this paper we present multithreaded algorithms for computing half-approximate weighted matching on state-of-the-art multicore (Intel Nehalem and AMD Magny-Cours), manycore (Nvidia Tesla and Nvidia Fermi), and massively multithreaded (Cray XMT) platforms. We provide two implementations: the first uses shared work queues and is suited for all platforms;and the second implementation, based on dataflow principles, exploits special features available on the Cray XMT. Using a carefully chosen dataset that exhibits characteristics from a wide range of applications, we show scalable performance across different platforms. In particular, for one instance of the input, an R-MAT graph (RMAT-G), we show speedups of about 32 on 48 cores of an AMD Magny-Cours, 7 on 8 cores of Intel Nehalem, 3 on Nvidia Tesla and 10 on Nvidia Fermi relative to one core of Intel Nehalem, and 60 on 128 processors of Cray XMT. We demonstrate strong as well as weak scaling for graphs with up to a billion edges using up to 12,800 threads. We avoid excessive fine-tuning for each platform and retain the basic structure of the algorithm uniformly across platforms. An exception is the dataflow algorithm designed specifically for the Cray XMT. To the best of the authors' knowledge, this is the first such large-scale study of the half-approximate weighted matching problem on multithreaded platforms. Driven by the critical enabling role of combinatorial algorithms such as matching in scientific computing and the emergence of informatics applications, there is a growing demand to s

关键词： approximation dataflow GPU graph algorithms manycore matching multicore weighted matching

来源：评论

学校读者我要写书评

暂无评论

On Exact algorithms for Treewidth

引用

ACM TRANSACTIONS ON algorithms 2012年第1期9卷 1–23页

作者： Bodlaender, Hans L. Fomin, Fedor V. Koster, Arie M. C. A. Kratsch, Dieter Thilikos, Dimitrios M. Univ Utrecht Dept Informat & Comp Sci NL-3508 TB Utrecht Netherlands Univ Bergen Dept Informat N-5020 Bergen Norway Univ Aachen Aachen Germany Univ Metz LITA F-507045 Metz 01 France Univ Athens GR-10679 Athens Greece

We give experimental and theoretical results on the problem of computing the treewidth of a graph by exact exponential-time algorithms using exponential space or using only polynomial space. We first report on an implementation of a dynamic programming algorithm for computing the treewidth of a graph with running time O*(2(n)). This algorithm is based on the old dynamic programming method introduced by Held and Karp for the TRAVELING SALESMAN problem. We use some optimizations that do not affect the worst case running time but improve on the running time on actual instances and can be seen to be practical for small instances. We also consider the problem of computing TREEWIDTH under the restriction that the space used is only polynomial and give a simple O*(4(n)) algorithm that requires polynomial space. We also show that with a more complicated algorithm using balanced separators, TREEWIDTH can be computed in O*(2.9512(n)) time and polynomial space.

关键词： algorithms Design Theory Experimentation graph algorithms exact algorithms treewidth dynamic programming separators

来源：评论

学校读者我要写书评

暂无评论

L(2,1)-labeling of dually chordal graphs and strongly orderable graphs

引用

INFORMATION PROCESSING LETTERS 2012年第13期112卷 552-556页

作者： Panda, B. S. Goel, Preeti Indian Inst Technol Delhi Dept Math Comp Sci & Applicat Grp New Delhi 110016 India

An L(2, 1)-labeling of a graph G = (V, E) is a function f : V (G) -> {0, 1, ...,} such that vertical bar f(u) - f(v)vertical bar >= 2 whenever uv is an element of E(G) and vertical bar f (u) - f(v)vertical bar >= 1 whenever u and v are at distance two apart. The span of an L(2. 1)-labeling f of G, denoted as SP2(f. G), is the maximum value of f (x) over all x is an element of V (G). The L(2, 1)-labeling number of a graph G, denoted as lambda(G), is the least integer k such that G admits an L(2.1)-labeling of span k. The problem of computing lambda(G) of a graph is known to be NP-complete. Griggs and Yeh have conjectured that lambda(G) <= Delta(2)(G) for a graph G with maximum degree, Delta(G), at least two. In this paper, we propose constant approximation algorithms for the problem of computing lambda(G) for dually chordal graphs and strongly orderable graphs. As a by-product, we prove Griggs and Yell Conjecture for dually chordal graphs and for those strongly orderable graphs whose maximum degrees are different from three. Finally, we propose a 2-approximation algorithm for computing lambda(G) for chordal bipartite graphs, a special subclass of strongly orderable graphs, and prove that Griggs and Yeh Conjecture holds true for this class of graphs. (C) 2012 Elsevier B.V. All rights reserved.

关键词： L(2,1)-labeling Strongly orderable graphs Dually chordal graphs Chordal bipartite graphs graph algorithms Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

A self-stabilizing algorithm to maximal 2-packing with improved complexity

引用

INFORMATION PROCESSING LETTERS 2012年第13期112卷 525-531页

作者： Shi, Zhengnan Univ Wisconsin Dept Math & Comp Sci Whitewater WI 53190 USA

In self-stabilization, each node has a local view of the distributed network system, in a finite amount of time the system converges to a global setup with desired property, in this case establishing a 2-packing set. Using a graph G = (V. E) to represent the network, a subset S subset of V is a 2-packing if for all i is an element of V: vertical bar N vertical bar i vertical bar boolean AND S vertical bar <= 1. In this paper, we first propose an ID-based. constant space, self-stabilizing algorithm that stabilizes to a maximal 2-packing in an arbitrary graph. We show that the algorithm stabilizes in O(mm) moves under any scheduler (such as a distributed daemon). Secondly, we show that the algorithm stabilizes in O(n(2)) rounds under a synchronous daemon where every privileged node moves at each round. Published by Elsevier B.V.

关键词： Self-stabilization 2-packing Distributed computing Fault tolerance graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Angular Embedding: A Robust Quadratic Criterion

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2012年第1期34卷 158-173页

作者： Yu, Stella X. Boston Coll Dept Comp Sci Chestnut Hill MA 02467 USA

Given the size and confidence of pairwise local orderings, angular embedding (AE) finds a global ordering with a near-global optimal eigensolution. As a quadratic criterion in the complex domain, AE is remarkably robust to outliers, unlike its real domain counterpart LS, the least squares embedding. Our comparative study of LS and AE reveals that AE's robustness is due not to the particular choice of the criterion, but to the choice of representation in the complex domain. When the embedding is encoded in the angular space, we not only have a nonconvex error function that delivers robustness, but also have a Hermitian graph Laplacian that completely determines the optimum and delivers efficiency. The high quality of embedding by AE in the presence of outliers can hardly be matched by LS, its corresponding L-1 norm formulation, or their bounded versions. These results suggest that the key to overcoming outliers lies not with additionally imposing constraints on the embedding solution, but with adaptively penalizing inconsistency between measurements themselves. AE thus significantly advances statistical ranking methods by removing the impact of outliers directly without explicit inconsistency characterization, and advances spectral clustering methods by covering the entire size-confidence measurement space and providing an ordered cluster organization.

关键词： Least squares methods spectral methods graph algorithms constrained optimization linear programming statistical computing clustering modeling and recovery of physical attributes

来源：评论

学校读者我要写书评

暂无评论

Linear-Time Algorithm for the Paired-Domination Problem in Convex Bipartite graphs

引用

THEORY OF COMPUTING SYSTEMS 2012年第4期50卷 721-738页

作者： Hung, Ruo-Wei Chaoyang Univ Technol Dept Comp Sci & Informat Engn Taichung 41349 Taiwan

A bipartite graph G=(U,W,E) with vertex set V=Ua(a)W is convex if there exists an ordering of the vertices of W such that for each uaU, the neighbors of u are consecutive in W. A compact representation of a convex bipartite graph for specifying such an ordering can be computed in O(|V|+|E|) time. The paired-domination problem on bipartite graphs has been shown to be NP-complete. The complexity of the paired-domination problem on convex bipartite graphs has remained unknown. In this paper, we present an O(|V|) time algorithm to solve the paired-domination problem on convex bipartite graphs given a compact representation. As a byproduct, we show that our algorithm can be directly applied to solve the total domination problem on convex bipartite graphs in the same time bound.

关键词： graph algorithms Linear-time algorithms Paired-domination Total domination Convex bipartite graphs

来源：评论

学校读者我要写书评

暂无评论

Algorithmic aspects of k-tuple total domination in graphs

引用

INFORMATION PROCESSING LETTERS 2012年第21期112卷 816-822页

作者： Pradhan, D. Indian Inst Sci Dept Comp Sci & Automat Bangalore 560012 Karnataka India

For a fixed positive integer k, a k-tuple total dominating set of a graph G = (V. E) is a subset T D-k of V such that every vertex in V is adjacent to at least k vertices of T Dk. In minimum k-tuple total dominating set problem (MIN k-TUPLE TOTAL DOM SET), it is required to find a k-tuple total dominating set of minimum cardinality and DECIDE MIN k-TUPLE TOTAL DOM SET is the decision version of MIN k-TUPLE TOTAL DOM SET problem. In this paper, we show that DECIDE MIN k-TUPLE TOTAL DOM SET is NP-complete for split graphs, doubly chordal graphs and bipartite graphs. For chordal bipartite graphs, we show that MIN k-TUPLE TOTAL DOM SET can be solved in polynomial time. We also propose some hardness results and approximation algorithms for MIN k-TUPLE TOTAL DOM SET problem. (c) 2012 Elsevier B.V. All rights reserved.

关键词： graph algorithms Domination Total domination k-Tuple total domination NP-complete APX-complete

来源：评论

学校读者我要写书评

暂无评论

Coloring chip configurations on graphs and digraphs

引用

INFORMATION PROCESSING LETTERS 2012年第1-2期112卷 1-4页

作者： Borowiecki, Mieczyslaw Grytczuk, Jaroslaw Pilsniak, Monika Warsaw Univ Technol Fac Math & Informat Sci PL-00661 Warsaw Poland Univ Zielona Gora Fac Math Comp Sci & Econometr PL-65516 Zielona Gora Poland AGH Univ Sci & Technol Fac Appl Math PL-30059 Krakow Poland

Let D be a simple directed graph. Suppose that each edge of D is assigned with some number of chips. For a vertex v of D, let q(+)(v) and q(-)(v) be the total number of chips lying on the arcs outgoing form v and incoming to v, respectively. Let q(v) = q(+)(v) - q(-)(v). We prove that there is always a chip arrangement, with one or two chips per edge, such that q(v) is a proper coloring of D. We also show that every undirected graph G can be oriented so that adjacent vertices have different balanced degrees (or even different in-degrees). The arguments are based on peculiar chip shifting operation which provides efficient algorithms for obtaining the desired chip configurations. We also investigate modular versions of these problems. We prove that every k-colorable digraph has a coloring chip configuration modulo k or k + 1. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Combinatorial problems graph algorithms graph coloring

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：