Variable neighborhood scatter search for the incremental graph drawing problem

被引：0
作者：
Jesús Sánchez-Oro
Anna Martínez-Gavara
Manuel Laguna
Rafael Martí
Abraham Duarte
机构：
[1] Universidad Rey Juan Carlos,Departamento de Ciencias de la Computación
[2] Universidad de Valencia,Departamento de Estadística e Investigación Operativa
[3] University of Colorado Boulder,Leeds School of Business
来源：
Computational Optimization and Applications | 2017年 / 68卷
关键词：
Graph drawing; Scatter search; Incremental graph; Dynamic graph drawing; Metaheuristics;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
Automated graph-drawing systems utilize procedures to place vertices and arcs in order to produce graphs with desired properties. Incremental or dynamic procedures are those that preserve key characteristics when updating an existing drawing. These methods are particularly useful in areas such as planning and logistics, where updates are frequent. We propose a procedure based on the scatter search methodology that is adapted to the incremental drawing problem in hierarchical graphs. These drawings can be used to represent any acyclic graph. Comprehensive computational experiments are used to test the efficiency and effectiveness of the proposed procedure.
引用
收藏
页码：775 / 797
页数：22
相关论文
共 25 条
[1]  
Carpano M(1980)Automatic display of hierarchized graphs for computer-aided decision analysis IEEE Trans. Syst. Man Cybern. 10 705-715
[2]  
Duarte A(2016)Parallel variable neighbourhood search strategies for the cutwidth minimization problem IMA J. Manag. Math. 27 55-73
[3]  
Pantrigo JJ(1995)Greedy randomized adaptive search procedures J. Glob. Optim. 6 109-133
[4]  
Pardo EG(1983)Crossing number is NP-complete SIAM J. Algebraic Discrete Methods 4 312-316
[5]  
Sánchez-Oro J(2008)Variable neighborhood search: methods and applications 4OR 6 319-360
[6]  
Feo TA(1999)GRASP and path relinking for 2-layer straight line crossing minimization INFORMS J. Comput. 11 44-52
[7]  
Resende MG(1997)Arc crossing minimization in hierarchical digraphs with tabu search Comput. Oper. Res. 24 1175-1186
[8]  
Garey M(2001)Incremental bipartite drawing problem Comput. Oper. Res. 28 1287-1298
[9]  
Johnson D(1997)Variable neighborhood search Comput. Oper. Res. 24 1097-1100
[10]  
Hansen P(2000)Effective information visualization: a study of graph drawing aesthetics and algorithms Interact. Comput. 13 147-162
123