# Faster Approximation of Distances in Graphs

Ontology type: schema:Chapter

### Chapter Info

DATE

2007-01-01

AUTHORS ABSTRACT

Let G = (V,E) be a weighted undirected graph on n vertices and m edges, and let dG be its shortest path metric. We present two simple deterministic algorithms for approximating all-pairs shortest paths in G. Our first algorithm runs in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\tilde{O}(n^2)$\end{document} time, and for any u,v ∈ V reports distance no greater than 2dG(u,v) + h(u,v). Here, h(u,v) is the largest edge weight on a shortest path between u and v. The previous algorithm, due to Baswana and Kavitha that achieved the same result was randomized. Our second algorithm for the all-pairs shortest path problem uses Boolean matrix multiplications and for any u,v ∈ V reports distance no greater than (1 + ε)dG(u,v) + 2h(u,v). The currently best known algorithm for Boolean matrix multiplication yields an O(n2.24 + o(1)ε− 3log(nε− 1)) time bound for this algorithm. The previously best known result of Elkin with a similar multiplicative factor had a much bigger additive error term.We also consider approximating the diameter and the radius of a graph. For the problem of estimating the radius, we present an almost 3/2-approximation algorithm which runs in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\tilde{O}(m\sqrt{n}+n^2)$\end{document} time. Aingworth, Chekuri, Indyk, and Motwani used a similar approach and obtained analogous results for the diameter approximation problem. Additionally, we show that if the graph has a small separator decomposition a 3/2-approximation of both the diameter and the radius can be obtained more efficiently. More... »

PAGES

541-552

### Book

TITLE

Algorithms and Data Structures

ISBN

978-3-540-73948-7
978-3-540-73951-7

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-73951-7_47

DOI

http://dx.doi.org/10.1007/978-3-540-73951-7_47

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1019791169

Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Information and Computing Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Computation Theory and Mathematics",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Computer Science and Engineering, Pennsylvania State University",
"id": "http://www.grid.ac/institutes/grid.29857.31",
"name": [
"Computer Science and Engineering, Pennsylvania State University"
],
"type": "Organization"
},
"familyName": "Berman",
"givenName": "Piotr",
"id": "sg:person.01274506210.27",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Computer Science and Engineering, Pennsylvania State University",
"id": "http://www.grid.ac/institutes/grid.29857.31",
"name": [
"Computer Science and Engineering, Pennsylvania State University"
],
"type": "Organization"
},
"familyName": "Kasiviswanathan",
"id": "sg:person.014625303707.58",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014625303707.58"
],
"type": "Person"
}
],
"datePublished": "2007-01-01",
"datePublishedReg": "2007-01-01",
"description": "Let G\u2009=\u2009(V,E) be a weighted undirected graph on n vertices and m edges, and let dG be its shortest path metric. We present two simple deterministic algorithms for approximating all-pairs shortest paths in G. Our first algorithm runs in \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\tilde{O}(n^2)$\\end{document} time, and for any u,v\u2009\u2208\u2009V reports distance no greater than 2dG(u,v)\u2009+\u2009h(u,v). Here, h(u,v) is the largest edge weight on a shortest path between u and v. The previous algorithm, due to Baswana and Kavitha that achieved the same result was randomized. Our second algorithm for the all-pairs shortest path problem uses Boolean matrix multiplications and for any u,v\u2009\u2208\u2009V reports distance no greater than (1\u2009+\u2009\u03b5)dG(u,v)\u2009+\u20092h(u,v). The currently best known algorithm for Boolean matrix multiplication yields an O(n2.24\u2009+\u2009o(1)\u03b5\u2212\u20093log(n\u03b5\u2212\u20091)) time bound for this algorithm. The previously best known result of Elkin with a similar multiplicative factor had a much bigger additive error term.We also consider approximating the diameter and the radius of a graph. For the problem of estimating the radius, we present an almost 3/2-approximation algorithm which runs in \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\tilde{O}(m\\sqrt{n}+n^2)$\\end{document} time. Aingworth, Chekuri, Indyk, and Motwani used a similar approach and obtained analogous results for the diameter approximation problem. Additionally, we show that if the graph has a small separator decomposition a 3/2-approximation of both the diameter and the radius can be obtained more efficiently.",
"editor": [
{
"familyName": "Dehne",
"givenName": "Frank",
"type": "Person"
},
{
"familyName": "Sack",
"givenName": "J\u00f6rg-R\u00fcdiger",
"type": "Person"
},
{
"familyName": "Zeh",
"givenName": "Norbert",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-540-73951-7_47",
"isAccessibleForFree": false,
"isPartOf": {
"isbn": [
"978-3-540-73948-7",
"978-3-540-73951-7"
],
"name": "Algorithms and Data Structures",
"type": "Book"
},
"keywords": [
"Boolean matrix multiplication",
"matrix multiplication",
"shortest path metric",
"largest edge weight",
"pairs shortest path problem",
"shortest path problem",
"pairs shortest paths",
"shortest path",
"weighted undirected graph",
"approximation problem",
"separator decomposition",
"fast approximation",
"undirected graph",
"n vertices",
"edge weights",
"path problem",
"error term",
"simple deterministic algorithm",
"deterministic algorithm",
"second algorithm",
"analogous results",
"graph",
"first algorithm",
"multiplicative factor",
"path metric",
"previous algorithms",
"algorithm",
"problem",
"approximation",
"same results",
"Motwani",
"vertices",
"Kavitha",
"multiplication",
"Indyk",
"similar approach",
"Chekuri",
"path",
"Baswana",
"edge",
"metrics",
"results",
"decomposition",
"terms",
"time",
"Elkins",
"approach",
"distance",
"diameter",
"weight",
"factors",
"report"
],
"name": "Faster Approximation of Distances in Graphs",
"pagination": "541-552",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1019791169"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-540-73951-7_47"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-540-73951-7_47",
"https://app.dimensions.ai/details/publication/pub.1019791169"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-08-04T17:21",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220804/entities/gbq_results/chapter/chapter_388.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-540-73951-7_47"
}
]

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-73951-7_47'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-73951-7_47'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-73951-7_47'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-73951-7_47'

This table displays all metadata directly associated to this object as RDF triples.

130 TRIPLES      22 PREDICATES      78 URIs      71 LITERALS      7 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0802
3 schema:author N2a971100a6c64f5988678f79f99cb1d4
4 schema:datePublished 2007-01-01
5 schema:datePublishedReg 2007-01-01
6 schema:description Let G = (V,E) be a weighted undirected graph on n vertices and m edges, and let dG be its shortest path metric. We present two simple deterministic algorithms for approximating all-pairs shortest paths in G. Our first algorithm runs in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\tilde{O}(n^2)$\end{document} time, and for any u,v ∈ V reports distance no greater than 2dG(u,v) + h(u,v). Here, h(u,v) is the largest edge weight on a shortest path between u and v. The previous algorithm, due to Baswana and Kavitha that achieved the same result was randomized. Our second algorithm for the all-pairs shortest path problem uses Boolean matrix multiplications and for any u,v ∈ V reports distance no greater than (1 + ε)dG(u,v) + 2h(u,v). The currently best known algorithm for Boolean matrix multiplication yields an O(n2.24 + o(1)ε− 3log(nε− 1)) time bound for this algorithm. The previously best known result of Elkin with a similar multiplicative factor had a much bigger additive error term.We also consider approximating the diameter and the radius of a graph. For the problem of estimating the radius, we present an almost 3/2-approximation algorithm which runs in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\tilde{O}(m\sqrt{n}+n^2)$\end{document} time. Aingworth, Chekuri, Indyk, and Motwani used a similar approach and obtained analogous results for the diameter approximation problem. Additionally, we show that if the graph has a small separator decomposition a 3/2-approximation of both the diameter and the radius can be obtained more efficiently.
7 schema:editor Nf4dd8e8083ab4a37b801a49309fe38d3
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N8a6c09a0e186487e98a5a004e9dbfa1d
11 schema:keywords Baswana
12 Boolean matrix multiplication
13 Chekuri
14 Elkins
15 Indyk
16 Kavitha
17 Motwani
19 algorithm
20 analogous results
21 approach
22 approximation
23 approximation problem
24 decomposition
25 deterministic algorithm
26 diameter
27 distance
28 edge
29 edge weights
30 error term
31 factors
32 fast approximation
33 first algorithm
34 graph
35 largest edge weight
36 matrix multiplication
37 metrics
38 multiplication
39 multiplicative factor
40 n vertices
41 pairs shortest path problem
42 pairs shortest paths
43 path
44 path metric
45 path problem
46 previous algorithms
47 problem
49 report
50 results
51 same results
52 second algorithm
53 separator decomposition
54 shortest path
55 shortest path metric
56 shortest path problem
57 similar approach
58 simple deterministic algorithm
59 terms
60 time
61 undirected graph
62 vertices
63 weight
64 weighted undirected graph
65 schema:name Faster Approximation of Distances in Graphs
66 schema:pagination 541-552
67 schema:productId N6a5f46cfe369411cba7de738c081be25
68 Nb004b3f7359446d4830d2a391d552a33
69 schema:publisher N7dd0dcfc63124d82a78e443d3cf653f4
70 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019791169
71 https://doi.org/10.1007/978-3-540-73951-7_47
72 schema:sdDatePublished 2022-08-04T17:21
74 schema:sdPublisher N3b71802df3414091a3492df90281798c
75 schema:url https://doi.org/10.1007/978-3-540-73951-7_47
77 sgo:sdDataset chapters
78 rdf:type schema:Chapter
79 N0f8b217595c74475a81a455356838409 rdf:first N4847689c5c284777b0e5e82dbbb00b3d
80 rdf:rest rdf:nil
81 N1f15dbec2b2347a4984efb3ac6186ffc schema:familyName Dehne
82 schema:givenName Frank
83 rdf:type schema:Person
84 N2a971100a6c64f5988678f79f99cb1d4 rdf:first sg:person.01274506210.27
85 rdf:rest Nf5163dede4444bdc9e0dd0b08ca038c2
86 N3b71802df3414091a3492df90281798c schema:name Springer Nature - SN SciGraph project
87 rdf:type schema:Organization
88 N4847689c5c284777b0e5e82dbbb00b3d schema:familyName Zeh
89 schema:givenName Norbert
90 rdf:type schema:Person
91 N6a5f46cfe369411cba7de738c081be25 schema:name dimensions_id
92 schema:value pub.1019791169
93 rdf:type schema:PropertyValue
94 N7dd0dcfc63124d82a78e443d3cf653f4 schema:name Springer Nature
95 rdf:type schema:Organisation
96 N7f5b7ebcebd343a4b78511a801610caf schema:familyName Sack
97 schema:givenName Jörg-Rüdiger
98 rdf:type schema:Person
99 N8a6c09a0e186487e98a5a004e9dbfa1d schema:isbn 978-3-540-73948-7
100 978-3-540-73951-7
101 schema:name Algorithms and Data Structures
102 rdf:type schema:Book
103 Nb004b3f7359446d4830d2a391d552a33 schema:name doi
104 schema:value 10.1007/978-3-540-73951-7_47
105 rdf:type schema:PropertyValue
106 Nd5ee3d47dfe04bc8affa071bf3d845bc rdf:first N7f5b7ebcebd343a4b78511a801610caf
107 rdf:rest N0f8b217595c74475a81a455356838409
108 Nf4dd8e8083ab4a37b801a49309fe38d3 rdf:first N1f15dbec2b2347a4984efb3ac6186ffc
109 rdf:rest Nd5ee3d47dfe04bc8affa071bf3d845bc
110 Nf5163dede4444bdc9e0dd0b08ca038c2 rdf:first sg:person.014625303707.58
111 rdf:rest rdf:nil
112 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
113 schema:name Information and Computing Sciences
114 rdf:type schema:DefinedTerm
115 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
116 schema:name Computation Theory and Mathematics
117 rdf:type schema:DefinedTerm
118 sg:person.01274506210.27 schema:affiliation grid-institutes:grid.29857.31
119 schema:familyName Berman
120 schema:givenName Piotr
121 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27
122 rdf:type schema:Person
123 sg:person.014625303707.58 schema:affiliation grid-institutes:grid.29857.31
124 schema:familyName Kasiviswanathan
126 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014625303707.58
127 rdf:type schema:Person
128 grid-institutes:grid.29857.31 schema:alternateName Computer Science and Engineering, Pennsylvania State University
129 schema:name Computer Science and Engineering, Pennsylvania State University
130 rdf:type schema:Organization