Approximating the Diameter of Planar Graphs in Near Linear Time

Weimann Oren; Yuster Raphael

首页> 外文期刊>ACM transactions on algorithms >Approximating the Diameter of Planar Graphs in Near Linear Time

【24h】

Approximating the Diameter of Planar Graphs in Near Linear Time

机译：在近似线性时间内近似平面图的直径

获取原文

获取原文并翻译 | 示例

获取外文期刊封面目录资料

开具论文收录证明 >>

文献代查 >>

文献数据库（团队版） >>

页面导航

摘要
著录项
引文网络
相似文献
相关主题

摘要

We present a (1 + epsilon) -approximation algorithm running in O(f(epsilon) . nlog(4) n) time for finding the diameter of an undirected planar graph with n vertices and with nonnegative edge lengths.

机译：我们提出了一种在O（f（epsilon）。nlog（4）n）时间中运行的（1 + epsilon）逼近算法，以查找具有n个顶点和非负边长的无向平面图的直径。

著录项

来源
《ACM transactions on algorithms》 |2016年第1期|共13页
作者
Weimann Oren; Yuster Raphael;
展开▼
作者单位

展开▼
收录信息
原文格式 PDF
正文语种 eng
中图分类数学;
关键词
All pairs shortest paths; planar graphs; diameter; distance oracles;

机译：所有对最短路径;平面图;直径;距离预言;

相似文献

外文文献
中文文献
专利

1. Approximating the Diameter of Planar Graphs in Near Linear Time [J] . Weimann Oren, Yuster Raphael ACM transactions on algorithms . 2016,第1期

机译：在近似线性时间内近似平面图的直径
2. Faster Approximate Diameter and Distance Oracles in Planar Graphs [J] . Chan Timothy M., Skrepetos Dimitrios Algorithmica . 2019,第8期

机译：平面图中更快的近似直径和距离Oracle
3. Faster Approximate Diameter and Distance Oracles in Planar Graphs [J] . Chan Timothy M., Skrepetos Dimitrios Algorithmica . 2019,第8期

机译：平面图中的更快近似直径和距离畸胎
4. Approximating the Diameter of Planar Graphs in Near Linear Time [C] . Oren Weimann, Raphael Yuster International colloquium on automata, languages and programming . 2013

机译：在近似线性时间内近似平面图的直径
5. Geographically local regression and linear mixed models for tree height-diameter relationship. [D] . Lu, Junfeng. 2010

机译：树高-直径关系的地理局部回归和线性混合模型。
6. On the Approximated Reachability of a Class of Time-Varying Nonlinear Dynamic Systems Based on Their Linearized Behavior about the Equilibria: Applications to Epidemic Models [O] . Manuel De la Sen 2019

机译：基于对均衡的线性化行为的一类时变非线动力系统的近似可达性：应用于流行模型的应用
7. Approximating the diameter of planar graphs in near linear time [O] . Oren Weimann, Raphael Yuster 2013

机译：近线性时间近似平面图的直径
8. Linear Time Coloring of Planar Graphs. [R] . lipton,richard j. miller,raymond e. 1976

机译：平面图的线性时间着色。

Approximating the Diameter of Planar Graphs in Near Linear Time

摘要

著录项

引文网络

相似文献

相关主题

期刊订阅