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

Approximating the minimum cycle mean

THEORETICAL COMPUTER SCIENCE 2014年第C期547卷 104-116页

作者： Chatterjee, Krishnendu Henzinger, Monika Krinninger, Sebastian Loitzenbauer, Veronika Raskin, Michael A. IST Austria A-3400 Klosterneuburg Austria Univ Vienna Fac Comp Sci A-1090 Vienna Austria Independent Univ Moscow Moscow 115162 Russia Moscow Inst Phys & Technol Dolgoprudnyi 141700 Russia

We consider directed graphs where each edge is labeled with an integer weight and study the fundamental algorithmic question of computing the value of a cycle with minimum mean weight. Our contributions are twofold: (1) First we show that the algorithmic question is reducible to the problem of a logarithmic number of min-plus matrix multiplications of n x n-matrices, where n is the number of vertices of the graph. (2) Second, when the weights are nonnegative, we present the first (1 + is an element of)-approximation algorithm for the problem and the running time of our algorithm is (O) over tilde (n(omega) log(3) (nW/is an element of)/is an element of),(1) where O(n(omega)) is the time required for the classic n x n-matrix multiplication and W is the maximum value of the weights. With an additional O(log(nW/is an element of)) factor in space a cycle with approximately optimal weight can be computed within the same time bound. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Quantitative verification graph algorithm Mean-payoff objective Approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Shortest Paths in Euclidean graphs

引用

algorithmICA 1986年第1-4期1卷 31-48页

作者： Sedgewick, Robert Vitter, Jeffrey Scott Brown Univ Dept Comp Sci Providence RI 02912 USA

We analyze a simple method for finding shortest paths in Euclidean graphs (where vertices are points in a Euclidean space and edge weights are Euclidean distances between points). For many graph models, the average running time of the algorithm to find the shortest path between a specified pair of vertices in a graph with V vertices and E edges is shown to be O(V) as compared with O(E + V log V) required by the classical algorithm due to Dijkstra.

关键词： Analysis of algorithms graph algorithm Shortest path Euclidean Heuristic Dijkstra's algorithm Priority queue

来源：评论

学校读者我要写书评

暂无评论

Efficient object-oriented integration and regression testing

引用

IEEE TRANSACTIONS ON RELIABILITY 2000年第1期49卷 12-25页

作者： Le Traon, Y Jéron, T Jézéquel, JM Morel, P Inst Rech Informat & Syst Aleatoires F-35042 Rennes France

This paper presents a model, a strategy, and a methodology for planning integration and regression testing from an object-oriented model, It shows how to produce a model of structural system test dependencies which evolves with the refinement process of the object-oriented design. The model (test dependency graph! serves as a basis for ordering classes and methods to be tested for regression and integration purposes (minimization of test stubs). The mapping from Unified Modeling Language to the defined model is detailed as well as the test methodology. While the complexity of optimal stub minimization is exponential with the size of the model, an algorithm is given that: computes a strategy for integration testing with a quadratic complexity in the worst case, provides an efficient testing order for minimizing the number of stubs. Various integration strategies are compared with the optimized algorithm (a real-world case study illustrates this comparison), The results of the experiment seem to give nearly optimal stubs with a low cost despite the exponential complexity of getting optimal stubs. As being a part of a design-for-testability approach, the presented methodology also leads to the early repartition of testing resources during system integration for reducing integration duration.

关键词： graph algorithm integration testing object-oriented modeling regression testing software testing

来源：评论

学校读者我要写书评

暂无评论

Minimum cut linear arrangement of p-q dags for VLSI layout of adder trees

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 1999年第5期E82A卷 767-774页

作者： Takagi, K Takagi, N Nara Inst Sci & Technol Grad Sch Informat Sci Ikoma 6300101 Japan Nagoya Univ Dept Informat Engn Nagoya Aichi 4648603 Japan

Two algorithms for minimum cut linear arrangement of a class of graphs called p-q dags are proposed. A p-q dag represents the connection scheme of an adder tree, such as Wallace tree, and the VLSI layout problem of a bit slice of an adder tree is treated as the minimum cut linear arrangement problem of its corresponding p-q dag. One of the two algorithms is based on dynamic programming. It calculates an exact minimum solution within n(O(1)) time and space, where n is the size of a given graph. The other algorithm is an approximation algorithm which calculates a solution with O(log n) cutwidth. It requires O(n log n) time.

关键词： graph algorithm minimum cut linear arrangement VLSI layout adder tree multiplier

来源：评论

学校读者我要写书评

暂无评论

On the complexity of reconfiguration problems

引用

THEORETICAL COMPUTER SCIENCE 2011年第12-14期412卷 1054-1065页

作者： Ito, Takehiro Demaine, Erik D. Harvey, Nicholas J. A. Papadimitriou, Christos H. Sideri, Martha Uehara, Ryuhei Uno, Yushi Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 9808579 Japan MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA Univ Waterloo Dept Combinator & Optimizat Waterloo ON N2L 3G1 Canada Univ Calif Berkeley Div Comp Sci Dept EECS Berkeley CA 94720 USA Athens Univ Econ & Business Dept Comp Sci Athens 10434 Greece JAIST Sch Informat Sci Nomi Ishikawa 9231292 Japan Osaka Prefecture Univ Grad Sch Sci Naka Ku Sakai Osaka 5998531 Japan

Reconfiguration problems arise when we wish to find a step-by-step transformation between two feasible solutions of a problem such that all intermediate results are also feasible. We demonstrate that a host of reconfiguration problems derived from NP-complete problems are PSPACE-complete, while some are also NP-hard to approximate. In contrast, several reconfiguration versions of problems in P are solvable in polynomial time. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Approximation graph algorithm PSPACE-complete Reachability on solution space

来源：评论

学校读者我要写书评

暂无评论

Linear-time algorithm for sliding tokens on trees

引用

THEORETICAL COMPUTER SCIENCE 2015年 600卷 132-142页

作者： Demaine, Erik D. Demaine, Martin L. Fox-Epstein, Eli Hoang, Duc A. Ito, Takehiro Ono, Hirotaka Otachic, Yota Uehara, Ryuhei Yamada, Takeshi MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA Brown Univ Dept Comp Sci Providence RI 02912 USA Japan Adv Inst Sci & Technol Sch Informat Sci Nomi Ishikawa 9231292 Japan Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 9808579 Japan JST CREST Kawaguchi Saitama 3320012 Japan Kyushu Univ Fac Econ Higashi Ku Fukuoka 8128581 Japan

Suppose that we are given two independent sets I-b and I-r of a graph such that vertical bar l(b)vertical bar =vertical bar I-r vertical bar and imagine that a token is placed on each vertex in I-b. Then, the SLIDING TOKEN problem is to determine whether there exists a sequence of independent sets which transforms I-b into I-r so that each independent set in the sequence results from the previous one by sliding exactly one token along an edge in the graph. This problem is known to be PSPACE-complete even for planar graphs, and also for bounded treewidth graphs. In this paper, we thus study the problem restricted to trees, and give the following three results: (1) the decision problem is solvable in linear time;(2) for a yes-instance, we can find in quadratic time an actual sequence of independent sets between I-b and I-r whose length (i.e., the number of token-slides) is quadratic;and (3) there exists an infinite family of instances on paths for which any sequence requires quadratic length. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Combinatorial reconfiguration graph algorithm Independent set Sliding token Tree

来源：评论

学校读者我要写书评

暂无评论

Wavelength conversion in all-optical networks with shortest-path routing

引用

algorithmICA 2005年第1-2期43卷 43-61页

作者： Erlebach, T Stefanakos, S Univ Leicester Dept Comp Sci Leicester LE1 7RH Leics England ETH Comp Engn & Networks Lab CH-8092 Zurich Switzerland

We consider all-optical networks with shortest-path routing that use wavelength-division multiplexing and employ wavelength conversion at specific nodes in order to maximize their capacity usage. We present efficient algorithms for deciding whether a placement of wavelength converters allows the network to run at maximum capacity, and for finding an optimal wavelength assignment when such a placement of converters is known. Our algorithms apply to both undirected and directed networks. Furthermore, we show that the problem of designing such networks, i.e., finding an optimal placement of converters, is MAX SNP-hard in both the undirected and the directed case. Finally, we give a linear-time algorithm for finding an optimal placement of converters in undirected triangle-free networks, and show that the problem remains NP-hard in bidirected triangle-free planar networks.

关键词： wavelength assignment wavelength converter placement graph algorithm edge coloring bipartization sufficient set L-reduction

来源：评论

学校读者我要写书评

暂无评论

An algorithm for two-dimensional rigidity percolation: The pebble game

引用

JOURNAL OF COMPUTATIONAL PHYSICS 1997年第2期137卷 346-365页

作者： Jacobs, DJ Hendrickson, B SANDIA NATL LABS ALBUQUERQUENM 87185

Many important macroscopic properties of materials depend upon the number of microscopic degrees of freedom. The task of counting the number of such degrees of freedom can be computationally very expensive. We describe a new approach for this calculation which is appropriate for two-dimensional, glass-like networks, building upon recent work in graph rigidity. This purely combinatorial algorithm is formulated in terms of a simple pebble game. It has allowed for the first studies of the rigidity transition in generic networks. which are models of amorphous materials and glasses. In the context of generic rigidity percolation, we show how to calculate the number of internal degrees of freedom, identify all rigid clusters, and locate the overconstrained regions. For a network of rr sites the pebble game has a worst case performance of O(n(2)). In our applications its performance scaled as n(1.15) at the rigidity transition, while away from the transition region it grew linearly. (C) 1997 Academic Press.

关键词： rigidity percolation graph rigidity graph algorithm vector percolation floppy modes network glass

来源：评论

学校读者我要写书评

暂无评论

Complexity of finding maximum regular induced subgraphs with prescribed degree

引用

THEORETICAL COMPUTER SCIENCE 2014年第C期550卷 21-35页

作者： Asahiro, Yuichi Eto, Hiroshi Ito, Takehiro Miyano, Eiji Kyushu Sangyo Univ Dept Informat Sci Fukuoka 8138503 Japan Kyushu Inst Technol Dept Syst Design & Informat Fukuoka 8208502 Japan Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 9808579 Japan

We study the problem of finding a maximum vertex-subset S of a given graph G such that the subgraph G[S] induced by S is r-regular for a prescribed degree r >= 0. We also consider a variant of the problem which requires G[S] to be r-regular and connected. Both problems are known to be NP-hard even to approximate for a fixed constant r. In this paper, we thus consider the problems whose input graphs are restricted to some special classes of graphs. We first show that the problems are still NP-hard to approximate even if r is a fixed constant and the input graph is either bipartite or planar. On the other hand, both problems are tractable for graphs having tree-like structures, as follows. We give linear-time algorithms to solve the problems for graphs with bounded treewidth;we note that the hidden constant factor of our running time is just a single exponential of the treewidth. Furthermore, both problems are solvable in polynomial time for chordal graphs. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Bipartite graph Chordal graph graph algorithm Inapproximability Planar graph Regular induced subgraph Treewidth

来源：评论

学校读者我要写书评

暂无评论

An Exact algorithm for TSP in Degree-3 graphs Via Circuit Procedure and Amortization on Connectivity Structure

引用

algorithmICA 2016年第2期74卷 713-741页

作者： Xiao, Mingyu Nagamochi, Hiroshi Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu 610054 Peoples R China Kyoto Univ Dept Appl Math & Phys Grad Sch Informat Kyoto 606 Japan

The paper presents an -time and polynomial-space algorithm for the traveling salesman problem in an -vertex graph with maximum degree 3. This improves all previous time bounds of polynomial-space algorithms for this problem. Our algorithm is a simple branch-and-search algorithm with only one branch rule designed on a cut-circuit structure of a graph induced by unprocessed edges. To improve a time bound by a simple analysis on measure and conquer, we introduce an amortization scheme over the cut-circuit structure by defining the measure of an instance to be the sum of not only weights of vertices but also weights of connected components of the induced graph.

关键词： Traveling salesman problem Exact exponential algorithm graph algorithm Connectivity Measure and conquer

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：