Approximation algorithms for constructing required subgraphs using stock pieces of fixed length

DOI10.1007/s10878-020-00543-xzbMath1502.90151OpenAlexW3006425482MaRDI QIDQ2082192

Jianping Li, Junran Lichen, Ko-Wei Lih, Xingxing Yu

Publication date: 4 October 2022

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

Full work available at URL: https://doi.org/10.1007/s10878-020-00543-x

zbMATH Keywords

approximation algorithmsbin packingAFPTASstock pieces of length \(L\)subgraph constructions

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• Steiner tree problem with minimum number of Steiner points and bounded edge-length
• Approximations for constructing tree-form structures using specific material with fixed length
• The Steiner tree problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Approximation algorithms for constructing some required structures in digraphs
• Optimal interconnection trees in the plane. Theory, algorithms and applications
• Approximation schemes for node-weighted geometric Steiner tree problems
• The node-weighted steiner tree problem
• Approximation Schemes for the Restricted Shortest Path Problem
• Bottleneck Steiner trees in the plane
• Approximations for Steiner trees with minimum number of Steiner points

This page was built for publication: Approximation algorithms for constructing required subgraphs using stock pieces of fixed length