An Efficient Algorithm for Determining the Length of the Longest Dead Path in an 'Lifo' Branch-and-Bound Exploration Schema,

Abstract

The length of the longest dead path (LLDP) is a widely used parameter in estimating the efficiency of branch-and-bound optimization algorithms that employ the LIFO exploration schema. Thanks to two original theorems, we are able to present a particularly attractive procedure for determining of the LLDP. In fact this procedure requires a number of storage variables which is independent of problem size and very small; moreover, the procedure is self-contained in the sense that it can be externally attached to any LIFO branch-and-bound program without interfering with its algorithms and data structures. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1980
Accession Number
ADA079912

Entities

People

  • Stefano Pallottino
  • Tommaso Toffoli

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Ground and Sea Platforms

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Classification
  • Computer Science
  • Computers
  • Digital Information
  • Efficiency
  • Graph Theory
  • Information Systems
  • Marine Corps
  • Mathematics
  • Military Research
  • Naval Operations
  • Security
  • Sequences
  • Technical Information Centers
  • Trees (Data Structures)

Readers

  • Distributed Systems and Data Platform Development
  • Mathematical Modeling and Probability Theory.
  • Regression Analysis.