A New Necessary Condition for Shortest Path Routing

Mats Petter Wallander, Krzysztof Kuchcinski

Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceedingForskningPeer review

Sammanfattning

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
Originalspråkengelska
Titel på gästpublikationNetwork Control and Optimization (Lecture notes in computer science)
FörlagSpringer
Sidor195-204
Volym4465
ISBN (tryckt)978-3-540-72708-8
DOI
StatusPublished - 2007
EvenemangFirst EuroFGI International Conference, NET-COOP 2007 - Avignon, Frankrike
Varaktighet: 2007 jul 52007 jul 7

Publikationsserier

Namn
Volym4465
ISSN (tryckt)0302-9743
ISSN (elektroniskt)1611-3349

Konferens

KonferensFirst EuroFGI International Conference, NET-COOP 2007
Land/TerritoriumFrankrike
OrtAvignon
Period2007/07/052007/07/07

Ämnesklassifikation (UKÄ)

  • Datavetenskap (datalogi)

Fingeravtryck

Utforska forskningsämnen för ”A New Necessary Condition for Shortest Path Routing”. Tillsammans bildar de ett unikt fingeravtryck.

Citera det här