scientific article; zbMATH DE number 1405806

MaRDI QIDQ4938792zbMATH OpenFDO

Authors R. Ravi, Joseph Cheriyan, Tibor Jordán

Publication date 27 September 2000

zbMATH Keywords

connectivity augmentationset packingsset coverslaminar families

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Combinatorial aspects of packing and covering (05B40)

Recommendations

• Approximation algorithms for maximum weight k-coverings of graphs by packings
• On star family packing of graphs
• Minimizing a monotone concave function with laminar covering constraints
• On the tractability of some natural packing, covering and partitioning problems
• Algorithms and Computation

Cited in

(27)

• Coloring down: 3/2-approximation for special cases of the weighted tree augmentation problem
• On the integrality ratio for tree augmentation
• Covering a laminar family by leaf to leaf links
• On the tree augmentation problem
• Approximation algorithms for vertex-connectivity augmentation on the cycle
• 2-node-connectivity network design
• Node connectivity augmentation via iterative randomized rounding
• A \((1 + \ln 2)\)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius
• An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
• Better-than-\(\frac{4}{3}\)-approximations for leaf-to-leaf tree and connectivity augmentation
• Generalized laminar families and certain forbidden matrices
• An optimal rounding for half-integral weighted minimum strongly connected spanning subgraph
• scientific article; zbMATH DE number 7205039 (Why is no real title available?)
• Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees
• Efficient constructions of convex combinations for 2-edge-connected subgraphs on fundamental classes
• Shorter tours and longer detours: uniform covers and a bit beyond
• Maximum flows in parametric graph templates
• LP-relaxations for tree augmentation
• Laminar matroids
• 2-node-connectivity network design
• Approximating (unweighted) tree augmentation via lift-and-project. I: Stemless TAP
• Algorithms and Computation
• A \({(1+\ln 2)}\)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius
• On the cycle augmentation problem: hardness and approximation algorithms
• Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree
• On small-depth tree augmentations
• Multicommodity flow in trees: packing via covering and iterated relaxation

This page was built for publication:

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