Premium
Exact algorithms for minimum routing cost trees
Author(s) -
Fischetti Matteo,
Lancia Giuseppe,
Serafini Paolo
Publication year - 2002
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.10022
Subject(s) - computer science , shortest path problem , heuristic , mathematical optimization , graph , steiner tree problem , algorithm , routing (electronic design automation) , set (abstract data type) , tree (set theory) , path (computing) , mathematics , theoretical computer science , combinatorics , computer network , programming language
Given a set of points and distances between them, a basic problem in network design calls for selecting a graph connecting them at a minimum total routing cost , that is, the sum over all pairs of points of the length of their shortest path in the graph. In this paper, we describe some branch‐and‐bound algorithms for the exact solution of a relevant special case arising when the graph has to be a tree. One of the enhancements to our algorithms is the use of “LP shortcutting,” which we introduce as a general‐purpose technique for speeding up the search. Besides network design, we show how trees of small routing cost find useful application in computational biology, where they can be used to determine good alignments of genomic sequences. This leads to a novel alignment heuristic that we analyze in our computational section. © 2002 Wiley Periodicals, Inc.