scientific article; zbMATH DE number 1405806
From MaRDI portal
Publication:4938792
zbMath0945.05014MaRDI QIDQ4938792
R. Ravi, Tibor Jordán, Joseph Cheriyan
Publication date: 27 September 2000
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Combinatorial aspects of packing and covering (05B40)
Related Items (24)
An optimal rounding for half-integral weighted minimum strongly connected spanning subgraph ⋮ On the tree augmentation problem ⋮ A \({(1+\ln 2)}\)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius ⋮ Generalized laminar families and certain forbidden matrices ⋮ Node connectivity augmentation via iterative randomized rounding ⋮ Maximum flows in parametric graph templates ⋮ Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree ⋮ LP-relaxations for tree augmentation ⋮ Approximating (unweighted) tree augmentation via lift-and-project. I: Stemless TAP ⋮ Shorter tours and longer detours: uniform covers and a bit beyond ⋮ On the cycle augmentation problem: hardness and approximation algorithms ⋮ Multicommodity flow in trees: packing via covering and iterated relaxation ⋮ 2-node-connectivity network design ⋮ Covering a laminar family by leaf to leaf links ⋮ Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees ⋮ On the integrality ratio for tree augmentation ⋮ Unnamed Item ⋮ A (1 + ln 2)-Approximation Algorithm for Minimum-Cost 2-Edge-Connectivity Augmentation of Trees with Constant Radius ⋮ Efficient constructions of convex combinations for 2-edge-connected subgraphs on fundamental classes ⋮ Approximation algorithms for vertex-connectivity augmentation on the cycle ⋮ On small-depth tree augmentations ⋮ Coloring down: 3/2-approximation for special cases of the weighted tree augmentation problem ⋮ An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree ⋮ 2-node-connectivity network design
This page was built for publication:
