Generating random test networks for shortest path algorithms

Dennis J. Adams-Smith; Douglas R. Shier

doi:10.1007/978-0-387-88843-9_15

Generating random test networks for shortest path algorithms

Dennis J. Adams-Smith, Douglas R. Shier

Clemson University

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

2 Scopus citations

Abstract

One of the pillars in the empirical testing of algorithms is the generation of representative and suitably informative test problems. We investigate the particular case of generating random test networks for shortest path problems and discuss several methods proposed for generating such networks. Both analytic and simulation results reveal several pitfalls to avoid in the generation of test networks. We also identify two particular generation methods having desirable characteristics.

Original language	English
Pages (from-to)	295-308
Number of pages	14
Journal	Operations Research/ Computer Science Interfaces Series
Volume	47
DOIs	https://doi.org/10.1007/978-0-387-88843-9_15
State	Published - 2009
Externally published	Yes

Keywords

Network generator
Random test problems
Shortest paths

Access to Document

10.1007/978-0-387-88843-9_15

Cite this

@article{fb7166ffed4844f39a44500340d59a2f,

title = "Generating random test networks for shortest path algorithms",

abstract = "One of the pillars in the empirical testing of algorithms is the generation of representative and suitably informative test problems. We investigate the particular case of generating random test networks for shortest path problems and discuss several methods proposed for generating such networks. Both analytic and simulation results reveal several pitfalls to avoid in the generation of test networks. We also identify two particular generation methods having desirable characteristics.",

keywords = "Network generator, Random test problems, Shortest paths",

author = "Adams-Smith, \{Dennis J.\} and Shier, \{Douglas R.\}",

year = "2009",

doi = "10.1007/978-0-387-88843-9\_15",

language = "English",

volume = "47",

pages = "295--308",

journal = "Operations Research/ Computer Science Interfaces Series",

issn = "1387-666X",

publisher = "Springer Science + Business Media",

}

TY - JOUR

T1 - Generating random test networks for shortest path algorithms

AU - Adams-Smith, Dennis J.

AU - Shier, Douglas R.

PY - 2009

Y1 - 2009

N2 - One of the pillars in the empirical testing of algorithms is the generation of representative and suitably informative test problems. We investigate the particular case of generating random test networks for shortest path problems and discuss several methods proposed for generating such networks. Both analytic and simulation results reveal several pitfalls to avoid in the generation of test networks. We also identify two particular generation methods having desirable characteristics.

AB - One of the pillars in the empirical testing of algorithms is the generation of representative and suitably informative test problems. We investigate the particular case of generating random test networks for shortest path problems and discuss several methods proposed for generating such networks. Both analytic and simulation results reveal several pitfalls to avoid in the generation of test networks. We also identify two particular generation methods having desirable characteristics.

KW - Network generator

KW - Random test problems

KW - Shortest paths

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

U2 - 10.1007/978-0-387-88843-9_15

DO - 10.1007/978-0-387-88843-9_15

M3 - Article

AN - SCOPUS:84888631546

SN - 1387-666X

VL - 47

SP - 295

EP - 308

JO - Operations Research/ Computer Science Interfaces Series

JF - Operations Research/ Computer Science Interfaces Series

ER -

Generating random test networks for shortest path algorithms

Abstract

Keywords

Access to Document

Other files and links

Cite this