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

Fully dynamic algorithm for chordal graphs with O(1) query-time and O(n²) update-time

THEORETICAL COMPUTER SCIENCE 2012年 445卷 82-92页

作者： Mezzini, Mauro Univ Roma La Sapienza Dept Comp Sci Rome Italy

We propose dynamic algorithms and data structures for chordal graphs supporting the following operation: determine if an edge can be added or removed from the graph while preserving the chordality in O(1) time. We show that the complexity of the algorithms for updating the data structures when an edge is actually inserted or deleted is O(n(2)) where n is the number of vertices of the graph. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Chordal graphs dynamic algorithms Minimal Triangulations

来源：评论

学校读者我要写书评

暂无评论

On the Domination Number of Cartesian Product of Two Directed Cycles

引用

JOURNAL OF APPLIED MATHEMATICS 2013年第unknown期2013卷 619695-1-619695-7页

作者： Shao, Zehui Zhu, Enqiang Lang, Fangnian Chengdu Univ Sch Informat Sci & Technol Chengdu 610106 Peoples R China Inst Higher Educ Sichuan Prov Key Lab Pattern Recognit & Intelligent Informat Chengdu 610106 Peoples R China Peking Univ Sch Elect Engn & Comp Sci Beijing 100871 Peoples R China

Denote by gamma(G) the domination number of a digraph G and C-m square C-n the Cartesian product of C-m and C-n, the directed cycles of length m, n >= 2. In 2010, Liu et al. determined the exact values of gamma(C-m square C-n) for m = 2, 3, 4, 5, 6. In 2013, Mollard determined the exact values of gamma(C-m square C-n) for m = 3k + 2. In this paper, we give lower and upper bounds of gamma(C-m square C-n) with m = 3k + 1 for different cases. In particular, inverted right perpendicular(2k + 1)n/2inverted left perpendicular <= gamma(C3k+1 square C-n) <= left perpendicular(2k + 1)n/2right perpendicular + k Based on the established result, the exact values of gamma(C-m square C-n) are determined for m = 7 and 10 by the combination of the dynamic algorithm, and an upper bound for gamma(C-13 square C-n) is provided.

关键词： On the Domination Number of Cartesian Product Two Directed Cycles Mentoring Upper bound Authoritarianism dynamic algorithms Cartesian product Exact

来源：评论

学校读者我要写书评

暂无评论

Improved Deterministic algorithms for Decremental Reachability and Strongly Connected Components

引用

ACM TRANSACTIONS ON algorithms 2013年第3期9卷 27-27页

作者： Lacki, Jakub Univ Warsaw Inst Informat PL-02097 Warsaw Poland

This article presents a new deterministic algorithm for decremental maintenance of the transitive closure in a directed graph. The algorithm processes any sequence of edge deletions in O(mn) time and answers queries in constant time. Previously, such time bound has only been achieved by a randomized Las Vegas algorithm. In addition to that, a few decremental algorithms for maintaining strongly connected components are shown, whose time complexity is O(n(1.5)) for planar graphs, O(n log n) for graphs with bounded treewidth and O(mn) for general digraphs.

关键词： algorithms dynamic algorithms decremental algorithms graph algorithms graphs strongly connected components transitive closure

来源：评论

学校读者我要写书评

暂无评论

dynamic Boolean Matrix Factorizations

Dynamic Boolean Matrix Factorizations

引用

12th IEEE International Conference on Data Mining (ICDM)

作者： Miettinen, Pauli Max Planck Inst Informat D-66123 Saarbrucken Germany

ISBN: (纸本)9781467346498;9780769549057

Boolean matrix factorization is a method to decompose a binary matrix into two binary factor matrices. Akin to other matrix factorizations, the factor matrices can be used for various data analysis tasks. Many (if not most) real-world data sets are dynamic, though, meaning that new information is recorded over time. Incorporating this new information into the factorization can require a re-computation of the factorization - something we cannot do if we want to keep our factorization up-to-date after each update. This paper proposes a method to dynamically update the Boolean matrix factorization when new data is added to the data base. This method is extended with a mechanism to improve the factorization with a trade-off in speed of computation. The method is tested with a number of real-world and synthetic data sets including studying its efficiency against off-line methods. The results show that with good initialization the proposed online and dynamic methods can beat the state-of-the-art offline Boolean matrix factorization algorithms.

关键词： Boolean matrix factorization On-line algorithms dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

On-line and dynamic Estimation of Rician Fading Channels in GSM-R Networks

On-line and Dynamic Estimation of Rician Fading Channels in ...

引用

4th International Conference on Wireless Communications and Signal Processing (WCSP)

作者： Ma, Yongsen Du, Pengyuan Mao, Xiaofeng Long, Chengnian Shanghai Jiao Tong Univ Minist Educ Dept Automat Key Lab Syst Control & Informat Proc Shanghai 200030 Peoples R China Shanghai Jiao Tong Univ Dept Elect Engn Shanghai Peoples R China

ISBN: (纸本)9781467358293;9781467358309

The on-line and dynamic estimation algorithm for Rician fading channels in GSM-R networks is proposed, which is an expansion of local mean power estimation of Rayleigh fading channels. The proper length of statistical interval and required number of averaging samples are determined which are adaptive to different propagation environments. It takes advantage of the sampling signals and Rician fading parameters of last estimation to reduce measurement overhead. The performance of this method was evaluated by measurement experiment along the Beijing-Shanghai high-speed railway. When it is NLOS propagation, the required sampling intervals can be increased from 1.1 lambda in Lee's method to 3.7 lambda of the on-line and dynamic algorithm. And the sampling interval can be set up to 12 lambda although the length of statistical interval decreases when there is LOS signal, which can reduce the measurement overhead significantly. The algorithm can be applied in coverage assessment with lower measurement overhead, and in dynamic and adaptive allocation of wireless resource.

关键词： Rician fading channels IN-LINE dynamic algorithms sampling interval Self tuning

来源：评论

学校读者我要写书评

暂无评论

Multi-stage recovery robustness for optimization problems: A new concept for planning under disturbances

引用

INFORMATION SCIENCES 2012年 190卷 107-126页

作者： Cicerone, Serafino Di Stefano, Gabriele Schachtebeck, Michael Schoebel, Anita Univ Aquila Dept Elect & Informat Engn I-67100 Laquila Italy Univ Gottingen Inst Numer & Appl Math D-3400 Gottingen Germany

In practical optimization problems, disturbances to a given instance are unavoidable due to unpredictable events which can occur when the system is running. In order to face these situations, many approaches have been proposed during the last years in the area of robust optimization. The basic idea of robustness is to provide a solution which can be used even if the input instance is disturbed, at the cost of optimality. However, the notion of robustness in every day life is much broader than that pursued in the area of robust optimization so far. In practice it is reasonable to consider a solution as robust, if a recovery strategy is available that can be applied when disturbing events occur in order to adapt the solution to the new situation. This suggests to study robustness and recoverability in a unified framework. Recently, a first tentative of unifying the notions of robustness and recoverability into a new integrated notion of recoverable robustness has been done in the context of railway optimization, see [28]. Although this model represents a significant improvement, it has the following drawback: typically there is not only one disruption, but many of them might appear one after another. In this case, the solutions provided within the recoverable robustness are not satisfying. In this paper we extend the concept of recoverable robustness to deal not only with one single recovery step, but with many recovery steps. To this aim, we introduce the new notion of multi-stage recoverable robustness. We apply the new model in the context of timetabling and delay management problems. (C) 2011 Elsevier Inc. All rights reserved.

关键词： Robustness Optimization problems dynamic algorithms Timetabling Delay management Recovery

来源：评论

学校读者我要写书评

暂无评论

Profit-Maximizing Virtual Machine Trading in a Federation of Selfish Clouds

Profit-Maximizing Virtual Machine Trading in a Federation of...

引用

IEEE INFOCOM Conference

作者： Hongxing Li Chuan Wu Zongpeng Li Francis C. M. Lau Department of Computer Science The University of Hong Kong Hong Kong Department of Computer Science University of Calgary Canada

ISBN: (纸本)9781467359443

The emerging federated cloud paradigm advocates sharing of resources among cloud providers, to exploit temporal availability of resources and diversity of operational costs for job serving. While extensive studies exist on enabling interoperability across different cloud platforms, a fundamental question on cloud economics remains unanswered: When and how should a cloud trade VMs with others, such that its net profit is maximized over the long run? In order to answer this question by the federation, a number of important, correlated decisions, including job scheduling, server provisioning and resource pricing, need to be dynamically made, with long-term profit optimality being a goal. In this work, we design efficient algorithms for inter-cloud resource trading and scheduling in a federation of geo-distributed clouds. For VM trading among clouds, we apply a double auction-based mechanism that is strategyproof, individual rational, and ex-post budget balanced. Coupling with the auction mechanism is an efficient, dynamic resource trading and scheduling algorithm, which carefully decides the true valuations of VMs in the auction, optimally schedules stochastic job arrivals with different SLAs onto the VMs, and judiciously turns on and off servers based on the current electricity prices. Through rigorous analysis, we show that each individual cloud, by carrying out our dynamic algorithm, can achieve a time-averaged profit arbitrarily close to the offline optimum.

关键词： federations virtual machines Servers dynamic algorithms Electricity pricing Manufacturing costs jobs long run

来源：评论

学校读者我要写书评

暂无评论

dynamic Construction of Order-k Voronoi Diagram

Dynamic Construction of Order-k Voronoi Diagram

引用

International Conference on Computer Science and Network Technology

作者： Li Ma Guo-Bin Su Department of Information and Engineering Shijiazhuang University of Economics Hebei province talents exchange service center

ISBN: (纸本)9781467329637

The order-k Voronoi diagrams are difficult to construct because of their complicated structures. In traditional algorithm, production process was extremely complex. While dynamic algorithm is only concerned with positions of generators, so it is effective for constructing Voronoi diagrams with complicated shapes of Voronoi polygons. It can be applied to order-k Voronoi diagram with any generators, and can get over most shortcomings of traditional algorithm. So it is more useful and effective. Model is constructed with dynamic algorithm. And the application example shows that the algorithm is both simple and useful, and it is of high potential value in practice.

关键词： Voronoi diagram dynamic Order-k Voronoi diagrams dynamic algorithms dynamos dynamic high potential

来源：评论

学校读者我要写书评

暂无评论

On-line and dynamic estimation of Rician fading channels in GSM-R networks

On-line and dynamic estimation of Rician fading channels in ...

引用

International Conference on Wireless Communications and Signal Processing (WCSP)

作者： Yongsen Ma Pengyuan Du Xiaofeng Mao Chengnian Long Department of Automation Key Laboratory of System Control and Information Processing Ministry of Education Shanghai Jiaotong University China Department of Electronic Engineering Shanghai Jiaotong University China

ISBN: (纸本)9781467358309

The on-line and dynamic estimation algorithm for Rician fading channels in GSM-R networks is proposed, which is an expansion of local mean power estimation of Rayleigh fading channels. The proper length of statistical interval and required number of averaging samples are determined which are adaptive to different propagation environments. It takes advantage of the sampling signals and Rician fading parameters of last estimation to reduce measurement overhead. The performance of this method was evaluated by measurement experiment along the Beijing-Shanghai high-speed railway. When it is NLOS propagation, the required sampling intervals can be increased from 1.1λ in Lee's method to 3.7λ of the on-line and dynamic algorithm. And the sampling interval can be set up to 12λ although the length of statistical interval decreases when there is LOS signal, which can reduce the measurement overhead significantly. The algorithm can be applied in coverage assessment with lower measurement overhead, and in dynamic and adaptive allocation of wireless resource.

关键词： dynamic Estimation Rician Rician fading channels Rician fading IN-LINE dynamic dynamic algorithms sampling interval Self tuning

来源：评论

学校读者我要写书评

暂无评论

Improved dynamic reachability algorithms for directed graphs

引用

SIAM JOURNAL ON COMPUTING 2008年第5期37卷 1455-1471页

作者： Roditty, Liam Zwick, Uri Tel Aviv Univ Sch Comp Sci IL-69978 Tel Aviv Israel

We obtain several new dynamic algorithms for maintaining the transitive closure of a directed graph and several other algorithms for answering reachability queries without explicitly maintaining a transitive closure matrix. Among our algorithms are: (i) A decremental algorithm for maintaining the transitive closure of a directed graph, through an arbitrary sequence of edge deletions, in O(mn) total expected time, essentially the time needed for computing the transitive closure of the initial graph. Such a result was previously known only for acyclic graphs. (ii) Two fully dynamic algorithms for answering reachability queries. The first is deterministic and has an amortized insert/delete time of O(m root n), and worst-case query time of O(root n). The second is randomized and has an amortized insert/delete time of O(m(0.5)8n) and worst-case query time of O(m(0.43)). This significantly improves the query times of algorithms with similar update times. (iii) A fully dynamic algorithm for maintaining the transitive closure of an acyclic graph. The algorithm is deterministic and has a worst-case insert time of O(m), constant amortized delete time of O(1), and a worst-case query time of O(n/log n). Our algorithms are obtained by combining several new ideas, one of which is a simple sampling idea used for detecting decompositions of strongly connected components, with techniques of Even and Shiloach [J. ACM, 28 (1981), pp. 1-4], Italiano [Inform. Process. Lett., 28 (1988), pp. 5-11], Henzinger and King [Proceedings of the 36th Annual Symposium on Foundations of Computer Science, Milwaukee, WI, 1995, pp. 664-672], and Frigioni et al. [ACM J. Exp. Algorithmics, 6 (2001), (electronic)].

关键词： dynamic algorithms transitive closure strongly connected components

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：