Approximation algorithms for constructing specific subgraphs with minimum number of length-bounded stock pieces

DOI10.1016/j.ipl.2018.04.013zbMath1478.68248OpenAlexW2802366486MaRDI QIDQ1641150

Ko-Wei Lih, Junran Lichen, Jianping Li

Publication date: 15 June 2018

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2018.04.013

zbMATH Keywords

approximation algorithmsbin-packingsubgraphsAPTASstock piece

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Cites Work

• Steiner tree problem with minimum number of Steiner points and bounded edge-length
• The Steiner tree problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Approximations for Steiner trees with minimum number of Steiner points
• Unnamed Item
• Unnamed Item

This page was built for publication: Approximation algorithms for constructing specific subgraphs with minimum number of length-bounded stock pieces