Steiner Transitive-Closure Spanners of Low-Dimensional Posets View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2011

AUTHORS

Piotr Berman , Arnab Bhattacharyya , Elena Grigorescu , Sofya Raskhodnikova , David P. Woodruff , Grigory Yaroslavtsev

ABSTRACT

Given a directed graph G = (V,E) and an integer k ≥ 1, a Steiner k-transitive-closure-spanner (Steiner k-TC-spanner) of G is a directed graph H = (VH, EH) such that (1) V ⊆ VH and (2) for all vertices v,u ∈ V, the distance from v to u in H is at most k if u is reachable from v in G, and ∞ otherwise. Motivated by applications to property reconstruction and access control hierarchies, we concentrate on Steiner TC-spanners of directed acyclic graphs or, equivalently, partially ordered sets. We study the relationship between the dimension of a poset and the size, denoted Sk, of its sparsest Steiner k-TC-spanner.We present a nearly tight lower bound on S2 for d-dimensional directed hypergrids. Our bound is derived from an explicit dual solution to a linear programming relaxation of the 2-TC-spanner problem. We also give an efficient construction of Steiner 2-TC-spanners, of size matching the lower bound, for all low-dimensional posets. Finally, we present a nearly tight lower bound on Sk for d-dimensional posets. More... »

PAGES

760-772

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-22006-7_64

DOI

http://dx.doi.org/10.1007/978-3-642-22006-7_64

DIMENSIONS

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


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/0806", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information Systems", 
        "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": "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": "Massachusetts Institute of Technology, USA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "Massachusetts Institute of Technology, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Bhattacharyya", 
        "givenName": "Arnab", 
        "id": "sg:person.012357145015.18", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012357145015.18"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Georgia Institute of Technology, USA", 
          "id": "http://www.grid.ac/institutes/grid.213917.f", 
          "name": [
            "Georgia Institute of Technology, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Grigorescu", 
        "givenName": "Elena", 
        "id": "sg:person.014612515147.15", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014612515147.15"
        ], 
        "type": "Person"
      }, 
      {
        "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"
      }, 
      {
        "affiliation": {
          "alternateName": "IBM Almaden Research Center, USA", 
          "id": "http://www.grid.ac/institutes/grid.481551.c", 
          "name": [
            "IBM Almaden Research Center, USA"
          ], 
          "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"
      }, 
      {
        "affiliation": {
          "alternateName": "Pennsylvania State University, USA", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "Pennsylvania State University, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Yaroslavtsev", 
        "givenName": "Grigory", 
        "id": "sg:person.015277345473.26", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015277345473.26"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2011", 
    "datePublishedReg": "2011-01-01", 
    "description": "Given a directed graph G\u2009=\u2009(V,E) and an integer k\u2009\u2265\u20091, a Steiner k-transitive-closure-spanner (Steiner k-TC-spanner) of G is a directed graph H\u2009=\u2009(VH, EH) such that (1)\u00a0V\u2009\u2286\u2009VH and (2)\u00a0for all vertices v,u\u2009\u2208\u2009V, the distance from v to u in H is at most\u00a0k if u is reachable from v in G, and \u221e otherwise. Motivated by applications to property reconstruction and access control hierarchies, we concentrate on Steiner TC-spanners of directed acyclic graphs or, equivalently, partially ordered sets. We study the relationship between the dimension of a poset and the size, denoted Sk, of its sparsest Steiner k-TC-spanner.We present a nearly tight lower bound on S2 for d-dimensional directed hypergrids. Our bound is derived from an explicit dual solution to a linear programming relaxation of the 2-TC-spanner problem. We also give an efficient construction of Steiner 2-TC-spanners, of size matching the lower bound, for all low-dimensional posets. Finally, we present a nearly tight lower bound on Sk for d-dimensional posets.", 
    "editor": [
      {
        "familyName": "Aceto", 
        "givenName": "Luca", 
        "type": "Person"
      }, 
      {
        "familyName": "Henzinger", 
        "givenName": "Monika", 
        "type": "Person"
      }, 
      {
        "familyName": "Sgall", 
        "givenName": "Ji\u0159\u00ed", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-22006-7_64", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-22005-0", 
        "978-3-642-22006-7"
      ], 
      "name": "Automata, Languages and Programming", 
      "type": "Book"
    }, 
    "keywords": [
      "explicit dual solutions", 
      "linear programming relaxation", 
      "access control hierarchy", 
      "dual solutions", 
      "programming relaxation", 
      "property reconstruction", 
      "graph H", 
      "dimensional poset", 
      "graph G", 
      "posets", 
      "vertex v", 
      "acyclic graph", 
      "control hierarchy", 
      "efficient construction", 
      "graph", 
      "spanners", 
      "hypergrid", 
      "problem", 
      "solution", 
      "set", 
      "relaxation", 
      "dimensions", 
      "applications", 
      "hierarchy", 
      "distance", 
      "size", 
      "Steiner", 
      "construction", 
      "SK", 
      "reconstruction", 
      "S2", 
      "relationship", 
      "VH"
    ], 
    "name": "Steiner Transitive-Closure Spanners of Low-Dimensional Posets", 
    "pagination": "760-772", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1018924561"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-22006-7_64"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-22006-7_64", 
      "https://app.dimensions.ai/details/publication/pub.1018924561"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-08-04T17:18", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220804/entities/gbq_results/chapter/chapter_350.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-22006-7_64"
  }
]
 

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-22006-7_64'

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-22006-7_64'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-22006-7_64'

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-22006-7_64'


 

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

146 TRIPLES      22 PREDICATES      58 URIs      51 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-22006-7_64 schema:about anzsrc-for:08
2 anzsrc-for:0806
3 schema:author Nc22ce443fec94ef1b5eb919d41396e11
4 schema:datePublished 2011
5 schema:datePublishedReg 2011-01-01
6 schema:description Given a directed graph G = (V,E) and an integer k ≥ 1, a Steiner k-transitive-closure-spanner (Steiner k-TC-spanner) of G is a directed graph H = (VH, EH) such that (1) V ⊆ VH and (2) for all vertices v,u ∈ V, the distance from v to u in H is at most k if u is reachable from v in G, and ∞ otherwise. Motivated by applications to property reconstruction and access control hierarchies, we concentrate on Steiner TC-spanners of directed acyclic graphs or, equivalently, partially ordered sets. We study the relationship between the dimension of a poset and the size, denoted Sk, of its sparsest Steiner k-TC-spanner.We present a nearly tight lower bound on S2 for d-dimensional directed hypergrids. Our bound is derived from an explicit dual solution to a linear programming relaxation of the 2-TC-spanner problem. We also give an efficient construction of Steiner 2-TC-spanners, of size matching the lower bound, for all low-dimensional posets. Finally, we present a nearly tight lower bound on Sk for d-dimensional posets.
7 schema:editor N9970e2476f5242e782198e78a904b536
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf Nd16f46a7c7594545803815302b7f24b8
11 schema:keywords S2
12 SK
13 Steiner
14 VH
15 access control hierarchy
16 acyclic graph
17 applications
18 construction
19 control hierarchy
20 dimensional poset
21 dimensions
22 distance
23 dual solutions
24 efficient construction
25 explicit dual solutions
26 graph
27 graph G
28 graph H
29 hierarchy
30 hypergrid
31 linear programming relaxation
32 posets
33 problem
34 programming relaxation
35 property reconstruction
36 reconstruction
37 relationship
38 relaxation
39 set
40 size
41 solution
42 spanners
43 vertex v
44 schema:name Steiner Transitive-Closure Spanners of Low-Dimensional Posets
45 schema:pagination 760-772
46 schema:productId N454e17d28d4b4557a42bb5899bfe63ce
47 N72df55633c21404384b6772685d8eec1
48 schema:publisher N6e21cb0307c34b5a9c21ad02c9121d49
49 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018924561
50 https://doi.org/10.1007/978-3-642-22006-7_64
51 schema:sdDatePublished 2022-08-04T17:18
52 schema:sdLicense https://scigraph.springernature.com/explorer/license/
53 schema:sdPublisher N902651bcf40e4632aebfe44f2990c9a8
54 schema:url https://doi.org/10.1007/978-3-642-22006-7_64
55 sgo:license sg:explorer/license/
56 sgo:sdDataset chapters
57 rdf:type schema:Chapter
58 N16d8abbe6eef485399b336b884168651 rdf:first sg:person.012727410605.86
59 rdf:rest N77fb14959b8542589a07bf37aef9c802
60 N212855ac28ff4854a6cbcd2b919e11ec schema:familyName Henzinger
61 schema:givenName Monika
62 rdf:type schema:Person
63 N2c91e06808f54c71a45cd54f0ba53c24 rdf:first N212855ac28ff4854a6cbcd2b919e11ec
64 rdf:rest N63bb82178cf24dbfa3dc407b8b909dd6
65 N2d3cd00e6ab742e282888cd60465444b schema:familyName Aceto
66 schema:givenName Luca
67 rdf:type schema:Person
68 N454e17d28d4b4557a42bb5899bfe63ce schema:name dimensions_id
69 schema:value pub.1018924561
70 rdf:type schema:PropertyValue
71 N606d56a545aa4fb693c261613ce7e93f rdf:first sg:person.07502404747.45
72 rdf:rest N16d8abbe6eef485399b336b884168651
73 N63bb82178cf24dbfa3dc407b8b909dd6 rdf:first Nbf865282b8a043aea09b8d2939a670f9
74 rdf:rest rdf:nil
75 N6e21cb0307c34b5a9c21ad02c9121d49 schema:name Springer Nature
76 rdf:type schema:Organisation
77 N72df55633c21404384b6772685d8eec1 schema:name doi
78 schema:value 10.1007/978-3-642-22006-7_64
79 rdf:type schema:PropertyValue
80 N77fb14959b8542589a07bf37aef9c802 rdf:first sg:person.015277345473.26
81 rdf:rest rdf:nil
82 N902651bcf40e4632aebfe44f2990c9a8 schema:name Springer Nature - SN SciGraph project
83 rdf:type schema:Organization
84 N9970e2476f5242e782198e78a904b536 rdf:first N2d3cd00e6ab742e282888cd60465444b
85 rdf:rest N2c91e06808f54c71a45cd54f0ba53c24
86 Na2ad2791dad44aaeaf1cec2d4a3f1d27 rdf:first sg:person.014612515147.15
87 rdf:rest N606d56a545aa4fb693c261613ce7e93f
88 Naae2c71cb9fd49a18bbf5e89deed3c85 rdf:first sg:person.012357145015.18
89 rdf:rest Na2ad2791dad44aaeaf1cec2d4a3f1d27
90 Nbf865282b8a043aea09b8d2939a670f9 schema:familyName Sgall
91 schema:givenName Jiří
92 rdf:type schema:Person
93 Nc22ce443fec94ef1b5eb919d41396e11 rdf:first sg:person.01274506210.27
94 rdf:rest Naae2c71cb9fd49a18bbf5e89deed3c85
95 Nd16f46a7c7594545803815302b7f24b8 schema:isbn 978-3-642-22005-0
96 978-3-642-22006-7
97 schema:name Automata, Languages and Programming
98 rdf:type schema:Book
99 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
100 schema:name Information and Computing Sciences
101 rdf:type schema:DefinedTerm
102 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
103 schema:name Information Systems
104 rdf:type schema:DefinedTerm
105 sg:person.012357145015.18 schema:affiliation grid-institutes:grid.116068.8
106 schema:familyName Bhattacharyya
107 schema:givenName Arnab
108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012357145015.18
109 rdf:type schema:Person
110 sg:person.012727410605.86 schema:affiliation grid-institutes:grid.481551.c
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 sg:person.01274506210.27 schema:affiliation grid-institutes:grid.29857.31
116 schema:familyName Berman
117 schema:givenName Piotr
118 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27
119 rdf:type schema:Person
120 sg:person.014612515147.15 schema:affiliation grid-institutes:grid.213917.f
121 schema:familyName Grigorescu
122 schema:givenName Elena
123 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014612515147.15
124 rdf:type schema:Person
125 sg:person.015277345473.26 schema:affiliation grid-institutes:grid.29857.31
126 schema:familyName Yaroslavtsev
127 schema:givenName Grigory
128 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015277345473.26
129 rdf:type schema:Person
130 sg:person.07502404747.45 schema:affiliation grid-institutes:grid.29857.31
131 schema:familyName Raskhodnikova
132 schema:givenName Sofya
133 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07502404747.45
134 rdf:type schema:Person
135 grid-institutes:grid.116068.8 schema:alternateName Massachusetts Institute of Technology, USA
136 schema:name Massachusetts Institute of Technology, USA
137 rdf:type schema:Organization
138 grid-institutes:grid.213917.f schema:alternateName Georgia Institute of Technology, USA
139 schema:name Georgia Institute of Technology, USA
140 rdf:type schema:Organization
141 grid-institutes:grid.29857.31 schema:alternateName Pennsylvania State University, USA
142 schema:name Pennsylvania State University, USA
143 rdf:type schema:Organization
144 grid-institutes:grid.481551.c schema:alternateName IBM Almaden Research Center, USA
145 schema:name IBM Almaden Research Center, USA
146 rdf:type schema:Organization
 




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


...