This paper provides the first decremental algorithm for fair Buchi games. It efficiently recalculates the winning region under the deletion of live edges in the underlying game graph. Our algorithm addresses the uniqu...
详细信息
ISBN:
(纸本)9783031787089;9783031787096
This paper provides the first decremental algorithm for fair Buchi games. It efficiently recalculates the winning region under the deletion of live edges in the underlying game graph. Our algorithm addresses the unique challenges posed by fair Buchi games such as exponential-memory strategies and the non-monotonicity of the winning region under edge deletion. This prevents a straight forward extension of dynamic algorithms from (normal) Buchi games, in particular Jurdzinski's small progress measures, on which these algorithms rely. The main contribution of this paper is the definition of a specialized (one-digit) progress measure for fair Buchi games and its correctness proof. We further derive a decremental algorithm for fair Buchi games using a fixed-point calculation entailed by this progress measure. We show that the (non-optimized) prototype implementation of our decremental algorithm outperforms an (optimized) fair Buchi game solver on a large class of benchmarks. By this, our work not only expands the scope of dynamic algorithms but also underscores the benefit of tailored solutions for specific game structures such as fair Buchi games.
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 i...
详细信息
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.
In many modern applications, the generated data is a dynamic networks. The networks are graphs that change over time by a sequence of update operations (node addition, node deletion, edge addition, edge deletion, and ...
详细信息
In many modern applications, the generated data is a dynamic networks. The networks are graphs that change over time by a sequence of update operations (node addition, node deletion, edge addition, edge deletion, and edge weight change). In these networks, it is inefficient to compute from scratch the solution of a data mining/machine learning task, after any update operation. Therefore in recent years, several so-called dynamical algorithms have been proposed that update the solution, instead of computing it from scratch. In this paper, first we formulate this emerging setting and discuss its high-level algorithmic aspects. Then, we review state of the art dynamical algorithms proposed for several data mining and machine learning tasks, including frequent pattern discovery, betweenness/closeness/PageRank centralities, clustering, classification, and regression. This article is categorized under: Technologies > Structure Discovery and Clustering Technologies > Machine Learning Fundamental Concepts of Data and Knowledge > Big Data Mining
In this paper we propose dynamic algorithms for maintaining a breadth-first search tree from a given source vertex of a directed graph G in either an incremental or a decremental setting. During a sequence of q edge i...
详细信息
In this paper we propose dynamic algorithms for maintaining a breadth-first search tree from a given source vertex of a directed graph G in either an incremental or a decremental setting. During a sequence of q edge insertions or a sequence of q edge deletions the total time required is O(m(.)min{q, n}), where n is the number of vertices of G, and m is the final number of edges of G in the case of insertions or the initial number of edges of G in the case of deletions. This gives O(n) amortized time for each operation if the sequence has length Omega (m). Our algorithms require O(n + m) space. These are the first results in the literature concerning the dynamic maintenance of a breadth-first search tree for directed graphs, As a straightforward application of such algorithms we can maintain a shortest path tree for a directed graph in the case of unit edge weights within the same time bounds. In this case distance queries can be answered in constant time, while shortest path queries can be answered in time linear in the length of the retrieved path, (C) 2001 Elsevier Science B.V. All rights reserved.
暂无评论