Centrality of Shortest Paths: Algorithms and Complexity Results

Johnson Phosavanh
Johnson Phosavanh
[email protected]
https://orcid.org/0000-0002-3073-5230
Discipline of Business Analytics, The University of Sydney, Sydney, New South Wales 2006, Australia
Search for more papers by this author
,
Dmytro Matsypura
Corresponding Author
Dmytro Matsypura
[email protected]
https://orcid.org/0000-0002-0824-4558
Discipline of Business Analytics, The University of Sydney, Sydney, New South Wales 2006, Australia
Search for more papers by this author

Johnson Phosavanh

Johnson Phosavanh

[email protected]

https://orcid.org/0000-0002-3073-5230

Discipline of Business Analytics, The University of Sydney, Sydney, New South Wales 2006, Australia

Search for more papers by this author

,

Dmytro Matsypura

Corresponding Author

Dmytro Matsypura

[email protected]

https://orcid.org/0000-0002-0824-4558

Discipline of Business Analytics, The University of Sydney, Sydney, New South Wales 2006, Australia

Search for more papers by this author

Published Online:9 Dec 2025https://doi.org/10.1287/ijoc.2024.0945

Supplemental Material

ijoc.2024.0945.cd.zip

cover image INFORMS Journal on Computing

Articles In Advance

Article Information

Supplemental Material

Metrics

Information

Received:September 11, 2024
Accepted:August 29, 2025
Published Online:December 09, 2025

Copyright © 2025, INFORMS

Cite as

Johnson Phosavanh, Dmytro Matsypura (2025) Centrality of Shortest Paths: Algorithms and Complexity Results. INFORMS Journal on Computing 0(0).

https://doi.org/10.1287/ijoc.2024.0945

Keywords

Acknowledgments

The authors thank the editors and reviewers for their valuable comments and advice, which helped improve the paper. The authors are grateful to Andreas Ernst and Dan Iancu for helpful suggestions and discussions.