Fast Algorithms for Diameter-Optimally Augmenting Paths and Trees

被引：2

作者：

Grosse, Ulrike ^{[1
]}

Knauer, Christian ^{[1
]}

Stehn, Fabian ^{[1
]}

Gudmundsson, Joachim ^{[2
]}

Smid, Michiel ^{[3
]}

机构：

[1] Univ Bayreuth, Inst Angew Informat, Univ Str 30, D-95447 Bayreuth, Germany

[2] Univ Sydney, Sch Informat Technol, J12, Sydney, NSW 2006, Australia

[3] Carleton Univ, Sch Comp Sci, 1125 Colonel Dr, Ottawa, ON K1S 5B6, Canada

来源：

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE | 2019年 / 30卷 / 02期

基金：

加拿大自然科学与工程研究理事会;

关键词：

Computational geometry; geometric graphs; diameter; approximation; parametric search; optimization; BOUNDED-DIAMETER;

D O I：

10.1142/S0129054119500060

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We consider the problem of augmenting an n-vertex graph embedded in a metric space, by inserting one additional edge in order to minimize the diameter of the resulting graph. We present exact algorithms for the cases when (i) the input graph is a path, running in O(n log(3) n) time, and (ii) the input graph is a tree, running in O(n(2) log n) time. We also present an algorithm for paths that computes a (1 + epsilon)-approximation in O(n + 1/epsilon(3)) time.

引用

页码：293 / 313

页数：21

共 28 条

[1]

Alon N, 2000, J GRAPH THEOR, V35, P161, DOI 10.1002/1097-0118(200011)35:3<161::AID-JGT1>3.0.CO

[2]

2-Y

[3]

[Anonymous], 2008, COMPUTATIONAL GEOMET, DOI DOI 10.1007/978-3-540-77974-2

[4] Improved approximability and non-approximability results for graph diameter decreasing problems [J].

Bilo, Davide ;

Guala, Luciano ;

Proietti, Guido .

THEORETICAL COMPUTER SCIENCE, 2012, 417 :12-22

[5] Augmenting trees to meet biconnectivity and diameter constraints [J].

Chepoi, V ;

Vaxes, Y .

ALGORITHMICA, 2002, 33 (02) :243-262

[6]

CHUNG FRK, 1984, J GRAPH THEOR, V8, P511, DOI 10.1002/jgt.3190080408

[7]

Cormen T. H., 1990, Introduction to Algorithms

[8] Minimizing the Continuous Diameter when Augmenting a Tree with a Shortcut [J].

De Carufel, Jean-Lou ;

Grimm, Carsten ;

Schirra, Stefan ;

Smid, Michiel .

ALGORITHMS AND DATA STRUCTURES: 15TH INTERNATIONAL SYMPOSIUM, WADS 2017, 2017, 10389 :301-312

[9]

Dodis Y., 1999, Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, P750, DOI 10.1145/301250.301447

[10] How to decrease the diameter of triangle-free graphs [J].

Erdos, P ;

Gyárfás, A ;

Ruszinkó, M .

COMBINATORICA, 1998, 18 (04) :493-501

← 1 2 3 →