Fast algorithms for diameter-optimally augmenting paths and trees

DOI10.1142/S0129054119500060zbMATH Open1415.68254arXiv1607.05547OpenAlexW2963394786WikidataQ128226181 ScholiaQ128226181MaRDI QIDQ5384465FDOQ5384465

Authors: Ulrike Große, Christian Knauer, Fabian Stehn, Joachim Gudmundsson, Michiel Smid 

Publication date: 24 June 2019

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Abstract: 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 that computes a (1+eps)-approximation in O(n + 1/eps^3) time, for paths in R^d, where d is a constant.

Full work available at URL: https://arxiv.org/abs/1607.05547

Recommendations

• Fast algorithms for diameter-optimally augmenting paths
• Almost optimal algorithms for diameter-optimally augmenting trees
• Algorithms for radius-optimally augmenting trees in a metric space

zbMATH Keywords

optimizationcomputational geometryapproximationdiametergeometric graphsparametric search

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• Bounded-diameter minimum-cost graph problems
• Title not available (Why is that?)
• On the minimum-cardinality-bounded-diameter and the bounded-cardinality- minimum-diameter edge addition problems
• Augmenting trees to meet biconnectivity and diameter constraints
• Diameter bounds for altered graphs
• Computational geometry. Algorithms and applications.
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Combinatorial Optimization with Rational Objective Functions
• Diameter increase caused by edge deletion
• Computing the dilation of edge-augmented graphs in metric spaces
• Euclidean chains and their shortcuts
• Design networks with bounded pairwise distance
• The parametric complexity of graph diameter augmentation
• Augmenting outerplanar graphs to meet diameter requirements
• Decreasing the diameter of bounded degree graphs
• Improved approximability and non-approximability results for graph diameter decreasing problems
• Parametric search made practical
• Improving the Stretch Factor of a Geometric Network by Edge Augmentation
• Title not available (Why is that?)
• Fast algorithms for diameter-optimally augmenting paths
• Augmenting the connectivity of planar and geometric graphs
• How to decrease the diameter of triangle-free graphs
• Minimizing the continuous diameter when augmenting a tree with a shortcut
• Computing Best and Worst Shortcuts of Graphs Embedded in Metric Spaces
• A near-optimal algorithm for finding an optimal shortcut of a tree

Cited In (14)

• Algorithms for radius-optimally augmenting trees in a metric space
• Algorithms for radius-optimally augmenting trees in a metric space
• Algorithms for diameters of unicycle graphs and diameter-optimally augmenting trees
• Fast algorithms for diameter-optimally augmenting paths
• Shortest augmenting paths for online matchings on trees
• Algorithms for diameters of unicycle graphs and diameter-optimally augmenting trees
• A linear-time algorithm for discrete radius optimally augmenting paths in a metric space
• Almost optimal algorithms for diameter-optimally augmenting trees
• Algorithms and Data Structures
• Finding diameter-reducing shortcuts in trees
• Minimizing the continuous diameter when augmenting a tree with a shortcut
• Almost optimal algorithms for diameter-optimally augmenting trees
• Augmenting graphs to minimize the radius
• Upgrading trees under diameter and budget constraints

This page was built for publication: Fast algorithms for diameter-optimally augmenting paths and trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5384465)