On reductions for the Steiner Problem in Graphs

Jeffrey H. Kingston; Nicholas Paul Sheppard

doi:10.1016/S1570-8667(03)00008-X

On reductions for the Steiner Problem in Graphs

Jeffrey H. Kingston, Nicholas Paul Sheppard

Research output: Contribution to journal › Article › peer-review

2 Citations (Scopus)

Abstract

Several authors have demonstrated how reductions can be used to improve the efficiency with which the Steiner Problem in Graphs can be solved. Previous reduction algorithms have been largely ad hoc in nature. This paper uses a theory of confluence to show that, in many cases, all maximal reduction sequences are equivalent, gaining insights into the design of reduction algorithms that obtain a maximum degree of reduction.

Original language	English
Pages (from-to)	77-88
Number of pages	12
Journal	Journal of Discrete Algorithms
Volume	1
Issue number	1
DOIs	https://doi.org/10.1016/S1570-8667(03)00008-X
Publication status	Published - Feb 2003
Externally published	Yes

Keywords

Reduction
Steiner problem

Access to Document

10.1016/S1570-8667(03)00008-X

Cite this

@article{bd746f897a5f44df95fd5ab73040d98b,

title = "On reductions for the Steiner Problem in Graphs",

abstract = "Several authors have demonstrated how reductions can be used to improve the efficiency with which the Steiner Problem in Graphs can be solved. Previous reduction algorithms have been largely ad hoc in nature. This paper uses a theory of confluence to show that, in many cases, all maximal reduction sequences are equivalent, gaining insights into the design of reduction algorithms that obtain a maximum degree of reduction.",

keywords = "Reduction, Steiner problem",

author = "Kingston, {Jeffrey H.} and Sheppard, {Nicholas Paul}",

year = "2003",

month = feb,

doi = "10.1016/S1570-8667(03)00008-X",

language = "English",

volume = "1",

pages = "77--88",

journal = "Journal of Discrete Algorithms",

issn = "1570-8667",

publisher = "Elsevier",

number = "1",

}

TY - JOUR

T1 - On reductions for the Steiner Problem in Graphs

AU - Kingston, Jeffrey H.

AU - Sheppard, Nicholas Paul

PY - 2003/2

Y1 - 2003/2

N2 - Several authors have demonstrated how reductions can be used to improve the efficiency with which the Steiner Problem in Graphs can be solved. Previous reduction algorithms have been largely ad hoc in nature. This paper uses a theory of confluence to show that, in many cases, all maximal reduction sequences are equivalent, gaining insights into the design of reduction algorithms that obtain a maximum degree of reduction.

AB - Several authors have demonstrated how reductions can be used to improve the efficiency with which the Steiner Problem in Graphs can be solved. Previous reduction algorithms have been largely ad hoc in nature. This paper uses a theory of confluence to show that, in many cases, all maximal reduction sequences are equivalent, gaining insights into the design of reduction algorithms that obtain a maximum degree of reduction.

KW - Reduction

KW - Steiner problem

UR - http://www.scopus.com/inward/record.url?scp=77957196915&partnerID=8YFLogxK

U2 - 10.1016/S1570-8667(03)00008-X

DO - 10.1016/S1570-8667(03)00008-X

M3 - Article

AN - SCOPUS:77957196915

SN - 1570-8667

VL - 1

SP - 77

EP - 88

JO - Journal of Discrete Algorithms

JF - Journal of Discrete Algorithms

IS - 1

ER -

On reductions for the Steiner Problem in Graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this