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

semi-dynamic algorithms for strongly chordal graphs

DISCRETE MATHEMATICS algorithms AND APPLICATIONS 2021年第4期13卷

作者： Rahman, Md Zamilur Mukhopadhyay, Asish Univ Windsor Sch Comp Sci Windsor ON N9B 3P4 Canada

Within the broad ambit of algorithm design, the study of dynamic graph algorithms continues to be a thriving area of research. Commensurate with this interest is an extensive literature on the topic. Not surprisingly, dynamic algorithms for all varieties of shortest path problems, in view of their practical importance, occupy a preeminent position. Relevant to this paper are fully dynamic algorithms for chordal graphs. Surprisingly, to the best of our knowledge, there seems to be no reported results for the problem of dynamic algorithms for strongly chordal graphs. To redress this gap, in this paper, we propose a semi-dynamic algorithm for edge-deletions and a semi-dynamic algorithm for edge-insertions in a strongly chordal graph, G. The query complexity of an edge-deletion is O(d(u)(2)d(v)(2)), where d(u) and d(v) are the degrees of the vertices u and v of the candidate edge {u,v}, while the query complexity of an edge-insertion is O(n(2)), where n is the number of vertices of G.

关键词： Algorithm design graph algorithms semi-dynamic algorithms strongly chordal graphs

来源：评论

学校读者我要写书评

暂无评论

Maintaining Shortest Path Tree in dynamic Digraphs Having Negative Edge-Weights

Maintaining Shortest Path Tree in Dynamic Digraphs Having Ne...

引用

1st International Conference on Computer Science, Engineering and Information Technology (CCSEIT 2011)

作者： Rai, Atul Kumar Agarwal, Suneeta Motilal Nehru Natl Inst Technol Dept Comp Sci & Engn Allahabad Uttar Pradesh India

ISBN: (纸本)9783642240362;9783642240379

Given a directed graph G, a source vertex s and shortest path tree (SPT). T(s) rooted at 8 in G, the dynamic shortest path problem is to find the new SPT, T'(s) in G from T(s) when update(s) on edge weight(s) are performed. Previous works focus either on single edge weight update at a time or, process a set of updates together with the constraint that edge weights remain positive. In this paper we propose two semi-dynamic algorithms (one for increase only and the other for decrease only case) for maintaining SPT in a directed graph, even when some of edge weights assume negative values. Our algorithms process multiple edge weight updates simultaneously and also able to detect presence of negative weight cycle if introduced during update, to assert that no real SPT exists. From experiments conducted, we observe that dynamic algorithms perform better than the static algorithm when the percentage of updated edges is smaller than a certain threshold.

关键词： dynamic graphs dynamic shortest paths Shortest path trees semi-dynamic algorithms Fully-dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：