Paper Info
Title
Approximation algorithms for constructing spanning K-trees using stock pieces of bounded length.
Abstract
Given a weighted graph G on (n + 1) vertices, a spanning K-tree (T_K) of G is defined to be a spanning tree T of G together with K distinct edges of G that are not edges of T. The objective of the minimum-cost spanning K-tree problem is to choose a subset of edges to form a spanning K-tree with the minimum weight. In this paper, we consider the constructing spanning K-tree problem that is a generalization of the minimum-cost spanning K-tree problem. We are required to construct a spanning K-tree (T_K) whose (n+K) edges are assembled from some stock pieces of bounded length L. Let (c_0) be the sale price of each stock piece of length L and (k(T_K)) the number of minimum stock pieces to construct the (n+K) edges in (T_K). For each edge e in G, let c(e) be the construction cost of that edge e. Our new objective is to minimize the total cost of constructing a spanning K-tree (T_K), i.e., (min _{T_K}{sum _{ein T_K} c(e)+ k(T_K)cdot c_0}). The main results obtained in this paper are as follows. (1) A 2-approximation algorithm to solve the constructing spanning K-tree problem. (2) A (frac{3}{2})-approximation algorithm to solve the special case for constant construction cost of edges. (3) An APTAS for this special case.
Year
DOI
Venue
2017
10.1007/s11590-016-1078-5
Optimization Letters
Keywords
Field
DocType
K-tree, Stock pieces of length L, Approximation algorithms, APTAS
Discrete mathematics,Graph,Approximation algorithm,Combinatorics,Mathematical optimization,Vertex (geometry),K-tree,Spanning tree,Minimum weight,Mathematics,Bounded function
Journal
Volume
Issue
ISSN
11
8
1862-4480
Citations 
PageRank 
References 
0
0.34
13
Authors
3
Name
Order
Citations
PageRank
Junran Lichen122.77
Jianping Li245576.28
Ko-wei Lih352958.80