Augmenting trees to meet biconnectivity and diameter constraints

DOI10.1007/S00453-001-0113-8MaRDI QIDQ1601019zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Algorithms and Computation
• Augmenting forests to meet odd diameter requirements
• scientific article; zbMATH DE number 1156599
• Augmenting outerplanar graphs to meet diameter requirements
• The parametric complexity of graph diameter augmentation

Cited in

(25)

• Vertex fusion under distance constraints
• Mixed covering of trees and the augmentation problem with odd diameter constraints
• Augmenting forests to meet odd diameter requirements
• Algorithms and Computation
• Augmenting graphs to minimize the radius
• Vertex fusion under diameter constraints
• Fast algorithms for diameter-optimally augmenting paths
• Fast algorithms for diameter-optimally augmenting paths and trees
• Minimizing the continuous diameter when augmenting a geometric tree with a shortcut
• Algorithms for diameters of unicycle graphs and diameter-optimally augmenting trees
• Almost optimal algorithms for diameter-optimally augmenting trees
• Minimizing the continuous diameter when augmenting a tree with a shortcut
• Finding diameter-reducing shortcuts in trees
• Mixed covering of trees and the augmentation problem with odd diameter constraints
• Augmenting outerplanar graphs to meet diameter requirements
• On the Hardness and Approximability of Planar Biconnectivity Augmentation
• Mathematical programming models for some smallest-world problems
• Approximation algorithms for forests augmentation ensuring two disjoint paths of bounded length
• scientific article; zbMATH DE number 1156599 (Why is no real title available?)
• Optimizing budget allocation for center and median points
• Almost optimal algorithms for diameter-optimally augmenting trees
• scientific article; zbMATH DE number 7205039 (Why is no real title available?)
• Improved approximability and non-approximability results for graph diameter decreasing problems
• On the characterization of the domination of a diameter-constrained network reliability model
• The parametric complexity of graph diameter augmentation

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

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