A New Necessary Condition for Shortest Path Routing

Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceeding

Abstract

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

Details

Authors
  • Mats Petter Wallander
  • Krzysztof Kuchcinski
Organisations
Research areas and keywords

Subject classification (UKÄ) – MANDATORY

  • Computer Science
Original languageEnglish
Title of host publicationNetwork Control and Optimization (Lecture notes in computer science)
PublisherSpringer
Pages195-204
Volume4465
ISBN (Print)978-3-540-72708-8
Publication statusPublished - 2007
Publication categoryResearch
Peer-reviewedYes
EventFirst EuroFGI International Conference, NET-COOP 2007 - Avignon, France
Duration: 2007 Jul 52007 Jul 7

Publication series

Name
Volume4465
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceFirst EuroFGI International Conference, NET-COOP 2007
CountryFrance
CityAvignon
Period2007/07/052007/07/07