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

10th International Symposium on Computing and Networking (CANDAR)

作者： Raikwar, Hemraj Karmakar, Sushanta Indian Inst Technol Guwahati Dept Comp Sci & Engn Gauhati India

ISBN: (纸本)9781665475327

In this paper, we propose a fully dynamic algorithm for the Steiner tree problem in a planar graph. We consider an undirected weighted planar graph G = (V, E) with positive real edge weights and a sequence of updates comprising of edge insertions and deletions. The goal is to maintain a Steiner tree (on the terminals) which is a good approximation of the minimum Steiner tree of the updated graph. We show that the proposed fully dynamic algorithm maintains a (2+ epsilon) approximate Steiner tree in (O) over tilde (|S|(2) root n + |S| D + n) worst case update time where the symbols have usual meanings. The update time reduces to O(n(c')-2) in a special case.

关键词： Steiner tree fully dynamic algorithm dynamic distance oracle

来源：评论

学校读者我要写书评

暂无评论

A fully dynamic algorithm for the recognition of P₄-sparse graphs

引用

THEORETICAL COMPUTER SCIENCE 2012年 439卷 41-57页

作者： Nikolopoulos, Stavros D. Palios, Leonidas Papadopoulos, Charis Univ Ioannina Dept Math GR-45110 Ioannina Greece Univ Ioannina Dept Comp Sci GR-45110 Ioannina Greece

In this paper, we solve the dynamic recognition problem for the class of P-4-sparse graphs: the objective is to handle edge/vertex additions and deletions, to recognize if each such modification yields a P-4-sparse graph, and if yes, to update a representation of the graph. Our approach relies on maintaining the modular decomposition tree of the graph, which we use for solving the recognition problem. We establish properties for each modification to yield a P-4-sparse graph and obtain a fully dynamic recognition algorithm which handles edge modifications in O(1) time and vertex modifications in O(d) time for a vertex of degree d. Thus, our algorithm implies an optimal edges-only dynamic algorithm and a new optimal incremental algorithm for P-4-sparse graphs. (C) 2012 Elsevier B.V. All rights reserved.

关键词： fully dynamic algorithm P-4-sparse graph Modular decomposition Recognition

来源：评论

学校读者我要写书评

暂无评论

A fully dynamic algorithm for modular decomposition and recognition of cographs

引用

DISCRETE APPLIED MATHEMATICS 2004年第2-3期136卷 329-340页

作者： Shamir, R Sharan, R Int Comp Sci Inst Berkeley CA 94704 USA Tel Aviv Univ Sackler Fac Exact Sci Sch Comp Sci IL-69978 Tel Aviv Israel

The problem of dynamically recognizing a graph property calls for efficiently deciding if an input graph satisfies the property under repeated modifications to its set of vertices and edges. The input to the problem consists of a series of modifications to be performed on the graph. The objective is to maintain a representation of the graph as long as the property holds, and to detect when it ceases to hold. In this paper, we solve the dynamic recognition problem for the class of cographs and some of its subclasses. Our approach is based on maintaining the modular decomposition tree of the dynamic graph, and using this tree for the recognition. We give the first fully dynamic algorithm for maintaining the modular decomposition tree of a cograph. We thereby obtain fully dynamic algorithms for the recognition of cographs, threshold graphs, and trivially perfect graphs. All these algorithms work in constant time per edge modification and O(d) time per d-degree vertex modification. (C) 2003 Elsevier B.V. All rights reserved.

关键词： fully dynamic algorithm cograph recognition modular decomposition

来源：评论

学校读者我要写书评

暂无评论

A fully dynamic algorithm for modular decomposition and recognition of cographs

A fully dynamic algorithm for modular decomposition and reco...

引用

1st CologneTwente Workshop on Graphs and Combinatorial Optimization (CTW2001)

作者： Shamir, R Sharan, R Int Comp Sci Inst Berkeley CA 94704 USA Tel Aviv Univ Sackler Fac Exact Sci Sch Comp Sci IL-69978 Tel Aviv Israel

关键词： fully dynamic algorithm cograph recognition modular decomposition

来源：评论

学校读者我要写书评

暂无评论

dynamic algorithms for Approximate Steiner Trees

引用

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE 2025年第6-8期37卷

作者： Raikwar, Hemraj Sadharakiya, Harshil Karmakar, Sushanta Indian Inst Technol Guwahati Dept Comp Sci & Engn Gauhati India

This study investigates the dynamic Steiner tree problem. The objective of the Steiner tree problem is to compute a minimum-weight tree connecting a set of designated vertices called terminals in a connected weighted graph with positive real edge weights. A dynamic graph is one in which the set of edges, the set of vertices, or both can change over time. Here, we focus on dynamic graphs where edges can change over time. The work begins by establishing a lower bound on the update time required to maintain an MST heuristic based (2-& varepsilon;)$$ \left(2-\epsilon \right) $$-approximate Steiner tree (where & varepsilon;$$ \epsilon $$ is a small fraction) in a general graph undergoing edge insertions or deletions. Subsequently, we propose two dynamic algorithms: A fully dynamic algorithm to maintain an approximate Steiner tree in planar graphs and an incremental algorithm to maintain an approximate Steiner tree in general graphs. We focus on edge-weighted connected graphs. The graph undergoes dynamic updates where edges with specific weights can be either inserted or deleted. The goal is to efficiently compute a Steiner tree of the updated graph, guaranteeing a solution quality (Steiner tree cost) within a good factor of the optimal Steiner tree. In the fully dynamic case, our analysis demonstrates that the presented algorithm maintains an approximation factor of (2+& varepsilon;)$$ \left(2+\epsilon \right) $$. The worst case update time for processing a series of k$$ k $$ number of updates is & Otilde;(|S|2n+|S|D+n)$$ \overset{\widetilde }{O}\left({\left|S\right|}<^>2\sqrt{n}+|S|D+n\right) $$ where n$$ n $$ is the cardinality of the vertex set of the input graph, D$$ D $$ denotes the unweighted diameter of the updated graph, and k is an element of Z+:1 <= k <=(n+m)$$ k\in {Z}<^>{+}:1\le k\le \left(\sqrt{n+m}\right) $$. It is shown that the update time can be improved to O(n(& varepsilon;')-2)$$ O\left(n{\left({\epsilon}<^>{\prime}\right)}<^>{-2}\right) $$ in a specia

关键词： approximation algorithms dynamic distance oracle dynamic graph algorithms fully dynamic algorithm shortest path forest Steiner tree

来源：评论

学校读者我要写书评

暂无评论

fully dynamic algorithms for bin packing: Being (mostly) myopic helps

引用

SIAM JOURNAL ON COMPUTING 1998年第2期28卷 775-812页

作者： Ivkovic, Z Lloyd, EL Yale Univ Sch Management New Haven CT 06520 USA Univ Delaware Dept Comp & Informat Sci Newark DE 19716 USA

The problem of maintaining an approximate solution for one-dimensional bin packing when items may arrive and depart dynamically is studied. In accordance with various work on fully dynamic algorithms, and in contrast to prior work on bin packing, it is assumed that the packing may be arbitrarily rearranged to accommodate arriving and departing items. In this context our main result is a fully dynamic approximation algorithm for bin packing MMP that is 5/4-competitive and requires Theta(log n) time per operation (i.e., for an Insert or a Delete of an item). This competitive ratio of 5/4 is nearly as good as that of the best practical off-line algorithms. Our algorithm utilizes the technique (introduced here) whereby the packing of an item is done with a total disregard for already packed items of a smaller size. This myopic packing of an item may then cause several smaller items to be repacked (in a similar fashion). With a bit of additional sophistication to avoid certain "bad" cases, the number of items (either individual items or "bundles" of very small items treated as a whole) that needs to be repacked is bounded by a constant.

关键词： bin packing fully dynamic algorithm

来源：评论

学校读者我要写书评

暂无评论

A New Deterministic algorithm for fully dynamic All-Pairs Shortest Paths 2023

A New Deterministic Algorithm for Fully Dynamic All-Pairs Sh...

引用

55th Annual ACM Symposium on Theory of Computing (STOC) part of the ACM Federated Computing Research Conference (FCRC)

作者： Chuzhoy, Julia Zhang, Ruimin Toyota Technol Inst Chicago Chicago IL 60637 USA Univ Chicago Chicago IL USA

ISBN: (纸本)9781450399135

We study the fully dynamic All-Pairs Shortest Paths (APSP) problem in undirected edge-weighted graphs. Given an n-vertex graph.. with non-negative edge lengths, that undergoes an online sequence of edge insertions and deletions, the goal is to support approximate distance queries and shortest-path queries. We provide a deterministic algorithm for this problem, that, for a given precision parameter epsilon, achieves approximation factor (log log n)(2O(1/epsilon 3)), and has amortized update time O(n(epsilon) log L) per operation, where.. is the ratio of longest to shortest edge length. Query time for distance-query is O (2(O(1/epsilon)) center dot log n center dot log log L), and query time for shortest-path query is O (O vertical bar E (P)vertical bar + 2(O (1/epsilon)) center dot log n center dot log log L), where P is the path that the algorithm returns. To the best of our knowledge, even allowing any o(n)-approximation factor, no adaptive-update algorithms with better than Theta(m) amortized update time and better than Theta(n) query time were known prior to this work. We also note that our guarantees are stronger than the best current guarantees for APSP in decremental graphs in the adaptive-adversary setting. In order to obtain these results, we consider an intermediate problem, called Recursive dynamic Neighborhood Cover (RecDynNC), that was formally introduced in [Chuzhoy, STOC '21]. At a high level, given an undirected edge-weighted graph.. undergoing an online sequence of edge deletions, together with a distance parameter D, the goal is to maintain a sparse D-neighborhood cover of G, with some additional technical requirements. Our main technical contribution is twofolds. First, we provide a black-box reduction from APSP in fully dynamic graphs to the RecDynNC problem. Second, we provide a new deterministic algorithm for the RecDynNC problem, that, for a given precision parameter.., achieves approximation factor (log log m)(2O(1/epsilon 2)), with total upda

关键词： all-pairs shortest path fully dynamic algorithm

来源：评论

学校读者我要写书评

暂无评论

fully dynamic Evaluation of Sequence Pair

引用

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 2013年第6期32卷 894-904页

作者： Kozik, Andrzej Wroclaw Univ Technol Inst Comp Engn Control & Robot PL-50370 Wroclaw Poland

In the electronic design automation field, as well as in other areas, problem instances and solutions are often subject to discrete changes. The foundational significance of efficient updates of the criterion value after dynamic updates, instead of recomputing it from scratch each time, has attracted a lot of research. In this paper, motivated by the significance of the sequence pair (SP) representation for floorplanning, we develop a fully dynamic algorithm of SP evaluation, that efficiently updates a criterion value after insertions and deletions of SP elements and after modifications of element weights. Our result is based on a new data structure for the predecessor problem, which maintains the whole history of its dynamic modifications, and the path-compression technique from the union-find problem, which efficiently support predecessor queries. Numerical experiments showed that our algorithm exhibits linear-time behavior and considerably reduces the time of SP evaluation, compared to other approaches.

关键词： Evaluation algorithm fully dynamic algorithm sequence pair

来源：评论

学校读者我要写书评

暂无评论

Near-Optimal fully dynamic Densest Subgraph 2020

Near-Optimal Fully Dynamic Densest Subgraph

引用

52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Sawlani, Saurabh Wang, Junxing Georgia Tech Atlanta GA 30332 USA CMU Pittsburgh PA USA

ISBN: (纸本)9781450369794

We give the first fully dynamic algorithm which maintains a (1 - epsilon)-approximate densest subgraph in worst-case time poly(log n, epsilon(-1)) per update. Dense subgraph discovery is an important primitive for many real-world applications such as community detection, link spam detection, distance query indexing, and computational biology. We approach the densest subgraph problem by framing its dual as a graph orientation problem, which we solve using an augmenting path-like adjustment technique. Our result improves upon the previous best approximation factor of ( 1/4 - epsilon) for fully dynamic densest subgraph [Bhattacharya et. al., STOC '15]. We also extend our techniques to solving the problem on vertex-weighted graphs with similar runtimes. Additionally, we reduce the (1 - epsilon)-approximate densest subgraph problem on directed graphs to.. (log n/epsilon) instances of (1 - epsilon)-approximate densest subgraph on vertex-weighted graphs. This reduction, together with our algorithm for vertex-weighted graphs, gives the first fully-dynamic algorithm for directed densest subgraph in worst-case time poly( log n, epsilon(-1)) per update. Moreover, combined with a near-linear time algorithm for densest subgraph [Bahmani et. al., WAW'14], this gives the first near-linear time algorithm for directed densest subgraph.

关键词： dense subgraph discovery fully dynamic algorithm linear programming dual graph orientation data structures

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：