Improved approximability and non-approximability results for graph diameter decreasing problems
type: Item
instance of: scholarly article
title: Improved approximability and non-approximability results for graph diameter decreasing problems
zbMATH Open document ID: 1234.68127
author: D. Bilò
author: Luciano Gualà
author: Guido Proietti
published in: Theoretical Computer Science
publication date: 2012-03-13T00:00:00Z
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 6014313
zbMATH Keywords: approximation algorithms
zbMATH Keywords: graphs
zbMATH Keywords: edge addition
zbMATH Keywords: diameter
MaRDI profile type: Publication
full work available at URL: j.tcs.2011.05.014
OpenAlex ID: W1973394376
cites work: Decreasing the diameter of bounded degree graphs
cites work: A textbook of graph theory
cites work: Graph Classes: A Survey
cites work: Location on Tree Networks: P-Centre and n-Dispersion Problems
cites work: Mixed covering of trees and the augmentation problem with odd diameter constraints
cites work: Augmenting trees to meet biconnectivity and diameter constraints
cites work: Q3470486
cites work: Diameter bounds for altered graphs
cites work: Minimizing the Diameter of a Network Using Shortcut Edges
cites work: Design networks with bounded pairwise distance
cites work: How to decrease the diameter of triangle-free graphs
cites work: Q5339970
cites work: Clustering to minimize the maximum intercluster distance
cites work: Decreasing the diameter of cycles
cites work: Augmenting forests to meet odd diameter requirements
cites work: Approximation algorithms for combinatorial problems
cites work: Bounded-diameter minimum-cost graph problems
cites work: An Algorithmic Approach to Network Location Problems. I: Thep-Centers
cites work: On the minimum-cardinality-bounded-diameter and the bounded-cardinality- minimum-diameter edge addition problems
cites work: Minimizing Average Shortest Path Distances via Shortcut Edge Addition
cites work: On the computational complexity of centers locating in a graph
cites work: The complexity of designing a network with minimum diameter
cites work: Q4527015
cites work: Diameter increase caused by edge deletion
DOI: 10.1016/J.TCS.2011.05.014
description: scientific article; zbMATH DE number 6014313