# Exact Distance Labelings Yield Additive-Stretch Compact Routing Schemes

Ontology type: schema:Chapter

### Chapter Info

DATE

2006

AUTHORS ABSTRACT

Distance labelings and compact routing schemes have both been active areas of recent research. It was already known that graphs with constant-sized recursive separators, such as trees, outerplanar graphs, series-parallel graphs and graphs of bounded treewidth, support both exact distance labelings and optimal (additive stretch 0, multiplicative stretch 1) compact routing schemes, but there are many classes of graphs known to admit exact distance labelings that do not have constant-sized separators. Our main result is to demonstrate that every unweighted, undirected n-vertex graph which supports an exact distance labeling with l(n)-sized labels also supports a compact routing scheme with O(l(n) + log2n/loglogn)-sized headers, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O(\sqrt{n}(l(n) + \log^2{n}/\log{\log{n}}))$\end{document}-sized routing tables, and an additive stretch of 6.We then investigate two classes of graphs which support exact distance labelings (but do not guarantee constant-sized separators), where we can improve substantially on our general result. In the case of interval graphs, we present a compact routing scheme with O(logn)-sized headers, O(logn)-sized routing tables and additive stretch 1, improving headers and table sizes from a result of [1], which uses O(log3n/loglogn)-bit headers and tables. We also present a compact routing scheme for the related family of circular arc graphs which guarantees O(log2n)-sized headers, O(logn)-sized routing tables and an additive stretch of 1. More... »

PAGES

339-354

### Book

TITLE

Distributed Computing

ISBN

978-3-540-44624-8
978-3-540-44627-9

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11864219_24

DOI

http://dx.doi.org/10.1007/11864219_24

DIMENSIONS

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

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/10",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Technology",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1005",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Communications Technologies",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Department of Computer Science, Tufts University, Medford, MA, USA",
"id": "http://www.grid.ac/institutes/grid.429997.8",
"name": [
"Department of Computer Science, Tufts University, Medford, MA, USA"
],
"type": "Organization"
},
"givenName": "Arthur",
"id": "sg:person.01025032714.70",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01025032714.70"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Computer Science, Tufts University, Medford, MA, USA",
"id": "http://www.grid.ac/institutes/grid.429997.8",
"name": [
"Department of Computer Science, Tufts University, Medford, MA, USA"
],
"type": "Organization"
},
"familyName": "Cowen",
"givenName": "Lenore",
"id": "sg:person.01106351776.04",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01106351776.04"
],
"type": "Person"
}
],
"datePublished": "2006",
"datePublishedReg": "2006-01-01",
"description": "Distance labelings and compact routing schemes have both been active areas of recent research. It was already known that graphs with constant-sized recursive separators, such as trees, outerplanar graphs, series-parallel graphs and graphs of bounded treewidth, support both exact distance labelings and optimal (additive stretch 0, multiplicative stretch 1) compact routing schemes, but there are many classes of graphs known to admit exact distance labelings that do not have constant-sized separators. Our main result is to demonstrate that every unweighted, undirected n-vertex graph which supports an exact distance labeling with l(n)-sized labels also supports a compact routing scheme with O(l(n) + log2n/loglogn)-sized headers, \\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}$O(\\sqrt{n}(l(n) + \\log^2{n}/\\log{\\log{n}}))$\\end{document}-sized routing tables, and an additive stretch of 6.We then investigate two classes of graphs which support exact distance labelings (but do not guarantee constant-sized separators), where we can improve substantially on our general result. In the case of interval graphs, we present a compact routing scheme with O(logn)-sized headers, O(logn)-sized routing tables and additive stretch 1, improving headers and table sizes from a result of [1], which uses O(log3n/loglogn)-bit headers and tables. We also present a compact routing scheme for the related family of circular arc graphs which guarantees O(log2n)-sized headers, O(logn)-sized routing tables and an additive stretch of 1.",
"editor": [
{
"familyName": "Dolev",
"givenName": "Shlomi",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/11864219_24",
"inLanguage": "en",
"isAccessibleForFree": false,
"isPartOf": {
"isbn": [
"978-3-540-44624-8",
"978-3-540-44627-9"
],
"name": "Distributed Computing",
"type": "Book"
},
"keywords": [
"routing scheme",
"routing tables",
"distance labeling",
"compact routing scheme",
"series-parallel graphs",
"class of graphs",
"table size",
"graph",
"interval graphs",
"scheme",
"outerplanar graphs",
"labeling",
"vertex graph",
"table",
"stretch 1",
"treewidth",
"active area",
"recent research",
"main results",
"labels",
"trees",
"class",
"results",
"stretch",
"cases",
"related families",
"family",
"area",
"research",
"size",
"general results",
"separator",
"circular",
],
"name": "Exact Distance Labelings Yield Additive-Stretch Compact Routing Schemes",
"pagination": "339-354",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1052251884"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/11864219_24"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/11864219_24",
"https://app.dimensions.ai/details/publication/pub.1052251884"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-06-01T22:28",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220601/entities/gbq_results/chapter/chapter_162.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/11864219_24"
}
]

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/11864219_24'

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/11864219_24'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11864219_24'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11864219_24'

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

103 TRIPLES      23 PREDICATES      62 URIs      55 LITERALS      7 BLANK NODES

Subject Predicate Object
2 anzsrc-for:1005
3 schema:author N28b995d793e14368b9a20e0c8e9dea1b
4 schema:datePublished 2006
5 schema:datePublishedReg 2006-01-01
6 schema:description Distance labelings and compact routing schemes have both been active areas of recent research. It was already known that graphs with constant-sized recursive separators, such as trees, outerplanar graphs, series-parallel graphs and graphs of bounded treewidth, support both exact distance labelings and optimal (additive stretch 0, multiplicative stretch 1) compact routing schemes, but there are many classes of graphs known to admit exact distance labelings that do not have constant-sized separators. Our main result is to demonstrate that every unweighted, undirected n-vertex graph which supports an exact distance labeling with l(n)-sized labels also supports a compact routing scheme with O(l(n) + log2n/loglogn)-sized headers, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O(\sqrt{n}(l(n) + \log^2{n}/\log{\log{n}}))$\end{document}-sized routing tables, and an additive stretch of 6.We then investigate two classes of graphs which support exact distance labelings (but do not guarantee constant-sized separators), where we can improve substantially on our general result. In the case of interval graphs, we present a compact routing scheme with O(logn)-sized headers, O(logn)-sized routing tables and additive stretch 1, improving headers and table sizes from a result of [1], which uses O(log3n/loglogn)-bit headers and tables. We also present a compact routing scheme for the related family of circular arc graphs which guarantees O(log2n)-sized headers, O(logn)-sized routing tables and an additive stretch of 1.
7 schema:editor Nda92b3b71bb8402982ae193a2a6ea326
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nf758b8d796e1498289f221520e2495b2
12 schema:keywords active area
14 area
16 cases
17 circular
18 class
19 class of graphs
20 compact routing scheme
21 distance labeling
22 family
23 general results
24 graph
26 interval graphs
27 labeling
28 labels
29 main results
30 outerplanar graphs
31 recent research
32 related families
33 research
34 results
35 routing scheme
36 routing tables
37 scheme
38 separator
39 series-parallel graphs
40 size
41 stretch
42 stretch 1
43 table
44 table size
45 trees
46 treewidth
47 vertex graph
48 schema:name Exact Distance Labelings Yield Additive-Stretch Compact Routing Schemes
49 schema:pagination 339-354
50 schema:productId N56accd171e6d463ea8c312d880ac442f
51 Nf3294a07137946479b8b86e81f39fc30
52 schema:publisher N683b15858a6745c1953758519ca11be4
53 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052251884
54 https://doi.org/10.1007/11864219_24
55 schema:sdDatePublished 2022-06-01T22:28
57 schema:sdPublisher Nbc28143dc2dd4f4393363b9a1edc7739
58 schema:url https://doi.org/10.1007/11864219_24
60 sgo:sdDataset chapters
61 rdf:type schema:Chapter
62 N1809ce63920146178ab35e1e757185e5 rdf:first sg:person.01106351776.04
63 rdf:rest rdf:nil
65 schema:givenName Shlomi
66 rdf:type schema:Person
67 N28b995d793e14368b9a20e0c8e9dea1b rdf:first sg:person.01025032714.70
68 rdf:rest N1809ce63920146178ab35e1e757185e5
69 N56accd171e6d463ea8c312d880ac442f schema:name dimensions_id
70 schema:value pub.1052251884
71 rdf:type schema:PropertyValue
72 N683b15858a6745c1953758519ca11be4 schema:name Springer Nature
73 rdf:type schema:Organisation
74 Nbc28143dc2dd4f4393363b9a1edc7739 schema:name Springer Nature - SN SciGraph project
75 rdf:type schema:Organization
77 rdf:rest rdf:nil
78 Nf3294a07137946479b8b86e81f39fc30 schema:name doi
79 schema:value 10.1007/11864219_24
80 rdf:type schema:PropertyValue
81 Nf758b8d796e1498289f221520e2495b2 schema:isbn 978-3-540-44624-8
82 978-3-540-44627-9
83 schema:name Distributed Computing
84 rdf:type schema:Book
85 anzsrc-for:10 schema:inDefinedTermSet anzsrc-for:
86 schema:name Technology
87 rdf:type schema:DefinedTerm
88 anzsrc-for:1005 schema:inDefinedTermSet anzsrc-for:
89 schema:name Communications Technologies
90 rdf:type schema:DefinedTerm
91 sg:person.01025032714.70 schema:affiliation grid-institutes:grid.429997.8
93 schema:givenName Arthur
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01025032714.70
95 rdf:type schema:Person
96 sg:person.01106351776.04 schema:affiliation grid-institutes:grid.429997.8
97 schema:familyName Cowen
98 schema:givenName Lenore
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01106351776.04
100 rdf:type schema:Person
101 grid-institutes:grid.429997.8 schema:alternateName Department of Computer Science, Tufts University, Medford, MA, USA
102 schema:name Department of Computer Science, Tufts University, Medford, MA, USA
103 rdf:type schema:Organization