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

Control of Multi-Hop Communication Networks for Inter-Session Network Coding

IEEE TRANSACTIONS ON INFORMATION THEORY 2011年第2期57卷 1092-1110页

作者： Eryilmaz, Atilla Lun, Desmond S. Swapna, B. T. Ohio State Univ Dept Elect & Comp Engn Columbus OH 43210 USA Rutgers State Univ Dept Comp Sci Camden NJ 08102 USA Rutgers State Univ Ctr Comp & Integrat Biol Camden NJ 08102 USA

This paper provides a solution to the question of how, when and where to perform inter-session network coding for a general network model both under wired and wireless conditions. In particular, an original queuing architecture and a dynamic routing-scheduling-coding strategy are introduced for serving multiple sessions when linear network coding is allowed across sessions. This policy provides a novel extension to the class of back-pressure policies by incorporating inter-session coding decisions via simple rules on the relevant queue-length levels. Despite the fact that the capacity region of inter-session coding is a challenging open problem, in this paper, we prove that our algorithm can support any set of rates in a nontrivial characterized region of achievable rates. In addition to its practical implications, this work also provides a theoretical framework in which the gains of inter-session network coding and pure routing can be compared.

关键词： Backpressure policies butterfly network dynamic algorithms inter-session network coding Lyapunov stability stochastic networks

来源：评论

学校读者我要写书评

暂无评论

The general structure of edge-connectivity of a vertex subset in a graph and its incremental maintenance. Odd case

引用

SIAM JOURNAL ON COMPUTING 2000年第3期30卷 753-808页

作者： Dinitz, Y Vainshtein, A Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel Univ Haifa Dept Math IL-31905 Haifa Israel Univ Haifa Dept Comp Sci IL-31905 Haifa Israel

Let G = (V, E) be an undirected graph, S be a subset of its vertices, C-S be the set of minimum edge-cuts partitioning S, and S be the cardinality of such a cut. We suggest a graph structure, called the connectivity carcass of S, that represents both cuts in CS and the partition of V by all these cuts;its size is O(min{\E\, lambda(S)\V\}). In this paper we present general constructions and study in detail the case lambda(S) odd;the specifics of the case S even are considered elsewhere. For an adequate description of the connectivity carcass we introduce a new type of graph: locally orientable graphs, which generalize digraphs. The connectivity carcass consists of a locally orientable quotient graph of G, a cactus tree (in case S odd, just a tree) representing all distinct partitions of S by cuts in C-S, and a mapping connecting them. One can build it in O (\S\) max-flow computations in G. For an arbitrary sequence of u edge insertions not changing lambda(S), the connectivity carcass can be maintained in time O (\V\ min {\E\, lambda(S) \V\} + u). For two vertices of G, queries asking whether they are separated by a cut in C-S are answered in O(1) worst-case time per query. Another possibility is to maintain the carcass in O (\S\ min {\E\, lambda(S) \V\} + u) time, but to answer the queries in O(1) time only if at least one of the vertices belongs to S.

关键词： edge-connectivity minimum cuts graph structures incremental maintenance dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

Online Topological Ordering

引用

ACM TRANSACTIONS ON algorithms 2006年第3期2卷 364-379页

作者： Katriel, Irit Bodlaender, Hans L. Univ Aarhus BRICS Aarhus Denmark Univ Utrecht Inst Informat & Comp Sci Utrecht Netherlands

It is shown that the problem of maintaining the topological order of the nodes of a directed acyclic graph while inserting m edges can be solved in O (min{m(3/2) log n, m(3/2) + n(2) log n}) time, an improvement over the best known result of O(mn). In addition, we analyze the complexity of the same algorithm with respect to the treewidth k of the underlying undirected graph. We show that the algorithm runs in time O (mk log(2) n) for general k and that it can be implemented to run in O (n log n) time on trees, which is optimal. The algorithm also detects cycles in the input.

关键词： dynamic algorithms graphs online algorithms topological order treewidth

来源：评论

学校读者我要写书评

暂无评论

Fault Tolerant Depth First Search in Undirected Graphs: Simple Yet Efficient

引用

ALGORITHMICA 2022年第7期84卷 2028-2049页

作者： Baswana, Surender Gupta, Shiv Tulsyan, Ayush IIT Kanpur Dept CSE Kanpur 208016 Uttar Pradesh India

Let G be an undirected graph. We address the problem of fault tolerant depth first search (DFS) tree defined as follows. Build a compact data structure that, given any set F of failed vertices or edges, can efficiently report a DFS tree of G\F. We present an algorithm which is drastically simpler and yet more efficient than the current state-of-the-art algorithms for this problem. Additionally, for achieving efficiency, the current state -of-the -algorithms have to crucially rely on sophisticated data structures. The simplicity of our algorithm also enables us to replace these sophisticated data structures with much simpler and lighter data stnictures that occupy optimal space and take optimal preprocessing time. Our algorithm for the fault tolerant DFS tree also leads to a better time complexity for maintaining a DFS tree in a fully dynamic environment.

关键词： DFS tree Fault-tolerant dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

An Experimental Analysis of Self-Adjusting Computation

引用

ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS 2009年第1期32卷 3-3:53页

作者： Acar, Umut A. Blelloch, Guy E. Blume, Matthias Harper, Robert Tangwongsan, Kanat Toyota Technol Inst Chicago IL USA Carnegie Mellon Univ Pittsburgh PA 15213 USA

Recent work on adaptive functional programming (AFP) developed techniques for writing programs that can respond to modifications to their data by performing change propagation. To achieve this, executions of programs are represented with dynamic dependence graphs (DDGs) that record data dependences and control dependences in away that a change-propagation algorithm can update the computation as if the program were from scratch, by re-executing only the parts of the computation affected by the changes. Since change-propagation only re-executes parts of the computation, it can respond to certain incremental modifications asymptotically faster than recomputing from scratch, potentially offering significant speedups. Such asymptotic speedups, however, are rare: for many computations and modifications, change propagation is no faster than recomputing from scratch. In this article, we realize a duality between dynamic dependence graphs and memoization, and combine them to give a change-propagation algorithm that can dramatically increase computation reuse. The key idea is to use DDGs to identify and re-execute the parts of the computation that are affected by modifications, while using memoization to identify the parts of the computation that remain unaffected by the changes. We refer to this approach as self-adjusting computation. Since DDGs are imperative, but (traditional) memoization requires purely functional computation, reusing computation correctly via memoization becomes a challenge. We overcome this challenge with a technique for remembering and reusing not just the results of function calls (as in conventional memoization), but their executions represented with DDGs. We show that the proposed approach is realistic by describing a library for self-adjusting computation, presenting efficient algorithms for realizing the library, and describing and evaluating an implementation. Our experimental evaluation with a variety of applications, ranging from simple list pr

关键词： Languages Performance algorithms Computational geometry dynamic algorithms dynamic dependence graphs memoization performance self-adjusting computation

来源：评论

学校读者我要写书评

暂无评论

New Partitioning Techniques and Faster algorithms for Approximate Interval Scheduling

引用

ALGORITHMICA 2024年第9期86卷 2997-3026页

作者： Compton, Spencer Mitrovic, Slobodan Rubinfeld, Ronitt Stanford Univ Comp Sci Dept 353 Jane Stanford Way Stanford CA 94305 USA Univ Calif Davis Comp Sci Dept Kemper Hall Davis CA 95616 USA MIT CSAIL 32 Vassar St Cambridge MA 02139 USA

Interval scheduling is a basic algorithmic problem and a classical task in combinatorial optimization. We develop techniques for partitioning and grouping jobs based on their starting/ending times, enabling us to view an instance of interval scheduling on many jobs as a union of multiple interval scheduling instances, each containing only a few jobs. Instantiating these techniques in a dynamic setting produces several new results. For (1+epsilon)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(1+\varepsilon )$$\end{document}-approximation of job scheduling of n jobs on a single machine, we develop a fully dynamic algorithm with O(logn epsilon)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\nicefrac {\log {n}}{\varepsilon })$$\end{document} update and O(logn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\log {n})$$\end{document} query worst-case time. Our techniques are also applicable in a setting where jobs have weights. We design a fully dynamic deterministic algorithm whose worst-case update and query times are poly(logn,1 epsilon)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\text {poly} (\log n,\frac{1}{\varepsilon })$$\end{document}. This is the first algorithm that maintains a (1+epsilon)\documentclass[12pt]{minimal} \usepackage{amsmath

关键词： Interval scheduling Job scheduling dynamic algorithms Local computation algorithms

来源：评论

学校读者我要写书评

暂无评论

dynamically maintaining split graphs

引用

DISCRETE APPLIED MATHEMATICS 2009年第9期157卷 2057-2069页

作者： Heggernes, Pinar Mancini, Federico Univ Bergen Dept Informat N-5020 Bergen Norway

We present an algorithm that supports operations for modifying a split graph by adding edges or vertices and deleting edges, such that after each modification the graph is repaired to become a split graph in a minimal way. In particular, if the graph is not split after the modification, the algorithm computes a minimal, or if desired even a minimum, split completion or deletion of the modified graph. The motivation for such operations is similar to the motivation for fully dynamic algorithms for particular graph classes. In our case we allow all modifications to the graph and repair, rather than allowing only the modifications that keep the graph split. Fully dynamic algorithms of the latter kind are known for split graphs [L Ibarra, Fully dynamic algorithms for chordal graphs and split graphs, Technical Report DCS-262-IR, University of Victoria, Canada, 2000]. Our results can be used to design linear time algorithms for some recognition and completion problems, where the input is supplied in an on-line fashion. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Split graphs dynamic algorithms On-line algorithms Minimal split completions

来源：评论

学校读者我要写书评

暂无评论

Doppler frequency estimation-based handover algorithm for long-term evolution networks

引用

IET NETWORKS 2014年第2期3卷 88-96页

作者： Altrad, Omar Muhaidat, Sami Yoo, Paul D. Simon Fraser Univ Burnaby BC Canada Khalifa Univ Abu Dhabi U Arab Emirates Univ Surrey CCSR Guildford Surrey England

Mobile cellular radio systems have become complex multi-layered systems with a mixed architecture of macro and micro cells;therefore, a dynamic method of triggering the handover algorithm in such systems is invaluable and required. In this paper the authors develop a simple handover mechanism to adapt for a fast moving mobile station requesting a handover, in which the authors utilise a Doppler frequency estimation in the downlink for adjustment and apply it to a long-term evolution (LTE) network. This method is beneficial for high speed mobiles in macro and/or micro cells, in which for the latter the cell radius is small and needs a dynamic algorithm to respond in a timely manner. The main objective of this study is to investigate the performance of the proposed algorithm;hence, a system layout is specifically designed for this study. Other factors, such as interference, which may affect the performance of the suggested system are not addressed here. The main concern is to study and compare the proposed algorithm to the standard handover algorithm currently implemented in LTE. Simulations at the system level show a marked decrease in the average number of handovers requested.

关键词： Frequency estimation Microcells Local thermodynamic equilibrium macro commands algorithms system level Handover dynamic algorithms Doppler frequency Long Term Evolution

来源：评论

学校读者我要写书评

暂无评论

Dog bites postman: Point location in the moving Voronoi diagram and related problems

引用

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS 1998年第3期8卷 321-342页

作者： Devillers, O Golin, MJ INRIA F-06902 Sophia Antipolis France Hong Kong Univ Sci & Technol Kowloon Hong Kong

In this paper, we discuss two variations of the two-dimensional post-office problem that arise when the post-offices are n postmen moving with constant velocities. The first variation addresses the question: given a point q(0) and time t(0) who is the nearest postman to q(0) at time t(0)? We present a randomized incremental data structure that answers the query in expected O(log(2) n) time. The second variation views a query point as a dog searching for a postman to bite and finds the postman that a dog running with speed v(d) could reach first. While it is quite straightforward to design a data structure for the first problem, designing one for the second appears more difficult. We show that if the dog is quicker than all of the postmen then there is a nice correspondence between the problems. This correspondence will permit us to use the data structure developed for the first problem to solve the second one in O(log(2) n) time as well. The proposed structure is semi-dynamic, that is the set of postmen can be modified by inserting new postmen. A fully dynamic structure that also supports deletions can be obtained, but in that case the query time becomes O(log(3) n).

关键词： computational geometry moving points Voronoi Delaunay randomized algorithms dynamic algorithms localisation

来源：评论

学校读者我要写书评

暂无评论

NOVEL algorithms FOR SEARCHING CONFORMATIONAL SPACE

引用

JOURNAL OF COMPUTER-AIDED MOLECULAR DESIGN 1994年第1期8卷 67-82页

作者： BYRNE, D LI, J PLATT, E ROBSON, B WEINER, P PROTEUS MOLEC DESIGN LTD PROTEUS HOUSELYME GREEN BUSINESS PKMACCLESFIELD SK11 0JLCHESHIREENGLAND AMBER SYST INC SOMERVILLEMA 02143

The modelling of biological molecules by molecular dynamics is beset by a range of problems. The most important of these is the multiple-minima problem. The deep metastable minima can cause difficulties in proper equilibration of a molecular system and result in the simulated system being trapped in a long-lived metastable state. One way to overcome these problems is to re-engineer the ''Newtonian Rules' in order to more efficiently search conformational space. Re-engineering of the 'Newtonian Rules' implies a redesign of the physical laws arising from them. This is done in various ways by the RUSH, Hybrid Monte Carlo and PEACS algorithms. This paper explores applications of these algorithms, and compares them to a traditional molecular dynamics method.

关键词： MOLECULAR SIMULATION CONFORMATIONAL SEARCH dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：