Fixed topology Steiner trees and spanning forests

Lusheng Wang; Xiaohua Jia

doi:10.1016/s0304-3975(98)00216-3

Fixed topology Steiner trees and spanning forests

Department of Computer Science

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

8 Citations (Scopus)

Abstract

We present pseudo-polynomial time algorithms for fixed topology Steiner tree problems with various time-delay constraints. We study the spanning forest problem with bandwidth constraint. A polynomial-time algorithm is given. Those problems have applications in network communications. © 1999 Published by Elsevier Science B.V. All rights reserved.

Original language	English
Pages (from-to)	359-370
Journal	Theoretical Computer Science
Volume	215
Issue number	1-2
DOIs	https://doi.org/10.1016/s0304-3975(98)00216-3
Publication status	Published - 28 Feb 1999

Research Keywords

Bandwidth constraints
Fixed topology Steiner trees
Spanning forests
Time-delay

Access Output

10.1016/s0304-3975(98)00216-3Licence: Elsevier user license

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{62923986f49945909fa6765edf0d2eae,

title = "Fixed topology Steiner trees and spanning forests",

abstract = "We present pseudo-polynomial time algorithms for fixed topology Steiner tree problems with various time-delay constraints. We study the spanning forest problem with bandwidth constraint. A polynomial-time algorithm is given. Those problems have applications in network communications. {\textcopyright} 1999 Published by Elsevier Science B.V. All rights reserved.",

keywords = "Bandwidth constraints, Fixed topology Steiner trees, Spanning forests, Time-delay",

author = "Lusheng Wang and Xiaohua Jia",

year = "1999",

month = feb,

day = "28",

doi = "10.1016/s0304-3975(98)00216-3",

language = "English",

volume = "215",

pages = "359--370",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "1-2",

}

TY - JOUR

T1 - Fixed topology Steiner trees and spanning forests

AU - Wang, Lusheng

AU - Jia, Xiaohua

PY - 1999/2/28

Y1 - 1999/2/28

N2 - We present pseudo-polynomial time algorithms for fixed topology Steiner tree problems with various time-delay constraints. We study the spanning forest problem with bandwidth constraint. A polynomial-time algorithm is given. Those problems have applications in network communications. © 1999 Published by Elsevier Science B.V. All rights reserved.

AB - We present pseudo-polynomial time algorithms for fixed topology Steiner tree problems with various time-delay constraints. We study the spanning forest problem with bandwidth constraint. A polynomial-time algorithm is given. Those problems have applications in network communications. © 1999 Published by Elsevier Science B.V. All rights reserved.

KW - Bandwidth constraints

KW - Fixed topology Steiner trees

KW - Spanning forests

KW - Time-delay

UR - https://www.scopus.com/pages/publications/0347028371

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-0347028371&origin=recordpage

U2 - 10.1016/s0304-3975(98)00216-3

DO - 10.1016/s0304-3975(98)00216-3

M3 - RGC 21 - Publication in refereed journal

SN - 0304-3975

VL - 215

SP - 359

EP - 370

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1-2

ER -

Fixed topology Steiner trees and spanning forests

Abstract

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this