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 augmentationlaminar familiesset coversset packings

Mathematics Subject Classification ID

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

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

(30)

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

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)