Approximation algorithms for forests augmentation ensuring two disjoint paths of bounded length

DOI10.1016/j.tcs.2008.03.028zbMath1161.68053OpenAlexW2085280901MaRDI QIDQ935155

Yann Vaxès, Victor Chepoi, Bertrand Estellon

Publication date: 31 July 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.03.028

zbMATH Keywords

diametergraph algorithmsapproximation algorithmsdistance constraintsaugmentation problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Cites Work

• A new look at fault-tolerant network routing
• Labeling algorithms for domination problems in sun-free chordal graphs
• On the minimum-cardinality-bounded-diameter and the bounded-cardinality- minimum-diameter edge addition problems
• Augmenting trees to meet biconnectivity and diameter constraints
• Augmenting forests to meet odd diameter requirements
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Diameter increase caused by edge deletion
• Augmentation Problems
• Decreasing the diameter of bounded degree graphs
• Diameter bounds for altered graphs
• Mixed covering of trees and the augmentation problem with odd diameter constraints
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Approximation algorithms for forests augmentation ensuring two disjoint paths of bounded length