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

DOI10.1007/S10878-020-00543-XMaRDI QIDQ2082192zbMATH OpenOpenAlexFDO

Authors Junran Lichen, Jianping Li, 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

AFPTASapproximation algorithmsbin packingstock pieces of length \(L\)subgraph constructions

Mathematics Subject Classification ID

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

Recommendations

• Approximation algorithms for constructing specific subgraphs with minimum number of length-bounded stock pieces
• Approximation algorithms for constructing spanning \(K\)-trees using stock pieces of bounded length
• Approximations for constructing tree-form structures using specific material with fixed length
• Approximating minimum-cost graph problems with spanning tree edges
• Approximations for two variants of the Steiner tree problem in the Euclidean plane \(\mathbb R^2\)

Cites work

• A note on two problems in connexion with graphs
• Approximation algorithms for constructing some required structures in digraphs
• Approximation algorithms for NP-hard problems.
• Approximation schemes for node-weighted geometric Steiner tree problems
• Approximation Schemes for the Restricted Shortest Path Problem
• Approximations for constructing tree-form structures using specific material with fixed length
• Approximations for Steiner trees with minimum number of Steiner points
• Bottleneck Steiner trees in the plane
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 563208 (Why is no real title available?)
• scientific article; zbMATH DE number 1839431 (Why is no real title available?)
• Optimal interconnection trees in the plane. Theory, algorithms and applications
• Steiner tree problem with minimum number of Steiner points and bounded edge-length
• The node-weighted steiner tree problem
• The Steiner tree problem

Cited in

(5)

• Approximation algorithms for constructing specific subgraphs with minimum number of length-bounded stock pieces
• Approximation algorithms for constructing spanning \(K\)-trees using stock pieces of bounded length
• Approximation algorithms for constructing some required structures in digraphs
• Approximations for constructing tree-form structures using specific material with fixed length
• On approximations for constructing required subgraphs using stock pieces of fixed length

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

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