Combinatorial Algorithms. 29th International Workshop, IWOCA 2018, Singapore, July 16–19, 2018. Lecture Notes in Computer Science

Vol. 10979. Springer, 2018.

Under the general editorship: C. Iliopoulos, H. W. Leong, W. Sung

This book constitutes the refereed post-conference proceedings of the 29th International Workshop on Combinatorial Algorithms, IWOCA 2018, held in Singapore, Singapore, in July 2018. The 31 regular papers presented in this volume were carefully reviewed and selected from 69 submissions. They cover diverse areas of combinatorical algorithms, complexity theory, graph theory and combinatorics, combinatorial optimization, cryptography and information security, algorithms on strings and graphs, graph drawing and labelling, computational algebra and geometry, computational biology, probabilistic and randomised algorithms, algorithms for big data analytics, and new paradigms of computation.

Chapters

Branch-and-bound algorithm for Symmetric Travelling Salesman Problem

Alexey Nikolaev, Mikhail Batsyn, , in: Combinatorial Algorithms. 29th International Workshop, IWOCA 2018, Singapore, July 16–19, 2018. Lecture Notes in Computer ScienceVol. 10979.: Springer, 2018. P. 311–322.

In this paper a branch-and-bound algorithm for the Symmetric Travelling Salesman Problem (STSP) is presented. The algorithm is based on the 1-tree Lagrangian relaxation. A new branching strategy is suggested in which the algorithm branches on the 1-tree edge belonging to the vertex with maximum degree in the 1-tree and having the maximum tolerance. This ...

Added: October 23, 2018

Keywords: combinatorial optimization, data mining, approximation algorithms, cryptography, graph algorithms, graph drawing, computational geometry, heuristic methods, information security, Data security, computer graphics, artificial intelligence, authentication, graph theory, drawing (graphics), linear programming problem