Transitive-Closure Spanners: A Survey View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2010

AUTHORS

Sofya Raskhodnikova

ABSTRACT

We survey results on transitive-closure spanners and their applications. Given a directed graph G = (V,E) and an integer k ≥ 1, a k-transitive-closure-spanner (k-TC-spanner) of G is a directed graph H = (V, EH) that has (1) the same transitive-closure as G and (2) diameter at most k. These spanners were studied implicitly in different areas of computer science, and properties of these spanners have been rediscovered over the span of 20 years. The common task implicitly tackled in these diverse applications can be abstracted as the problem of constructing sparse TC-spanners.In this article, we survey combinatorial bounds on the size of sparsest TC-spanners, and algorithms and inapproximability results for the problem of computing the sparsest TC-spanner of a given directed graph. We also describe multiple applications of TC-spanners, including property testing, property reconstruction, key management in access control hierarchies and data structures. More... »

PAGES

167-196

Book

TITLE

Property Testing

ISBN

978-3-642-16366-1
978-3-642-16367-8

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-16367-8_10

DOI

http://dx.doi.org/10.1007/978-3-642-16367-8_10

DIMENSIONS

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


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": "Pennsylvania State University, USA", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "Pennsylvania State University, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Raskhodnikova", 
        "givenName": "Sofya", 
        "id": "sg:person.07502404747.45", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07502404747.45"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2010", 
    "datePublishedReg": "2010-01-01", 
    "description": "We survey results on transitive-closure spanners and their applications. Given a directed graph G\u2009=\u2009(V,E) and an integer k\u2009\u2265\u20091, a k-transitive-closure-spanner (k-TC-spanner) of G is a directed graph H\u2009=\u2009(V, EH) that has (1)\u00a0the same transitive-closure as G and (2) diameter at most\u00a0k. These spanners were studied implicitly in different areas of computer science, and properties of these spanners have been rediscovered over the span of 20 years. The common task implicitly tackled in these diverse applications can be abstracted as the problem of constructing sparse TC-spanners.In this article, we survey combinatorial bounds on the size of sparsest TC-spanners, and algorithms and inapproximability results for the problem of computing the sparsest TC-spanner of a given directed graph. We also describe multiple applications of TC-spanners, including property testing, property reconstruction, key management in access control hierarchies and data structures.", 
    "editor": [
      {
        "familyName": "Goldreich", 
        "givenName": "Oded", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-16367-8_10", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-16366-1", 
        "978-3-642-16367-8"
      ], 
      "name": "Property Testing", 
      "type": "Book"
    }, 
    "keywords": [
      "access control hierarchy", 
      "key management", 
      "data structure", 
      "computer science", 
      "common task", 
      "control hierarchy", 
      "multiple applications", 
      "inapproximability results", 
      "diverse applications", 
      "combinatorial bounds", 
      "spanners", 
      "property reconstruction", 
      "graph H", 
      "graph G", 
      "applications", 
      "algorithm", 
      "graph", 
      "task", 
      "different areas", 
      "hierarchy", 
      "problem", 
      "bounds", 
      "property testing", 
      "reconstruction", 
      "management", 
      "results", 
      "science", 
      "properties", 
      "testing", 
      "article", 
      "area", 
      "structure", 
      "size", 
      "survey", 
      "span", 
      "years", 
      "diameter"
    ], 
    "name": "Transitive-Closure Spanners: A Survey", 
    "pagination": "167-196", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1009421283"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-16367-8_10"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-16367-8_10", 
      "https://app.dimensions.ai/details/publication/pub.1009421283"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-09-02T16:13", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220902/entities/gbq_results/chapter/chapter_279.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-16367-8_10"
  }
]
 

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-16367-8_10'

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-16367-8_10'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-16367-8_10'

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-16367-8_10'


 

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

96 TRIPLES      22 PREDICATES      62 URIs      55 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-16367-8_10 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nf6245a37954f4a4498346ae720f80dd9
4 schema:datePublished 2010
5 schema:datePublishedReg 2010-01-01
6 schema:description We survey results on transitive-closure spanners and their applications. Given a directed graph G = (V,E) and an integer k ≥ 1, a k-transitive-closure-spanner (k-TC-spanner) of G is a directed graph H = (V, EH) that has (1) the same transitive-closure as G and (2) diameter at most k. These spanners were studied implicitly in different areas of computer science, and properties of these spanners have been rediscovered over the span of 20 years. The common task implicitly tackled in these diverse applications can be abstracted as the problem of constructing sparse TC-spanners.In this article, we survey combinatorial bounds on the size of sparsest TC-spanners, and algorithms and inapproximability results for the problem of computing the sparsest TC-spanner of a given directed graph. We also describe multiple applications of TC-spanners, including property testing, property reconstruction, key management in access control hierarchies and data structures.
7 schema:editor N468cb0a8951249d58f653225d26a274d
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N80a673d362fa481ca378a28ee5fc185c
11 schema:keywords access control hierarchy
12 algorithm
13 applications
14 area
15 article
16 bounds
17 combinatorial bounds
18 common task
19 computer science
20 control hierarchy
21 data structure
22 diameter
23 different areas
24 diverse applications
25 graph
26 graph G
27 graph H
28 hierarchy
29 inapproximability results
30 key management
31 management
32 multiple applications
33 problem
34 properties
35 property reconstruction
36 property testing
37 reconstruction
38 results
39 science
40 size
41 span
42 spanners
43 structure
44 survey
45 task
46 testing
47 years
48 schema:name Transitive-Closure Spanners: A Survey
49 schema:pagination 167-196
50 schema:productId N6e33c9d150484a99a206a0adba7c6ac8
51 N95bcbc03bfe34b99abd407a5ad372759
52 schema:publisher N1006e9a0a1884ef6a5c2f60ed75ce71c
53 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009421283
54 https://doi.org/10.1007/978-3-642-16367-8_10
55 schema:sdDatePublished 2022-09-02T16:13
56 schema:sdLicense https://scigraph.springernature.com/explorer/license/
57 schema:sdPublisher Nc1bd2cc8e90f430b8de4c5b264d80cb3
58 schema:url https://doi.org/10.1007/978-3-642-16367-8_10
59 sgo:license sg:explorer/license/
60 sgo:sdDataset chapters
61 rdf:type schema:Chapter
62 N1006e9a0a1884ef6a5c2f60ed75ce71c schema:name Springer Nature
63 rdf:type schema:Organisation
64 N468cb0a8951249d58f653225d26a274d rdf:first Nb8a7c0efd803408aaadcc314dd3e6761
65 rdf:rest rdf:nil
66 N6e33c9d150484a99a206a0adba7c6ac8 schema:name dimensions_id
67 schema:value pub.1009421283
68 rdf:type schema:PropertyValue
69 N80a673d362fa481ca378a28ee5fc185c schema:isbn 978-3-642-16366-1
70 978-3-642-16367-8
71 schema:name Property Testing
72 rdf:type schema:Book
73 N95bcbc03bfe34b99abd407a5ad372759 schema:name doi
74 schema:value 10.1007/978-3-642-16367-8_10
75 rdf:type schema:PropertyValue
76 Nb8a7c0efd803408aaadcc314dd3e6761 schema:familyName Goldreich
77 schema:givenName Oded
78 rdf:type schema:Person
79 Nc1bd2cc8e90f430b8de4c5b264d80cb3 schema:name Springer Nature - SN SciGraph project
80 rdf:type schema:Organization
81 Nf6245a37954f4a4498346ae720f80dd9 rdf:first sg:person.07502404747.45
82 rdf:rest rdf:nil
83 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
84 schema:name Information and Computing Sciences
85 rdf:type schema:DefinedTerm
86 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
87 schema:name Computation Theory and Mathematics
88 rdf:type schema:DefinedTerm
89 sg:person.07502404747.45 schema:affiliation grid-institutes:grid.29857.31
90 schema:familyName Raskhodnikova
91 schema:givenName Sofya
92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07502404747.45
93 rdf:type schema:Person
94 grid-institutes:grid.29857.31 schema:alternateName Pennsylvania State University, USA
95 schema:name Pennsylvania State University, USA
96 rdf:type schema:Organization
 




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


...