Augmenting trees to meet biconnectivity and diameter constraints

DOI10.1007/s00453-001-0113-8zbMath1052.68099OpenAlexW2143091044MaRDI QIDQ1601019

Victor Chepoi, Yann Vaxès

Publication date: 17 June 2002

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-001-0113-8

zbMATH Keywords

DOMINATING SET problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (19)

Optimizing budget allocation for center and median points ⋮ Fast Algorithms for Diameter-Optimally Augmenting Paths ⋮ Almost optimal algorithms for diameter-optimally augmenting trees ⋮ Vertex fusion under diameter constraints ⋮ Augmenting graphs to minimize the radius ⋮ Finding diameter-reducing shortcuts in trees ⋮ Minimizing the continuous diameter when augmenting a geometric tree with a shortcut ⋮ Fast Algorithms for Diameter-Optimally Augmenting Paths and Trees ⋮ Approximation algorithms for forests augmentation ensuring two disjoint paths of bounded length ⋮ Augmenting graphs to minimize the diameter ⋮ On the characterization of the domination of a diameter-constrained network reliability model ⋮ Unnamed Item ⋮ Augmenting forests to meet odd diameter requirements ⋮ Mixed covering of trees and the augmentation problem with odd diameter constraints ⋮ Improved approximability and non-approximability results for graph diameter decreasing problems ⋮ Vertex fusion under distance constraints ⋮ Mathematical programming models for some smallest-world problems ⋮ Augmenting Outerplanar Graphs to Meet Diameter Requirements ⋮ Algorithms for diameters of unicycle graphs and diameter-optimally augmenting trees

This page was built for publication: Augmenting trees to meet biconnectivity and diameter constraints