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

International Conference on Software Maintenance

作者： Salecker, Elke Glesner, Sabine Berlin Inst Technol TU Berlin Berlin Germany

ISBN: (纸本)9781424486298

of input values and can be detected using pairwise test sets that cover each pair of input values. The generation of pairwise test sets with a minimal size is an NP-complete problem which implies that many algorithms are either expensive or based on a random process. In this paper we present a deterministic algorithm that exploits our observation that the pairwise testing problem can be modeled as a k-partite graph problem. We calculate the test set using well investigated graph algorithms that take advantage of properties of k-partite graphs. We present evaluation results that prove the applicability of our algorithm and discuss possible improvement of our approach.

关键词： NP-complete problem computational complexity deterministic algorithm deterministic algorithms fault diagnosis graph theory k-partite graph problem k-partite graphs pairwise test set calculation pairwise testing problem program testing random process software fault tolerance software faults

来源：评论

学校读者我要写书评

暂无评论

Fixed Outline Multi-Bend Bus Driven Floorplanning

Fixed Outline Multi-Bend Bus Driven Floorplanning

引用

11th International Symposium on Quality Electronic Design (ISQED)

作者： Sheng, Wenxu Dong, Sheqin Wu, Yuliang Goto, Satoshi Tsinghua Univ Tsinghua Natl Lab Informat Sci & Technol Beijing 100084 Peoples R China Chinese Univ Hong Kong Dept Comp Sci & Engn Shatin Hong Kong Peoples R China Waseda Univ Informat Prod & Syst Kitakyushu Fukuoka 8080135 Japan

ISBN: (纸本)9781424464555

Modern hierarchical SOC design flows need to deal with fixed-outline floorplanning under the interconnect constraints, in this paper, we address the problem of bus driven floorplanning in a fixed-outline area. Given a set of blocks, the bus specification, and the height and width of the chip area, a floorplan solution including bus routes and satisfying the outline constraint will be generated with the total floorplan area and total bus area minimized The approach proposed in this paper is based on a deterministic algorithm Less Flexibility First (LFF), which runs in a fixed outline area and packs hard blocks one after another with no drawbacks. In our approach, we put no limitation to the shape of the buses, and the processes block-packing and bus packing are proceeding simultaneously. Experiment results show that under the constraint of fixed-outline, we can also obtain a good solution, with less dead space percentage and shorter run time, besides, for large test cases, our algorithm still works well.

关键词： Bus planning Fixed outline deterministic algorithm Floorplanning

来源：评论

学校读者我要写书评

暂无评论

deterministic 7/8-approximation for the metric maximum TSP

引用

THEORETICAL COMPUTER SCIENCE 2009年第47-49期410卷 5000-5009页

作者： Kowalik, Lukasz Mucha, Marcin Univ Warsaw Inst Informat PL-00913 Warsaw Poland

We present the first 7/8-approximation algorithm for the maximum Traveling Salesman Problem (MAX-TSP) with triangle inequality. Our algorithm is deterministic. This improves over both the randomized algorithm of Hassin and Rubinstein [R. Hassin, S. Rubinstein, A 7/8-approximation algorithm for metric Max TSP, Inf Process. Lett. 81 (5) (2002) 247-251] with an expected approximation ratio of 7/8 - O(n(-1/2)) and the deterministic (7/8 - O(n(-1/3)))-approximation algorithm of Chen and Nagoya [Z.-Z. Chen, T. Nagoya, Improved approximation algorithms for metric max TSP, in: Proc. ESA'05, 2005, pp. 179-190]. In the new algorithm, we extend the approach of processing local configurations using the so-called loose-ends. which we introduced in [L Kowalik, M. Mucha, 35/44-approximation for asymmetric maximum TSP with triangle inequality, in: Proc. 10th Workshop on algorithms and Data Structures, WADS'07, 2007, pp. 590-601]. (C) 2009 Elsevier B.V. All rights reserved.

关键词： The Traveling Salesman Problem Approximation deterministic algorithm

来源：评论

学校读者我要写书评

暂无评论

On the Black-Box Complexity of Sperner's Lemma

引用

THEORY OF COMPUTING SYSTEMS 2009年第3期45卷 629-646页

作者： Friedl, Katalin Ivanyos, Gabor Santha, Miklos Verhoeven, Yves F. Budapest Univ Technol & Econ H-1521 Budapest Hungary Hungarian Acad Sci Comp & Automat Res Inst H-1518 Budapest Hungary Univ Paris 11 CNRS LRI F-91405 Orsay France Natl Univ Singapore Ctr Quantum Technol Singapore 117543 Singapore Univ Paris 11 LRI F-91405 Orsay France ENST F-75013 Paris France

We present several results on the complexity of various forms of Sperner's Lemma in the black-box model of computing. We give a deterministic algorithm for Sperner problems over pseudo-manifolds of arbitrary dimension. The query complexity of our algorithm is linear in the separation number of the skeleton graph of the manifold and the size of its boundary. As a corollary we get an O(root n) deterministic query algorithm for the black-box version of the problem 2D-SPERNER, a well studied member of Papadimitriou's complexity class PPAD. This upper bound matches the Omega(root n) deterministic lower bound of Crescenzi and Silvestri. The tightness of this bound was not known before. In another result we prove for the same problem an Omega((4)root n) lower bound for its probabilistic, and an Omega((8)root n) lower bound for its quantum query complexity, showing that all these measures are polynomially related.

关键词： Query complexity Sperner's lemma deterministic algorithm Probabilistic and quantum lower bound

来源：评论

学校读者我要写书评

暂无评论

algorithm for calculating the roots of polynomials with coefficients in the ring of polynomials over an arbitrary integral domain

引用

MATHEMATICAL NOTES 2009年第1-2期85卷 68-81页

作者： Maevskii, A. E. So Fed Univ Rostov Na Donu Russia

A deterministic algorithm for calculating the roots of polynomials in one variable with coefficients in the ring of polynomials in several variables over an arbitrary integral domain is constructed. An estimate for th... 详细信息

关键词： root of a polynomial deterministic algorithm integral domain polynomial ring arithmetic complexity algebraic-geometric code principal prime ideal

来源：评论

学校读者我要写书评

暂无评论

BIBD's for (13, 5, 5), (16, 6, 5) and (21, 6, 4) Possessing Possibly an Automorphism of Order 3

引用

World Academy of Science, Engineering and Technology 2009年 58卷 902-905页

作者： Martinjak, Ivica Pavčević, Mario-Osvin University of Zagreb Faculty of Electrical Engineering and Computing Department of Applied Mathematics Unska 3 HR - 10000 Zagreb Croatia

When trying to enumerate all BIBD's for given parameters, their natural solution space appears to be huge and grows extremely with the number of points of the design. Therefore, constructive enumerations are often carried out by assuming additional constraints on design's structure, automorphisms being mostly used ones. It remains a hard task to construct designs with trivial automorphism group - those with no additional symmetry - although it is believed that most of the BIBD's belong to that case. In this paper, very many new designs with parameters 2-(13, 5, 5), 2- (16, 6, 5) and 2-(21, 6, 4) are constructed, assuming an action of an automorphism of order 3. Even more, it was possible to construct millions of such designs with no non-trivial automorphisms.

关键词： Automorphism group BIBD deterministic algorithm Incidence matrix Tactical decomposition

来源：评论

学校读者我要写书评

暂无评论

Fractal fitting research on stock prices

Fractal fitting research on stock prices

引用

1st International Congress on Image and Signal Processing

作者： Lin, Yong Tong, Xin Renmin Univ China Informat Sch Dept Math Beijing 100872 Peoples R China

ISBN: (纸本)9780769531199

In this paper, we mainly study the law of stock price changes and the fitting method of it. After introducing the key point of fractal and Genetic algorithm, we focus on explaining the inverse problems of piecewise fractal interpolation theoretically first. Then, based on the theory, we analyze a large amount of stock price data, calculate all the values of parameters in the model, and finally get an image of the attractor. The result is comparatively satisfying, so that this algorithm is very effective.

关键词： piecewise fractal interpolation function deterministic algorithm Genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

Optimal deterministic broadcasting in known topology radio networks

引用

DISTRIBUTED COMPUTING 2007年第3期19卷 185-195页

作者： Kowalski, Dariusz R. Pelc, Andrzej Univ Liverpool Dept Comp Sci Liverpool L69 7ZF Merseyside England Univ Quebec Dept Informat Gatineau PQ J8X 3X7 Canada

We consider deterministic broadcasting in radio networks whose nodes have full topological information about the network. The aim is to design a polynomial algorithm, which, given a graph G with source s, produces a fast broadcast scheme in the radio network represented by G. The problem of finding a fastest broadcast scheme for a given graph is NP-hard, hence it is only possible to get an approximation algorithm. We give a deterministic polynomial algorithm which produces a broadcast scheme of length O(D + log(2) n), for every n-node graph of diameter D, thus improving a result of Gasieniec et al. (PODC 2005) [ 17] and solving a problem stated there. Unless the inclusion NP subset of BPTIME(n(O(log log n))) holds, the length O(D + log(2) n) of a polynomially constructible deterministic broadcast scheme is optimal.

关键词： broadcast deterministic algorithm radio network graph

来源：评论

学校读者我要写书评

暂无评论

Coupling stochastic and deterministic local search in examination timetabling

引用

OPERATIONS RESEARCH 2007年第2期55卷 351-366页

作者： Caramia, Massimiliano Dell'Olmo, Paolo Univ Roma Tor Vergata Dipartimento Ingn Impresa I-00173 Rome Italy Univ Roma 1 Dipartimento Stat Probalitia & Stat Applicate I-00185 Rome Italy

In this paper, we propose a novel optimization algorithm for examination timetabling. It works by alternating two phases;one based on a stochastic local search and the other on a deterministic local search. The stochastic phase is fundamentally based on biased random sampling that iteratively constructs schedules according to a matrix whose entries are the probability with which exams can be assigned to time slots. The deterministic phase, instead, consists of assigning (according to a given ordering) each exam sequentially to the time slot that causes the lowest increase in the. schedule penalty. After a schedule is constructed, swap operations are executed to improve performance. These two phases are coupled and made closely interactive by tunnelling information on what has happened during one phase to the successive ones. Moreover, the length of a phase and the parameter framework to be used in a new phase are automatically determined by a record of the process. We tested the proposed technique on known benchmarks, and a comparison with 17 algorithms drawn from the state of the art appears to show that our algorithm is able to improve best-known results. In particular, in reference to uncapacitated problems, i.e., the ones without room constraints, our algorithm bested the state of the art in 70% to 90% of the tested instances, while in capacitated problems with overnight conflicts (second-order conflicts), it was superior to all the other algorithms.

关键词： scheduling heuristic deterministic algorithm stochastic algorithm biasedrandom sampling examination timetabling local search

来源：评论

学校读者我要写书评

暂无评论

deterministic M2M multicast in radio networks

引用

THEORETICAL COMPUTER SCIENCE 2006年第1-3期362卷 196-206页

作者： Gasieniec, Leszek Kranakis, Evangelos Pelc, Andrzej Xin, Qin Univ Liverpool Dept Comp Sci Liverpool L69 7ZF Merseyside England Carleton Univ Sch Comp Sci Ottawa ON K1S 5B6 Canada Univ Quebec Dept Informat Gatineau PQ J8X 3X7 Canada Univ Bergen Dept Informat N-5020 Bergen Norway

We study the problem of exchanging messages within a fixed group of k nodes, called participants, in an n-node radio network, modeled as an undirected graph. This communication task was previously considered in the setting of ATM video applications, in [J.M. Tsai, H.-H. Fang, C.-Y. Lee, A multicast solution for ATM video applications, IEEE Trans. Circuits Systems Video Technol. 7 (1997) 675-686], and was called multipoint-to-multipoint (M2M) multicasting. While the radio network topology is known to all nodes, it is assumed that no node is aware of the location of the participants. We give a distributed deterministic algorithm for the M2M multicasting problem in radio networks, and analyze its time complexity. We show that if the maximum distance between any two out of k participants is d then this local information exchange problem can be solved in time O(d log(2) n + k log(4) n). (C) 2006 Elsevier B.V. All rights reserved.

关键词： radio communication deterministic algorithm broadcasting multicasting

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：