Approximating the Diameter of Planar Graphs in Near Linear Time

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

获取原文

页面导航

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

摘要

We present a (1 + ε)-approximation algorithm running in O(f(ε) · n log~4 n) time for finding the diameter of an undirected planar graph with n vertices and with non-negative edge lengths.

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

著录项

来源
《International colloquium on automata, languages and programming》|2013年|828-839|共12页
会议地点
作者
Oren Weimann; Raphael Yuster;
展开▼
作者单位

展开▼
会议组织
原文格式 PDF
正文语种
中图分类
关键词

相似文献

外文文献
中文文献
专利

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

机译：在近似线性时间内近似平面图的直径
2. Approximate tree decompositions of planar graphs in linear time [J] . Kammer Frank, Tholey Torsten Theoretical computer science . 2016,第Null期

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

机译：平面图中更快的近似直径和距离Oracle
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

摘要

著录项

相似文献

相关主题

期刊订阅