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

作者： Sukprasert, Pattara Northwestern University

学位级别：Ph.D., Doctor of Philosophy

Due to their widespread applicability, graphs and networks appear in various contexts. The increasing scale of graphs encountered in the real-world requires the development of efficient algorithms that run reasonably fast and produce close to optimal solutions. The main focus of this thesis is the development of fast graph algorithms for optimizing specific structural properties. Many classical problems can be thought of in this framework - for example, the maximum weight matching problem in graphs can be thought of as finding a maximum weight subgraph where each node has degree at most one. While these problems are known to be solvable in polynomial time, many interesting properties could lead to NP-hard optimization problems. We study four problems that fit in the framework. First, we study k-Edge Connected Spanning Subgraph (kECSS). Our goal here is to come up with a network that tolerates link failures. Given an undirected weighted graph, we want to find a minimum weighted spanning subgraph with a property that this subgraph must remain connected even after removing k edges. This problem has applications in route planning where links such as roads or network cables might become unusable. We can think of it as a generalization to the classical minimum spanning tree problem, and this belongs to a family of problems called Survivable Network Design. It has been known for a long time how to get a 2-approximation solution in polynomial time. We show how to find a fractional solution in near-linear time and how to round it to an integral solution efficiently. Second, we study the dynamic Graph Spanner problem. Here, our goal is to develop a data structure, called a spanner, that maintains a subgraph approximating distances between pairs of nodes dynamically. A dynamic graph undergoes structural changes such as edge insertions and deletions. More precisely, our goal is to maintain a t-spanner, which is small subgraph such that the distance between every pair of vertice

关键词： algorithms Approximation algorithms Combinatorial optimization dynamic algorithms Graph theory Parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Point Enclosure Problem for Homothetic Polygons 1

引用

34th International Workshop on Combinatorial algorithms (IWOCA)

作者： Akram, Waseem Saxena, Sanjeev Indian Inst Technol Dept Comp Sci & Engn Kanpur 208016 Uttar Pradesh India

ISBN: (数字)9783031343476

ISBN: (纸本)9783031343469;9783031343476

In this paper, we investigate the following problem: "given a set S of n homothetic polygons, preprocess S to efficiently report all the polygons of S containing a query point." A set of polygons is said to be homothetic if each polygon in the set can be obtained from any other polygon of the set using scaling and translating operations. The problem is the counterpart of the homothetic range search problem discussed by Chazelle and Edelsbrunner (Chazelle, B., and Edelsbrunner, H., Linear space data structures for two types of range search. Discrete & Computational Geometry 2, 2 (1987), 113-126). We show that after preprocessing a set of homothetic polygons with constant number of vertices, the queries can be answered in O(log n+k) optimal time, where k is the output size. The preprocessing takes O(n log n) space and time. We also study the problem in dynamic setting where insertion and deletion operations are also allowed.

关键词： Geometric Intersection algorithms Data Structures dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

dynamic DFS in Undirected Graphs: breaking the O(m) barrier 16

Dynamic DFS in Undirected Graphs: breaking the O(m) barrier

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Surender Baswana Shreejit Ray Chaudhury Keerti Choudhary Shahbaz Khan Dept. of CSE I.I.T. Kanpur

ISBN: (纸本)9781510819672

Given an undirected graphG = (V, E) on n vertices and m edges, we address the problem of maintaining a DFS tree when the graph is undergoing updates (insertion and deletion of vertices or edges). We present the following results for this problem. 1. Fault tolerant DFS tree: There exists a data structure of size O(m) such that given any set F of failed vertices or edges, a DFS tree of the graph GF can be reported in O(n|F|) time. 2. Fully dynamic DFS tree: There exists a fully dynamic algorithm for maintaining a DFS tree that takes worst case O ({the square root of}(mn)) time per update for any arbitrary online sequence of updates. 3. Incremental DFS tree: Given any arbitrary online sequence of edge insertions, we can maintain a DFS tree in O(n) worst case time per edge insertion. These are the first o(m) worst case time results for maintaining a DFS tree in a dynamic environment. Moreover, our fully dynamic algorithm provides, in a seamless manner, the first deterministic algorithm with O(1) query time and o(m) worst case update time for the dynamic subgraph connectivity, biconnectivity, and 2-edge connectivity.

关键词： Depth--first search dynamic algorithms Trees

来源：评论

学校读者我要写书评

暂无评论

Controle de granularidade com threads em programas MPI dinâmicos

Controle de granularidade com threads em programas MPI dinâ...

引用

作者： Lima, João Vicente Ferreira

In the last years, the demand for high performance enables the emergence of more efficient computing platforms and algorithms. The increase of distributed computing platforms rises new challenges for parallel algorithm development like communication, heterogeneity, and resource management. These factors can result in applications whose work load is unknown until runtime. An irregular behavior from algorithm or data can also affect the work load. A parallel application can solve these questions through a programming technique which predicts the work load of a task and offers resource on demand. The granularity, which is the ratio of computation to communication, considers more practical issues, and is an important factor in performance of dynamic algorithms. However, this control is difficult to be designed and the support of a programming tool is needed. Yet, the programming tools have extensive and complicated interfaces which difficult your usage in HPC. This work implements a library (libSpawn) which adds a granularity control on MPI dynamic programs. The library controls the granularity by mapping tasks between processes or threads with three parameters: cores of architecture, load and resources of the operating system. The results obtained between processes and libSpawn show significant gains on synthetic benchmarks from other programming tools. ...

关键词： Processamento paralelo Parallel computing High performance computing Mpi dynamic algorithms Granularity Dissertação

来源：评论

学校读者我要写书评

暂无评论

A note on improved results for one round distributed clique listing

引用

INFORMATION PROCESSING LETTERS 2023年 181卷

作者： Liu, Quanquan C. Northwestern Univ Comp Sci 2233 Tech DrThird Floor Evanston IL 60208 USA

In this note, we investigate listing cliques of arbitrary sizes in bandwidth-limited, dynamic networks. The problem of detecting and listing triangles and cliques was originally studied in great detail by Bonne and Censor-Hillel (ICALP 2019). We extend this study to dynamic graphs where more than one update may occur as well as resolve an open question posed by Bonne and Censor-Hillel (2019). Our algorithms and results are based on some simple observations about listing triangles under various settings and we show that we can list larger cliques using such facts. Specifically, we show that our techniques can be used to solve an open problem posed in the original paper: we show that detecting and listing cliques (of any size) can be done using O (1)-bandwidth after one round of communication under node insertions and node/edge deletions. We conclude with an extension of our techniques to obtain a small bandwidth 1-round algorithm for listing cliques when more than one node insertion/deletion and/or edge deletion update occurs at any time. (c) 2022 Elsevier B.V. All rights reserved.

关键词： Triangle counting Clique counting Distributed algorithms Graph algorithms dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

An experimental analysis of self-adjusting computation

引用

ACM SIGPLAN NOTICES 2006年第6期41卷 96-107页

作者： Acar, Umut A. Blelloch, Guy E. Blume, Matthias Tangwongsan, Kanat Carnegie Mellon Univ Pittsburgh PA 15213 USA

Dependence graphs and memoization can be used to efficiently update the output of a program as the input changes dynamically. Recent work has studied techniques for combining these approaches to effectively dynamize a wide range of applications. Toward this end various theoretical results were given. In this paper we describe the implementation of a library based on these ideas, and present experimental results on the efficiency of this library on a variety of applications. The results of the experiments indicate that the approach is effective in practice, often requiring orders of magnitude less time than recomputing the output from scratch. We believe this is the first experimental evidence that incremental computation of any type is effective in practice for a reasonably broad set of applications.

关键词： languages performance algorithms self-adjusting computation memoization dynamic dependence graphs dynamic algorithms computational geometry performance

来源：评论

学校读者我要写书评

暂无评论

A Faster Algorithm for Computing the Girth of Planar and Bounded Genus Graphs

引用

ACM TRANSACTIONS ON algorithms 2010年第1期7卷 3-3页

作者： Djidjev, Hristo N. Los Alamos Natl Lab Los Alamos NM 87545 USA

The girth of a graph G is the length of a shortest cycle of G. In this article we design an O(n(5/4) log n) algorithm for finding the girth of an undirected n-vertex planar graph, the first o(n(2)) algorithm for this problem. We also extend our results for the class of graphs embedded into an orientable surface of small genus. Our approach uses several techniques such as graph partitioning, hammock decomposition, graph covering, and dynamic shortest-path computation. We discuss extensions and generalizations of our result.

关键词： Girth graphs graph algorithms planar graphs cycles graph separators graph genus shortest paths dynamic algorithms hammock decomposition path and circuit problems

来源：评论

学校读者我要写书评

暂无评论

An O(n^2.75) Algorithm for Incremental Topological Ordering

引用

ACM TRANSACTIONS ON algorithms 2008年第4期4卷 1–14页

作者： Ajwani, Deepak Friedrich, Tobias Meyer, Ulrich Max Planck Inst Informat D-66123 Saarbrucken Germany Goethe Univ Frankfurt Inst Comp Sci D-60325 Frankfurt Germany

We present a simple algorithm which maintains the topological order of a directed acyclic graph (DAG) with n nodes, under an online edge insertion sequence, in O(n(2.75)) time, independent of the number m of edges inserted. For dense DAGs, this is an improvement over the previous best result of O(min{m(3/2) log n, m (3/2) + n(2) log n}) by Katriel and Bodlaender [2006]. We also provide an empirical comparison of our algorithm with other algorithms for incremental topological sorting.

关键词： dynamic algorithms graphs online algorithms topological order

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Recursive algorithms for phylogenetic tree counting

引用

algorithms FOR MOLECULAR BIOLOGY 2013年第1期8卷 26-26页

作者： Gavryushkina, Alexandra Welch, David Drummond, Alexei J. Univ Auckland Dept Comp Sci Auckland 1 New Zealand Univ Auckland Allan Wilson Ctr Mol Ecol & Evolut Auckland 1 New Zealand

Background: In Bayesian phylogenetic inference we are interested in distributions over a space of trees. The number of trees in a tree space is an important characteristic of the space and is useful for specifying prior distributions. When all samples come from the same time point and no prior information available on divergence times, the tree counting problem is easy. However, when fossil evidence is used in the inference to constrain the tree or data are sampled serially, new tree spaces arise and counting the number of trees is more difficult. Results: We describe an algorithm that is polynomial in the number of sampled individuals for counting of resolutions of a constraint tree assuming that the number of constraints is fixed. We generalise this algorithm to counting resolutions of a fully ranked constraint tree. We describe a quadratic algorithm for counting the number of possible fully ranked trees on n sampled individuals. We introduce a new type of tree, called a fully ranked tree with sampled ancestors, and describe a cubic time algorithm for counting the number of such trees on n sampled individuals. Conclusions: These algorithms should be employed for Bayesian Markov chain Monte Carlo inference when fossil data are included or data are serially sampled.

关键词： Ranked tree Constraint tree Resolution Counting trees dynamic algorithms Bayesian tree prior Phylogenetics

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：