Inverse All Shortest Path Problem

Qiu, Z.; Jokic, I.; Tang, Siyu; Noldus, R.A.C.J.; Van Mieghem, P.F.A.

doi:10.1109/TNSE.2023.3348233

Inverse All Shortest Path Problem

Title

Inverse All Shortest Path Problem

Author

Qiu, Z. (TU Delft Network Architectures and Services)
Jokic, I. (TU Delft Network Architectures and Services)
Tang, Siyu (Huawei Munich Research)
Noldus, R.A.C.J. (TU Delft Network Architectures and Services; Ericsson)
Van Mieghem, P.F.A. (TU Delft Network Architectures and Services)

Date

2024

Abstract

Although resource management schemes and algorithms for networks are well established, we present two novel ideas, based on graph theory, that solve inverse all shortest path problem. Given a symmetric and non-negative demand matrix, the inverse all shortest path problem (IASPP) asks to find a weighted adjacency matrix of a graph such that all the elements in the corresponding shortest path weight matrix are not larger than those of the demand matrix. In contrast to many inverse shortest path problems that are NP-complete, we propose the Descending Order Recovery (DOR) that exactly solves a variant of IASPP, referred to as optimised IASPP. The network provided by DOR minimized the number of links and the sum of the link weights among all the graphs with the same shortest path weight matrix. Our second proposed algorithm, Omega-based Link Removal (OLR), solves the optimised IASPP by utilising the effective resistance from flow networks. The essence of our idea is the applications of properties of flow networks, such as electrical power grids, to compute the needed resources in path networks subject to end-To-end demands, such as telecommunication networks where quality of service constraints specify the end-To-end demands.

Subject

Complex network
effective resistance
graph theory
inverse all shortest path problem (IASPP)
shortest path

To reference this document use:

http://resolver.tudelft.nl/uuid:142c5f4e-2eb5-451d-8642-3440bf0e645c

DOI

https://doi.org/10.1109/TNSE.2023.3348233

Embargo date

2024-10-30

ISSN

2327-4697

Source

IEEE Transactions on Network Science and Engineering, 11 (3), 2703-2714

Bibliographical note

Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

Part of collection

Institutional Repository

Document type

journal article

Rights

Files

file embargo until 2024-10-30