Inverse All Shortest Path Problem

doi:10.1109/TNSE.2023.3348233

Inverse All Shortest Path Problem

2024-05-01

0

PRE

AI

DOI：10.1109/TNSE.2023.3348233

Original

Original request for help

Save

Abstract

En 中文

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.

Keywords:

Resistance

Symmetric matrices

Shortest path problem

Matrix decomposition

Delays

Eigenvalues and eigenfunctions

Voltage

Complex network

inverse all shortest path problem (IASPP)

graph theory

shortest path

effective resistance

Inverse All Shortest Path Problem

Abstract

Journal

Organization