scientific article; zbMATH DE number 1405806

zbMATH Open0945.05014MaRDI QIDQ4938792FDOQ4938792

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

Publication date: 27 September 2000

Title of this publication is not available (Why is that?)

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

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)

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
• Title not available (Why is that?)
• Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees
• Efficient constructions of convex combinations for 2-edge-connected subgraphs on fundamental classes
• Maximum flows in parametric graph templates
• Shorter tours and longer detours: uniform covers and a bit beyond
• LP-relaxations for tree augmentation
• Algorithms and Computation
• 2-node-connectivity network design
• Approximating (unweighted) tree augmentation via lift-and-project. I: Stemless TAP
• Laminar matroids
• Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree
• On the cycle augmentation problem: hardness and approximation algorithms
• A \({(1+\ln 2)}\)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius
• 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)