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)

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

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)