Additive Spanners in Nearly Quadratic Time View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2010

AUTHORS

David P. Woodruff

ABSTRACT

We consider the problem of efficiently finding an additive C-spanner of an undirected unweighted graph G, that is, a subgraph H so that for all pairs of vertices u,v, δH(u,v) ≤ δG(u,v) + C, where δ denotes shortest path distance. It is known that for every graph G, one can find an additive 6-spanner with O(n4/3) edges in O(mn2/3) time. It is unknown if there exists a constant C and an additive C-spanner with o(n4/3) edges. Moreover, for C ≤ 5 all known constructions require Ω(n3/2) edges.We give a significantly more efficient construction of an additive 6-spanner. The number of edges in our spanner is n4/3 polylog n, matching what was previously known up to a polylogarithmic factor, but we greatly improve the time for construction, from O(mn2/3) to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$n^2 {\rm polylog} \ n$\end{document}. Notice that mn2/3 ≤ n2 only if m ≤ n4/3, but in this case G itself is a sparse spanner. We thus provide both the fastest and the sparsest (up to logarithmic factors) known construction of a spanner with constant additive distortion.We give similar improvements in the construction time of additive spanners under the assumption that the input graph has large girth, or more generally, the input graph has few edges on short cycles. More... »

PAGES

463-474

Book

TITLE

Automata, Languages and Programming

ISBN

978-3-642-14164-5
978-3-642-14165-2

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-14165-2_40

DOI

http://dx.doi.org/10.1007/978-3-642-14165-2_40

DIMENSIONS

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


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: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "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": "IBM Almaden", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "IBM Almaden"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Woodruff", 
        "givenName": "David P.", 
        "id": "sg:person.012727410605.86", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012727410605.86"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2010", 
    "datePublishedReg": "2010-01-01", 
    "description": "We consider the problem of efficiently finding an additive C-spanner of an undirected unweighted graph G, that is, a subgraph H so that for all pairs of vertices u,v, \u03b4H(u,v)\u2009\u2264\u2009\u03b4G(u,v)\u2009+\u2009C, where \u03b4 denotes shortest path distance. It is known that for every graph G, one can find an additive 6-spanner with O(n4/3) edges in O(mn2/3) time. It is unknown if there exists a constant C and an additive C-spanner with o(n4/3) edges. Moreover, for C\u2009\u2264\u20095 all known constructions require \u03a9(n3/2) edges.We give a significantly more efficient construction of an additive 6-spanner. The number of edges in our spanner is n4/3 polylog n, matching what was previously known up to a polylogarithmic factor, but we greatly improve the time for construction, from O(mn2/3) to \\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}$n^2 {\\rm polylog} \\ n$\\end{document}. Notice that mn2/3\u2009\u2264\u2009n2 only if m\u2009\u2264\u2009n4/3, but in this case G itself is a sparse spanner. We thus provide both the fastest and the sparsest (up to logarithmic factors) known construction of a spanner with constant additive distortion.We give similar improvements in the construction time of additive spanners under the assumption that the input graph has large girth, or more generally, the input graph has few edges on short cycles.", 
    "editor": [
      {
        "familyName": "Abramsky", 
        "givenName": "Samson", 
        "type": "Person"
      }, 
      {
        "familyName": "Gavoille", 
        "givenName": "Cyril", 
        "type": "Person"
      }, 
      {
        "familyName": "Kirchner", 
        "givenName": "Claude", 
        "type": "Person"
      }, 
      {
        "familyName": "Meyer auf der Heide", 
        "givenName": "Friedhelm", 
        "type": "Person"
      }, 
      {
        "familyName": "Spirakis", 
        "givenName": "Paul G.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-14165-2_40", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-14164-5", 
        "978-3-642-14165-2"
      ], 
      "name": "Automata, Languages and Programming", 
      "type": "Book"
    }, 
    "keywords": [
      "graph G", 
      "input graph", 
      "c-spanner", 
      "shortest path distance", 
      "number of edges", 
      "case G", 
      "subgraph H", 
      "polylogarithmic factors", 
      "sparse spanners", 
      "additive spanners", 
      "large girth", 
      "quadratic time", 
      "vertices u", 
      "path distance", 
      "additive distortion", 
      "graph", 
      "unweighted graph G", 
      "spanners", 
      "edge", 
      "efficient construction", 
      "polylog", 
      "n4/3", 
      "short cycles", 
      "problem", 
      "construction", 
      "construction time", 
      "assumption", 
      "distance", 
      "time", 
      "distortion", 
      "pairs", 
      "number", 
      "girth", 
      "improvement", 
      "N2", 
      "similar improvements", 
      "factors", 
      "cycle"
    ], 
    "name": "Additive Spanners in Nearly Quadratic Time", 
    "pagination": "463-474", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1031433870"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-14165-2_40"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-14165-2_40", 
      "https://app.dimensions.ai/details/publication/pub.1031433870"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-12-01T06:55", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221201/entities/gbq_results/chapter/chapter_8.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-14165-2_40"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

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-642-14165-2_40'

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-642-14165-2_40'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-14165-2_40'

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-642-14165-2_40'


 

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

117 TRIPLES      22 PREDICATES      63 URIs      56 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-14165-2_40 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nc09d99bc6f414b04be57913d26ed70a8
4 schema:datePublished 2010
5 schema:datePublishedReg 2010-01-01
6 schema:description We consider the problem of efficiently finding an additive C-spanner of an undirected unweighted graph G, that is, a subgraph H so that for all pairs of vertices u,v, δH(u,v) ≤ δG(u,v) + C, where δ denotes shortest path distance. It is known that for every graph G, one can find an additive 6-spanner with O(n4/3) edges in O(mn2/3) time. It is unknown if there exists a constant C and an additive C-spanner with o(n4/3) edges. Moreover, for C ≤ 5 all known constructions require Ω(n3/2) edges.We give a significantly more efficient construction of an additive 6-spanner. The number of edges in our spanner is n4/3 polylog n, matching what was previously known up to a polylogarithmic factor, but we greatly improve the time for construction, from O(mn2/3) to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$n^2 {\rm polylog} \ n$\end{document}. Notice that mn2/3 ≤ n2 only if m ≤ n4/3, but in this case G itself is a sparse spanner. We thus provide both the fastest and the sparsest (up to logarithmic factors) known construction of a spanner with constant additive distortion.We give similar improvements in the construction time of additive spanners under the assumption that the input graph has large girth, or more generally, the input graph has few edges on short cycles.
7 schema:editor N63d15ee3386c4379ac4558f2c8290d46
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf Naf1cfb1b4f3346c889e8dcaea57bd303
11 schema:keywords N2
12 additive distortion
13 additive spanners
14 assumption
15 c-spanner
16 case G
17 construction
18 construction time
19 cycle
20 distance
21 distortion
22 edge
23 efficient construction
24 factors
25 girth
26 graph
27 graph G
28 improvement
29 input graph
30 large girth
31 n4/3
32 number
33 number of edges
34 pairs
35 path distance
36 polylog
37 polylogarithmic factors
38 problem
39 quadratic time
40 short cycles
41 shortest path distance
42 similar improvements
43 spanners
44 sparse spanners
45 subgraph H
46 time
47 unweighted graph G
48 vertices u
49 schema:name Additive Spanners in Nearly Quadratic Time
50 schema:pagination 463-474
51 schema:productId N22b9f28c2f48482cb6b8bda7f09a6e3a
52 Na314151e7f4e4e5c8dfa7a5398a48bef
53 schema:publisher N30296ef7ef7f41b2b1f74a1baf174d17
54 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031433870
55 https://doi.org/10.1007/978-3-642-14165-2_40
56 schema:sdDatePublished 2022-12-01T06:55
57 schema:sdLicense https://scigraph.springernature.com/explorer/license/
58 schema:sdPublisher N5d51dea024b741d2b42df9b0965d77b0
59 schema:url https://doi.org/10.1007/978-3-642-14165-2_40
60 sgo:license sg:explorer/license/
61 sgo:sdDataset chapters
62 rdf:type schema:Chapter
63 N0135dce3a9e542f3bc219884aa40610d rdf:first Nd4562af411fc41aaa23ae65be42560d8
64 rdf:rest rdf:nil
65 N13284033e12344d2824d9980eed1b71f schema:familyName Abramsky
66 schema:givenName Samson
67 rdf:type schema:Person
68 N22b9f28c2f48482cb6b8bda7f09a6e3a schema:name doi
69 schema:value 10.1007/978-3-642-14165-2_40
70 rdf:type schema:PropertyValue
71 N2555e0f10f834decac30ceaefa494488 rdf:first Na81261b3ff9d4cf5aaf57069960cf3ad
72 rdf:rest N0135dce3a9e542f3bc219884aa40610d
73 N2bc19ea7d3f544859b3043151c7a93b2 schema:familyName Kirchner
74 schema:givenName Claude
75 rdf:type schema:Person
76 N30296ef7ef7f41b2b1f74a1baf174d17 schema:name Springer Nature
77 rdf:type schema:Organisation
78 N3efd14623ef541b79d07eaed8a82af8a rdf:first N2bc19ea7d3f544859b3043151c7a93b2
79 rdf:rest N2555e0f10f834decac30ceaefa494488
80 N5382038e6211433db1e3ad02f144dc1c rdf:first Nf7b5bb67ce77497cba96399b59b5ad32
81 rdf:rest N3efd14623ef541b79d07eaed8a82af8a
82 N5d51dea024b741d2b42df9b0965d77b0 schema:name Springer Nature - SN SciGraph project
83 rdf:type schema:Organization
84 N63d15ee3386c4379ac4558f2c8290d46 rdf:first N13284033e12344d2824d9980eed1b71f
85 rdf:rest N5382038e6211433db1e3ad02f144dc1c
86 Na314151e7f4e4e5c8dfa7a5398a48bef schema:name dimensions_id
87 schema:value pub.1031433870
88 rdf:type schema:PropertyValue
89 Na81261b3ff9d4cf5aaf57069960cf3ad schema:familyName Meyer auf der Heide
90 schema:givenName Friedhelm
91 rdf:type schema:Person
92 Naf1cfb1b4f3346c889e8dcaea57bd303 schema:isbn 978-3-642-14164-5
93 978-3-642-14165-2
94 schema:name Automata, Languages and Programming
95 rdf:type schema:Book
96 Nc09d99bc6f414b04be57913d26ed70a8 rdf:first sg:person.012727410605.86
97 rdf:rest rdf:nil
98 Nd4562af411fc41aaa23ae65be42560d8 schema:familyName Spirakis
99 schema:givenName Paul G.
100 rdf:type schema:Person
101 Nf7b5bb67ce77497cba96399b59b5ad32 schema:familyName Gavoille
102 schema:givenName Cyril
103 rdf:type schema:Person
104 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
105 schema:name Information and Computing Sciences
106 rdf:type schema:DefinedTerm
107 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
108 schema:name Computation Theory and Mathematics
109 rdf:type schema:DefinedTerm
110 sg:person.012727410605.86 schema:affiliation grid-institutes:None
111 schema:familyName Woodruff
112 schema:givenName David P.
113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012727410605.86
114 rdf:type schema:Person
115 grid-institutes:None schema:alternateName IBM Almaden
116 schema:name IBM Almaden
117 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...