.png){kind=icon}
.png){kind=icon}
Return
The geodesic-transversal problem
.png){kind=icon}
OA
AI
DOI：10.1016/j.amc.2021.126621.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
A maximal geodesic in a graph is a geodesic (alias shortest path) which is not a subpath of a longer geodesic. The geodesic-transversal problem in a graph G is introduced as the task to find a smallest set Sof vertices of G such that each maximal geodesic has at least one vertex in S. The minimum cardinality of such a set is the geodesic-transversal number gt(G) of G. It is proved that gt (G) = 1 if and only if G is a subdivided star and that the geodesic-transversal problem is NP-complete. Fast algorithms to determine the geodesic-transversal number of trees and of spread cactus graphs are designed, respectively. (C) 2021 Elsevier Inc. All rights reserved.
Keywords:
Hitting set
Geodesic-transversal problem
Network centrality
Tree
Cactus graph
Algorithm
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
3.4
Papers:
2.3W
Citations:
3.3W