• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

author:

Yao, Pei (Yao, Pei.) [1] | Guo, Longkun (Guo, Longkun.) [2] (Scholars:郭龙坤)

Indexed by:

CPCI-S EI Scopus

Abstract:

Given an integer L is an element of Z(+) and an undirected graph with a weight and a length associated with every edge, the constrained minimum spanning tree (CMST) problem is to compute a minimum weight spanning tree with total length bounded by L. The problem was shown weakly NP-hard in [1], admitting a PTAS with a runtime O(n(O(1/epsilon))(m log(2) n + n log(3) n)) due to Ravi and Goemans [13]. In the paper, we present an exact algorithm for CMST, based on our developed bicameral edge replacement which improves a feasible solution of CMST towards an optimal solution. By applying the classical rounding and scaling technique to the exact algorithm, we can obtain a fully polynomial-time approximation scheme (FPTAS), i.e. an approximation algorithm with a ratio (1 + epsilon) and a runtime O(mn(5) 1/c(2)), where epsilon > 0 is any fixed real number.

Keyword:

Approximation algorithm Bicameral edge replacement Constrained minimum spanning tree FPTAS

Community:

  • [ 1 ] [Yao, Pei]Fuzhou Univ, Coll Math & Comp Sci, Fuzhou 350116, Peoples R China
  • [ 2 ] [Guo, Longkun]Fuzhou Univ, Coll Math & Comp Sci, Fuzhou 350116, Peoples R China

Reprint 's Address:

  • 郭龙坤

    [Guo, Longkun]Fuzhou Univ, Coll Math & Comp Sci, Fuzhou 350116, Peoples R China

Show more details

Version:

Related Keywords:

Related Article:

Source :

COMBINATORIAL OPTIMIZATION AND APPLICATIONS, COCOA 2017, PT I

ISSN: 0302-9743

Year: 2017

Volume: 10627

Page: 103-110

Language: English

0 . 4 0 2

JCR@2005

Cited Count:

WoS CC Cited Count: 1

SCOPUS Cited Count: 1

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 0

Online/Total:90/10116626
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1