Shortest Path Improvement Problems

Xiucui Guan, Panos M. Pardalos and Binwu Zhang
Additional contact information
Xiucui Guan: Southeast University
Binwu Zhang: Hohai University

Chapter Chapter 5 in Inverse Combinatorial Optimization Problems, 2025, pp 141-154 from Springer

Abstract: Abstract We investigate the shortest path improvement problems (Imp-SPs) under different norms. We explore the intricacies of enhancing existing shortest paths in a graph by strategically modifying edge weights to improve the length of the shortest path. We introduce the problem (Imp, SP, Bounded, l 1 $$l_1$$ ) and its complexity, presenting a polynomial-time solution for specific cases. Furthermore, we extend the analysis to (Imp-SPs) under weighted sum Hamming distance, establishing its strong N P $$\mathcal {N}\mathcal {P}$$ -hardness and proposing effective heuristic algorithms. This chapter culminates in an exploration of (Imp-SPs) in tree networks, offering a combinatorial algorithm tailored to exploit the tree’s structure. This work provides a significant contribution to the field, presenting both theoretical insights and practical algorithms for solving (Imp-SPs) efficiently.

Keywords: Shortest path improvement problems; Time complexity; Weighted l 1 $$l_1$$ norm; Sum hamming distance; Trees (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-3-031-91175-0_5

Ordering information: This item can be ordered from
http://www.springer.com/9783031911750

DOI: 10.1007/978-3-031-91175-0_5

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().