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

Top-k Distance Queries on Large Time-Evolving Graphs

IEEE ACCESS 2023年 11卷 102228-102242页

作者： D'Ascenzo, Andrea D'Emidio, Mattia Univ Aquila Dept Informat Engn Comp Sci & Math I-67100 Laquila Italy

Fast extraction of top- k distances from graph data is a primitive of paramount importance in the fields of data mining, network analytics and machine learning, where ranked distances are exploited for several purposes (e.g., link prediction or network classification). While investigation on computational methods to address this retrieval task for regularly sized, static inputs has been extensive, much less is known when managed graphs are massive, i.e., having millions of vertices/edges, and time-evolving, i.e., when their structure can grow over time, a scenario that introduces a number of scalability and effectiveness issues otherwise not arising. Since, nowadays, most real-world applications exploiting top- k distances have to handle inherently dynamic and rapidly growing graphs, in this paper we present the first dynamic indexing scheme that supports very fast queries on top- k distances when graphs are massive and incrementally time-evolving. We assess the scalability and effectiveness of our method through extensive experimentation on both real-world and artificial graph datasets.

关键词： Heuristic algorithms Data structures Scalability Data mining Labeling Computational modeling Time complexity Algorithm design and analysis Algorithm engineering dynamic algorithms k shortest distances massive graph mining

来源：评论

学校读者我要写书评

暂无评论

Maintenance of a piercing set for intervals with applications

引用

ALGORITHMICA 2003年第1期36卷 59-73页

作者： Katz, MJ Nielsen, F Segal, M Ben Gurion Univ Negev Dept Comp Sci IL-84105 Beer Sheva Israel SONY Comp Sci Labs Inc FRL Shinagawa Ku Tokyo 1410022 Japan Ben Gurion Univ Negev Dept Commun Syst Engn IL-84105 Beer Sheva Israel

We show how to maintain efficiently a minimum piercing set for a set S of intervals on the line, under insertions and deletions to/from S. A linear-size dynamic data structure is presented, which enables us to compute a new minimum piercing set following an insertion or deletion in time O(c(S) log \S\), where c(S) is the size of the new minimum piercing set. We also show how to maintain a piercing set for S of size at most (1 + epsilon)c(S), for 0 < epsilon less than or equal to 1, in (O) over bar((log\S\)/epsilon) amortized time per update. We then apply these results to obtain efficient solutions to the following three problems: (i) the shooter location problem, (ii) computing a minimum piercing set for arcs on a circle, and (iii) dynamically maintaining a box cover for a d-dimensional point set.

关键词： geometric optimization piercing set dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：