liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Complexity of Inverse Shortest Path Routing
Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.ORCID iD: 0000-0001-5907-0087
Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
2011 (English)In: Network Optimization: 5th International Conference, INOC 2011 / [ed] J. Pahl, T. Reiners, and S. Voß, Springer Berlin/Heidelberg, 2011, 339-353 p.Chapter in book (Refereed)
Abstract [en]

The inverse shortest path routing problem is to decide if a set of tentative routing patterns is simultaneously realizable. A routing pattern is defined by its destination and two arc subsets of required shortest path arcs and prohibited non-shortest path arcs. A set of tentative routing patterns is simultaneously realizable if there is a cost vector such that for all routing patterns it holds that all shortest path arcs are in some shortest path and no non-shortest path arc is in any shortest path to the destination of the routing pattern. Our main result is that this problem is NP-complete, contrary to what has been claimed earlier in the literature. Inverse shortest path routing problems naturally arise as a subproblem in bilevel programs where the lower level consists of shortest path problems. Prominent applications that fit into this framework include traffic engineering in IP networks using OSPF or IS-IS and in Stackelberg network pricing games. In this paper we focus on the common subproblem that arises if the bilevel program is linearized and solved by branch-and-cut. Then, it must repeatedly be decided if a set of tentative routing patterns is realizable. In particular, an NP-completeness proof for this problem is given.

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2011. 339-353 p.
Series
Lecture Notes in Computer Science, ISSN 0302-9743 (print), 1611-3349 (online) ; 6701
National Category
Other Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-73152DOI: 10.1007/978-3-642-21527-8_39ISBN: 978-3-642-21526-1 (print)ISBN: 978-3-642-21527-8 (print)OAI: oai:DiVA.org:liu-73152DiVA: diva2:467470
Available from: 2011-12-19 Created: 2011-12-19 Last updated: 2014-10-17Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textFind book in another country/Hitta boken i ett annat landfind book at a swedish library/hitta boken i ett svenskt bibliotek

Authority records BETA

Holmberg, KajCall, Mikael

Search in DiVA

By author/editor
Holmberg, KajCall, Mikael
By organisation
Optimization The Institute of Technology
Other Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 106 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf