A New Necessary Condition for Shortest Path Routing
(2007) First EuroFGI International Conference, NET-COOP 2007 4465. p.195-204- 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
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/622416
- author
- Wallander, Mats Petter LU and Kuchcinski, Krzysztof LU
- organization
- publishing date
- 2007
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- host publication
- Network Control and Optimization (Lecture notes in computer science)
- volume
- 4465
- pages
- 195 - 204
- publisher
- Springer
- conference name
- First EuroFGI International Conference, NET-COOP 2007
- conference location
- Avignon, France
- conference dates
- 2007-07-05 - 2007-07-07
- external identifiers
-
- wos:000247062000021
- scopus:37149007712
- ISSN
- 0302-9743
- 1611-3349
- ISBN
- 978-3-540-72708-8
- DOI
- 10.1007/978-3-540-72709-5_21
- language
- English
- LU publication?
- yes
- id
- edc13d5f-f3dc-4473-a777-5c476b9178ce (old id 622416)
- date added to LUP
- 2016-04-01 12:16:01
- date last changed
- 2024-10-09 03:40:21
@inproceedings{edc13d5f-f3dc-4473-a777-5c476b9178ce, 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}}, author = {{Wallander, Mats Petter and Kuchcinski, Krzysztof}}, booktitle = {{Network Control and Optimization (Lecture notes in computer science)}}, isbn = {{978-3-540-72708-8}}, issn = {{0302-9743}}, language = {{eng}}, pages = {{195--204}}, publisher = {{Springer}}, title = {{A New Necessary Condition for Shortest Path Routing}}, url = {{http://dx.doi.org/10.1007/978-3-540-72709-5_21}}, doi = {{10.1007/978-3-540-72709-5_21}}, volume = {{4465}}, year = {{2007}}, }