Generating Random Test Networks for Shortest Path Algorithms

被引：2

作者：

Adams-Smith, Dennis J. ^{[1
]}

Shier, Douglas R. ^{[1
]}

机构：

[1] Clemson Univ, Dept Math Sci, Clemson, SC 29634 USA

来源：

OPERATIONS RESEARCH AND CYBER-INFRASTRUCTURE | 2009年

关键词：

network generator; random test problems; shortest paths;

D O I：

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

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：295 / 308

页数：14

共 50 条

[21] Proxies for Shortest Path and Distance Queries [J].

Ma, Shuai ;

Feng, Kaiyu ;

Li, Jianxin ;

Wang, Haixun ;

Cong, Gao ;

Huai, Jinpeng .

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 2016, 28 (07) :1835-1850

[22] Shortest path poset of Bruhat intervals [J].

Saúl A. Blanco .

Journal of Algebraic Combinatorics, 2013, 38 :585-596

[23] Shortest path poset of Bruhat intervals [J].

Blanco, Saul A. .

JOURNAL OF ALGEBRAIC COMBINATORICS, 2013, 38 (03) :585-596

[24] SHORTEST PATH QUERIES IN RECTILINEAR WORLDS [J].

De Berg, Mark ;

Van Kreveld, Marc ;

Nilsson, Bengt J. ;

Overmars, Mark .

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 1992, 2 (03) :287-309

[25] Label Constrained Shortest Path Estimation [J].

Likhyani, Ankita ;

Bedathur, Srikanta .

PROCEEDINGS OF THE 22ND ACM INTERNATIONAL CONFERENCE ON INFORMATION & KNOWLEDGE MANAGEMENT (CIKM'13), 2013, :1177-1180

[26] The shortest path problem with forbidden paths [J].

Villeneuve, D ;

Desaulniers, G .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2005, 165 (01) :97-107

[27] Shortest-path network interdiction [J].

Israeli, E ;

Wood, RK .

NETWORKS, 2002, 40 (02) :97-111

[28] Shortest Path Embeddings of Graphs on Surfaces [J].

Hubard, Alfredo ;

Kaluza, Vojtech ;

de Mesmay, Arnaud ;

Tancer, Martin .

DISCRETE & COMPUTATIONAL GEOMETRY, 2017, 58 (04) :921-945

[29] Shortest Path Embeddings of Graphs on Surfaces [J].

Alfredo Hubard ;

Vojtěch Kaluža ;

Arnaud de Mesmay ;

Martin Tancer .

Discrete & Computational Geometry, 2017, 58 :921-945

[30] The Approximability of Shortest Path-Based Graph Orientations of Protein-Protein Interaction Networks [J].

Blokh, Dima ;

Segev, Danny ;

Sharan, Roded .

JOURNAL OF COMPUTATIONAL BIOLOGY, 2013, 20 (12) :945-957

← 1 2 3 4 5 →