The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

A New Necessary Condition for Shortest Path Routing

På svenska

Author

  • Mats Petter Wallander
  • Krzysztof Kuchcinski

Summary, in English

In shortest path routing, traffic is routed along shortest paths defined by link weights. However, not all path systems are feasible in that they can be realized in this way. This is something which needs to be taken into account when searching for a set of paths that minimize capacity consumption. In this paper, we discuss a new necessary condition that can be used during search to prune infeasible path systems. The condition can be expressed using linear inequalities, or used in constraint programming, where its simple definition is convenient for the efficient implementation of propagation. Experiments on networks from the SNDLib benchmark show that this condition has strong pruning capabilities

Publishing year

2007

Language

English

Pages

195-204

Publication/Series

Network Control and Optimization (Lecture notes in computer science)

Volume

4465

Document type

Conference paper

Publisher

Springer

Topic

  • Computer Science

Conference name

First EuroFGI International Conference, NET-COOP 2007

Conference date

2007-07-05 - 2007-07-07

Conference place

Avignon, France

Status

Published

Research group

  • ESDLAB

ISBN/ISSN/Other

  • ISSN: 0302-9743
  • ISSN: 1611-3349
  • ISBN: 978-3-540-72708-8