Paper Info
Title
Approximation algorithms for constructing specific subgraphs with minimum number of length-bounded stock pieces.
Abstract
Motivated by the Steiner tree problem with minimum number of Steiner points and bounded edge-length in [4], we consider the problem of constructing specific subgraph with minimum number of length-bounded stock pieces (CSS-MSP, for short), which is defined as follows. In some constructing specific subgraph problem Q (CSS, for short), the objective is to choose a minimum-length subset of edges, such that these edges form a specific subgraph (such as a spanning tree or a Steiner tree). In the CSS-MSP problem Q′, these edges are further required to be cut from some stock pieces of length L, and the new objective, however, is to minimize the number of stock pieces of length L to construct all edges in such a specific subgraph.
Year
DOI
Venue
2018
10.1016/j.ipl.2018.04.013
Information Processing Letters
Keywords
Field
DocType
Subgraphs,Stock piece of length L,Bin-packing,Approximation algorithms,APTAS
Discrete mathematics,Approximation algorithm,Combinatorics,Exact algorithm,Steiner tree problem,Spanning tree,Mathematics,Minimum spanning tree,Bounded function
Journal
Volume
ISSN
Citations 
137
0020-0190
0
PageRank 
References 
Authors
0.34
2
3
Name
Order
Citations
PageRank
Junran Lichen122.77
Jianping Li245576.28
Ko-wei Lih352958.80