{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,27]],"date-time":"2024-09-27T20:40:10Z","timestamp":1727469610480},"reference-count":0,"publisher":"Journal of Graph Algorithms and Applications","issue":"7","license":[{"start":{"date-parts":[[2023,8,1]],"date-time":"2023-08-01T00:00:00Z","timestamp":1690848000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["JGAA"],"abstract":"<jats:p>Let $G$ be an undirected graph with non-negative edge weights and let $S$ be a subset of its shortest paths such that, for every pair $(u,v)$ of distinct vertices, $S$ contains exactly one shortest path between $u$ and $v$. In this paper we define a range space associated with $S$ and prove that its VC dimension is 2. As a consequence, we show a bound for the number of shortest paths trees required to be sampled in order to solve a relaxed version of the All-pairs Shortest Paths problem (APSP) in $G$. In this version of the problem we are interested in computing all shortest paths with a certain \"importance\" \nat least $\\varepsilon$. Given any $0 &lt; \\varepsilon$, $ \\delta &lt; 1$, we propose a $\\mathcal{O}(m + n \\log n + (\\textrm{diam}_{V(G)})^2)$ sampling algorithm that outputs with probability $1 - \\delta$ the (exact) distance and the shortest path between every pair of vertices $(u, v)$ that appears as subpath of at least a proportion $\\varepsilon$ of all shortest paths in the set $S$, where $\\textrm{diam}_{V(G)}$ is the vertex-diameter of $G$. The bound that we obtain for the sample size depends only on $\\varepsilon$ and $\\delta$, and do not depend on the size of the graph.<\/jats:p>","DOI":"10.7155\/jgaa.00636","type":"journal-article","created":{"date-parts":[[2023,9,7]],"date-time":"2023-09-07T15:18:22Z","timestamp":1694099902000},"page":"603-619","source":"Crossref","is-referenced-by-count":0,"title":["A Range Space with Constant VC Dimension for All-pairs Shortest Paths in Graphs"],"prefix":"10.7155","volume":"27","author":[{"given":"Alane","family":"De Lima","sequence":"first","affiliation":[]},{"given":"Murilo","family":"Da Silva","sequence":"additional","affiliation":[]},{"given":"Andr\u00e9","family":"Vignatti","sequence":"additional","affiliation":[]}],"member":"4175","published-online":{"date-parts":[[2023,8,1]]},"container-title":["Journal of Graph Algorithms and Applications"],"original-title":[],"link":[{"URL":"https:\/\/jgaa.info\/index.php\/jgaa\/article\/download\/paper636\/2322","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/jgaa.info\/index.php\/jgaa\/article\/download\/paper636\/2322","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,27]],"date-time":"2024-09-27T20:09:02Z","timestamp":1727467742000},"score":1,"resource":{"primary":{"URL":"https:\/\/jgaa.info\/index.php\/jgaa\/article\/view\/paper636"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,1]]},"references-count":0,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2023,8,1]]}},"URL":"https:\/\/doi.org\/10.7155\/jgaa.00636","relation":{},"ISSN":["1526-1719"],"issn-type":[{"type":"electronic","value":"1526-1719"}],"subject":[],"published":{"date-parts":[[2023,8,1]]}}}