Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor(s)

Author(s):

Polzin, Tobias
Vahdati Daneshmand, Siavash

dblp
dblp

Not MPG Author(s):

Vahdati Daneshmand, Siavash

BibTeX cite key*:

PolzinVahdati2001b

Title

Title*:

Improved Algorithms for the Steiner Problem in Networks

Journal

Journal Title*:

Discrete Applied Mathematics

Journal's URL:


Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:

Elsevier

Publisher's URL:

http://www.elsevier.nl

Publisher's
Address:

Amsterdam, The Netherlands

ISSN:

0166-218X

Vol, No, pp, Date

Volume*:

112

Number:


Publishing Date:

August 2001

Pages*:

263-300

Number of
VG Pages:

95

Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) Abstract:

We present several new techniques for dealing with the Steiner problem in (undirected)
networks. We consider them as building blocks of an exact algorithm, but each of them
could also be of interest in its own right. First, we consider some relaxations of integer
programming formulations of this problem and investigate different methods for dealing
with these relaxations, not only to obtain lower bounds, but also to get additional
information which is used in the computation of upper bounds and in reduction
techniques. Then, we modify some known reduction tests and introduce some new ones.
We integrate some of these tests into a package with a small worst case time which
achieves impressive reductions on a wide range of instances. On the side of upper
bounds, we introduce the new concept of heuristic reductions. On the basis of this
concept, we develop heuristics that achieve sharper upper bounds than the strongest
known heuristics for this problem despite running times which are smaller by orders of
magnitude. Finally, we integrate these blocks into an exact algorithm. We present
computational results on a variety of benchmark instances. The results are clearly
superior to those of all other exact algorithms known to the authors.

URL for the Abstract:


Categories,
Keywords:

Steiner Problem, Relaxation, Lower Bound

HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

Expert

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{PolzinVahdati2001b,
AUTHOR = {Polzin, Tobias and Vahdati Daneshmand, Siavash},
TITLE = {Improved Algorithms for the {Steiner} Problem in Networks},
JOURNAL = {Discrete Applied Mathematics},
PUBLISHER = {Elsevier},
YEAR = {2001},
VOLUME = {112},
PAGES = {263--300},
ADDRESS = {Amsterdam, The Netherlands},
MONTH = {August},
ISBN = {0166-218X},
}


Entry last modified by Christine Kiesel, 03/02/2010
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Andreas Polzin
Created
08/06/2001 05:47:24 PM
Revisions
5.
4.
3.
2.
1.
Editor(s)
Christine Kiesel
Anja Becker
Anja Becker
Tobias Polzin
Tobias Polzin
Edit Dates
26.08.2003 15:15:29
08.04.2002 15:56:11
08.04.2002 15:11:43
14/01/2002 15:19:37
06/08/2001 18:24:55
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section