Partial degree bounded edge packing problem for graphs and k-uniform hypergraphs

DOI10.1007/S10878-015-9868-8MaRDI QIDQ328705zbMATHOpenAlexFDO

Authors Pawan Aurora, Sumit Singh, Shashank K. Mehta

Publication date 20 October 2016

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-015-9868-8

zbMATH Keywords

approximation algorithmLagrangian relaxationedge-packing problemsiterative rounding

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Recommendations

• Partial degree bounded edge packing problem with arbitrary bounds
• Constant factor approximation for the weighted partial degree bounded edge packing problem
• Constant factor approximation for the weighted partial degree bounded edge packing problem
• Partial degree bounded edge packing problem
• An approximation algorithm for the partial vertex cover problem in hypergraphs

Cites work

• A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees
• A factor 2 approximation algorithm for the generalized Steiner network problem
• A unified approach to approximating partial covering problems
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Budgeted Matching and Budgeted Matroid Intersection Via the Gasoline Puzzle
• Improving integrality gaps via Chvátal-Gomory rounding
• Partial degree bounded edge packing problem
• SOFSEM 2006: Theory and Practice of Computer Science
• The constrained minimum spanning tree problem
• Two Bounds for the Domination Number of a Graph

Cited in

(5)

• Constant factor approximation for the weighted partial degree bounded edge packing problem
• Partial degree bounded edge packing problem
• Constant factor approximation for the weighted partial degree bounded edge packing problem
• Partial degree bounded edge packing problem with arbitrary bounds
• Approximating upper degree-constrained partial orientations

This page was built for publication: Partial degree bounded edge packing problem for graphs and \(k\)-uniform hypergraphs

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