Constant factor approximation for the weighted partial degree bounded edge packing problem

DOI10.1007/978-3-319-48749-6_14MaRDI QIDQ2958313zbMATH OpenOpenAlexFDO

Authors Pawan Aurora, Monalisa Jena, Rajiv Raman

Publication date 1 February 2017

Published in Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-48749-6_14

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Constant factor approximation for the weighted partial degree bounded edge packing problem
• Partial degree bounded edge packing problem with arbitrary bounds
• Partial degree bounded edge packing problem for graphs and \(k\)-uniform hypergraphs
• Partial degree bounded edge packing problem
• Degree-Constrained Subgraph Problems: Hardness and Approximation Results

Cites work

• scientific article; zbMATH DE number 5999574 (Why is no real title available?)
• scientific article; zbMATH DE number 2086940 (Why is no real title available?)
• A partial k-arboretum of graphs with bounded treewidth
• Approximation algorithms for NP-complete problems on planar graphs
• Approximation hardness of dominating set problems in bounded degree graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Computing on binary strings
• Generalized hypergraph matching via iterated packing and local ratio
• Iterative packing for demand and hypergraph matching
• Matching theory
• Partial degree bounded edge packing problem
• Partial degree bounded edge packing problem with arbitrary bounds
• Paths, Trees, and Flowers
• SOFSEM 2006: Theory and Practice of Computer Science

Cited in

(4)

• Constant factor approximation for the weighted partial degree bounded edge packing problem
• Partial degree bounded edge packing problem with arbitrary bounds
• Partial degree bounded edge packing problem for graphs and \(k\)-uniform hypergraphs
• Partial degree bounded edge packing problem

This page was built for publication: Constant factor approximation for the weighted partial degree bounded edge packing problem

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