Steiner transitive-closure spanners of low-dimensional posets View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2014-02-08

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 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. In some applications, the shortcut paths added to the graph in order to obtain small diameter can use Steiner vertices, that is, vertices not in the original graph G. The resulting spanner is called a Steiner transitive-closure spanner (Steiner TC-spanner).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. In these applications, the goal is to find a sparsest Steiner k-TC-spanner of a poset G for a given k and G. The focus of this paper is the relationship between the dimension of a poset and the size of its sparsest Steiner TC-spanner. The dimension of a poset G is the smallest d such that G can be embedded into a d-dimensional directed hypergrid via an order-preserving embedding.We present a nearly tight lower bound on the size of Steiner 2-TC-spanners of d- dimensional directed hypergrids. It implies better lower bounds on the complexity of local reconstructors of monotone functions and functions with small Lipschitz constant. The lower bound is derived from an explicit dual solution to a linear programming relaxation of the Steiner 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 lower bound on the size of Steiner k-TC-spanners of d-dimensional posets. It shows that the best-known construction, due to De Santis et al., cannot be improved significantly. More... »

PAGES

255-277

References to SciGraph publications

  • 1999. Improved Testing Algorithms for Monotonicity in RANDOMIZATION, APPROXIMATION, AND COMBINATORIAL OPTIMIZATION. ALGORITHMS AND TECHNIQUES
  • 1986-03. On the dimensions of ordered sets of bounded degree in ORDER
  • 2007-10-19. Property-Preserving Data Reconstruction in ALGORITHMICA
  • 1993. On shortcutting digraphs in GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE
  • 2010. Transitive-Closure Spanners: A Survey in PROPERTY TESTING
  • 1983. Lower bounds for constant depth circuits for prefix problems in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 1987-11. Computing on a free tree via complexity-preserving mappings in ALGORITHMICA
  • 1928-12. Zum Hilbertschen Aufbau der reellen Zahlen in MATHEMATISCHE ANNALEN
  • 2011. Steiner Transitive-Closure Spanners of Low-Dimensional Posets in AUTOMATA, LANGUAGES AND PROGRAMMING
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00493-014-2833-9

    DOI

    http://dx.doi.org/10.1007/s00493-014-2833-9

    DIMENSIONS

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


    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/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Pure Mathematics", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Pennsylvania State University, University Park, Pennsylvania, USA", 
              "id": "http://www.grid.ac/institutes/grid.29857.31", 
              "name": [
                "Pennsylvania State University, University Park, Pennsylvania, 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": "DIMACS and Rutgers University, Newark, New Jersey, USA", 
              "id": "http://www.grid.ac/institutes/grid.430387.b", 
              "name": [
                "DIMACS and Rutgers University, Newark, New Jersey, 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": "Purdue University, West Lafayette, Indiana, USA", 
              "id": "http://www.grid.ac/institutes/grid.169077.e", 
              "name": [
                "Purdue University, West Lafayette, Indiana, 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, University Park, Pennsylvania, USA", 
              "id": "http://www.grid.ac/institutes/grid.29857.31", 
              "name": [
                "Pennsylvania State University, University Park, Pennsylvania, 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, San Jose, California, USA", 
              "id": "http://www.grid.ac/institutes/grid.481551.c", 
              "name": [
                "IBM Almaden Research Center, San Jose, California, 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, University Park, Pennsylvania, USA", 
              "id": "http://www.grid.ac/institutes/grid.29857.31", 
              "name": [
                "Pennsylvania State University, University Park, Pennsylvania, 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"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-3-540-48413-4_10", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049264838", 
              "https://doi.org/10.1007/978-3-540-48413-4_10"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-56402-0_48", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038985030", 
              "https://doi.org/10.1007/3-540-56402-0_48"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01459088", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027592656", 
              "https://doi.org/10.1007/bf01459088"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00453-007-9075-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009956801", 
              "https://doi.org/10.1007/s00453-007-9075-9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0036901", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051553095", 
              "https://doi.org/10.1007/bfb0036901"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-16367-8_10", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009421283", 
              "https://doi.org/10.1007/978-3-642-16367-8_10"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01840366", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047706640", 
              "https://doi.org/10.1007/bf01840366"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-22006-7_64", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018924561", 
              "https://doi.org/10.1007/978-3-642-22006-7_64"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00403406", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038468706", 
              "https://doi.org/10.1007/bf00403406"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2014-02-08", 
        "datePublishedReg": "2014-02-08", 
        "description": "Given a directed graph G=(V, E) and an integer k \u2265 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. In some applications, the shortcut paths added to the graph in order to obtain small diameter can use Steiner vertices, that is, vertices not in the original graph G. The resulting spanner is called a Steiner transitive-closure spanner (Steiner TC-spanner).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. In these applications, the goal is to find a sparsest Steiner k-TC-spanner of a poset G for a given k and G. The focus of this paper is the relationship between the dimension of a poset and the size of its sparsest Steiner TC-spanner. The dimension of a poset G is the smallest d such that G can be embedded into a d-dimensional directed hypergrid via an order-preserving embedding.We present a nearly tight lower bound on the size of Steiner 2-TC-spanners of d- dimensional directed hypergrids. It implies better lower bounds on the complexity of local reconstructors of monotone functions and functions with small Lipschitz constant. The lower bound is derived from an explicit dual solution to a linear programming relaxation of the Steiner 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 lower bound on the size of Steiner k-TC-spanners of d-dimensional posets. It shows that the best-known construction, due to De Santis et al., cannot be improved significantly.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00493-014-2833-9", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1136493", 
            "issn": [
              "0209-9683", 
              "1439-6912"
            ], 
            "name": "Combinatorica", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "3", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "34"
          }
        ], 
        "keywords": [
          "explicit dual solutions", 
          "original graph G.", 
          "linear programming relaxation", 
          "same transitive closure", 
          "order-preserving embedding", 
          "small Lipschitz", 
          "access control hierarchy", 
          "dual solutions", 
          "programming relaxation", 
          "De Santis et al", 
          "lower bounds", 
          "property reconstruction", 
          "graph G.", 
          "monotone functions", 
          "dimensional poset", 
          "posets", 
          "graph", 
          "acyclic graph", 
          "Steiner vertices", 
          "vertices", 
          "control hierarchy", 
          "transitive closure", 
          "hypergrid", 
          "Lipschitz", 
          "spanners", 
          "bounds", 
          "et al", 
          "efficient construction", 
          "reconstructor", 
          "dimensions", 
          "applications", 
          "embedding", 
          "Steiner", 
          "problem", 
          "solution", 
          "function", 
          "complexity", 
          "construction", 
          "set", 
          "G.", 
          "relaxation", 
          "path", 
          "size", 
          "hierarchy", 
          "order", 
          "small diameter", 
          "al", 
          "reconstruction", 
          "goal", 
          "diameter", 
          "shortcut paths", 
          "closure", 
          "focus", 
          "relationship", 
          "paper"
        ], 
        "name": "Steiner transitive-closure spanners of low-dimensional posets", 
        "pagination": "255-277", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1009141147"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00493-014-2833-9"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00493-014-2833-9", 
          "https://app.dimensions.ai/details/publication/pub.1009141147"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-10-01T06:39", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/article/article_622.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00493-014-2833-9"
      }
    ]
     

    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/s00493-014-2833-9'

    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/s00493-014-2833-9'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00493-014-2833-9'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00493-014-2833-9'


     

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

    192 TRIPLES      21 PREDICATES      88 URIs      71 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00493-014-2833-9 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author Nce943aa2f34c48a7a829b87300dda415
    4 schema:citation sg:pub.10.1007/3-540-56402-0_48
    5 sg:pub.10.1007/978-3-540-48413-4_10
    6 sg:pub.10.1007/978-3-642-16367-8_10
    7 sg:pub.10.1007/978-3-642-22006-7_64
    8 sg:pub.10.1007/bf00403406
    9 sg:pub.10.1007/bf01459088
    10 sg:pub.10.1007/bf01840366
    11 sg:pub.10.1007/bfb0036901
    12 sg:pub.10.1007/s00453-007-9075-9
    13 schema:datePublished 2014-02-08
    14 schema:datePublishedReg 2014-02-08
    15 schema:description 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. In some applications, the shortcut paths added to the graph in order to obtain small diameter can use Steiner vertices, that is, vertices not in the original graph G. The resulting spanner is called a Steiner transitive-closure spanner (Steiner TC-spanner).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. In these applications, the goal is to find a sparsest Steiner k-TC-spanner of a poset G for a given k and G. The focus of this paper is the relationship between the dimension of a poset and the size of its sparsest Steiner TC-spanner. The dimension of a poset G is the smallest d such that G can be embedded into a d-dimensional directed hypergrid via an order-preserving embedding.We present a nearly tight lower bound on the size of Steiner 2-TC-spanners of d- dimensional directed hypergrids. It implies better lower bounds on the complexity of local reconstructors of monotone functions and functions with small Lipschitz constant. The lower bound is derived from an explicit dual solution to a linear programming relaxation of the Steiner 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 lower bound on the size of Steiner k-TC-spanners of d-dimensional posets. It shows that the best-known construction, due to De Santis et al., cannot be improved significantly.
    16 schema:genre article
    17 schema:isAccessibleForFree false
    18 schema:isPartOf N9f304802aaee4241bda82e60688250df
    19 Ncf478990e1dd400296b9e65fa8ec79d0
    20 sg:journal.1136493
    21 schema:keywords De Santis et al
    22 G.
    23 Lipschitz
    24 Steiner
    25 Steiner vertices
    26 access control hierarchy
    27 acyclic graph
    28 al
    29 applications
    30 bounds
    31 closure
    32 complexity
    33 construction
    34 control hierarchy
    35 diameter
    36 dimensional poset
    37 dimensions
    38 dual solutions
    39 efficient construction
    40 embedding
    41 et al
    42 explicit dual solutions
    43 focus
    44 function
    45 goal
    46 graph
    47 graph G.
    48 hierarchy
    49 hypergrid
    50 linear programming relaxation
    51 lower bounds
    52 monotone functions
    53 order
    54 order-preserving embedding
    55 original graph G.
    56 paper
    57 path
    58 posets
    59 problem
    60 programming relaxation
    61 property reconstruction
    62 reconstruction
    63 reconstructor
    64 relationship
    65 relaxation
    66 same transitive closure
    67 set
    68 shortcut paths
    69 size
    70 small Lipschitz
    71 small diameter
    72 solution
    73 spanners
    74 transitive closure
    75 vertices
    76 schema:name Steiner transitive-closure spanners of low-dimensional posets
    77 schema:pagination 255-277
    78 schema:productId N9a9876aba446432380426502e317e7ea
    79 Ncc5bc4ca49e140a2ab785236778d46bd
    80 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009141147
    81 https://doi.org/10.1007/s00493-014-2833-9
    82 schema:sdDatePublished 2022-10-01T06:39
    83 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    84 schema:sdPublisher N47587df987864ec19b0a9b43c0b00e63
    85 schema:url https://doi.org/10.1007/s00493-014-2833-9
    86 sgo:license sg:explorer/license/
    87 sgo:sdDataset articles
    88 rdf:type schema:ScholarlyArticle
    89 N1cfda83e558a460995fbd18c108570cd rdf:first sg:person.07502404747.45
    90 rdf:rest N79d90a8e1dd642178279e4696240fef9
    91 N47587df987864ec19b0a9b43c0b00e63 schema:name Springer Nature - SN SciGraph project
    92 rdf:type schema:Organization
    93 N60e4dffa602f41b0ae3d750ee5a3fee3 rdf:first sg:person.012357145015.18
    94 rdf:rest Nf2d2e0c991ad4aa5be94424142441a2a
    95 N79d90a8e1dd642178279e4696240fef9 rdf:first sg:person.012727410605.86
    96 rdf:rest N8e39d8a4ac604408bbfaeee58dc987e8
    97 N8e39d8a4ac604408bbfaeee58dc987e8 rdf:first sg:person.015277345473.26
    98 rdf:rest rdf:nil
    99 N9a9876aba446432380426502e317e7ea schema:name dimensions_id
    100 schema:value pub.1009141147
    101 rdf:type schema:PropertyValue
    102 N9f304802aaee4241bda82e60688250df schema:issueNumber 3
    103 rdf:type schema:PublicationIssue
    104 Ncc5bc4ca49e140a2ab785236778d46bd schema:name doi
    105 schema:value 10.1007/s00493-014-2833-9
    106 rdf:type schema:PropertyValue
    107 Nce943aa2f34c48a7a829b87300dda415 rdf:first sg:person.01274506210.27
    108 rdf:rest N60e4dffa602f41b0ae3d750ee5a3fee3
    109 Ncf478990e1dd400296b9e65fa8ec79d0 schema:volumeNumber 34
    110 rdf:type schema:PublicationVolume
    111 Nf2d2e0c991ad4aa5be94424142441a2a rdf:first sg:person.014612515147.15
    112 rdf:rest N1cfda83e558a460995fbd18c108570cd
    113 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    114 schema:name Mathematical Sciences
    115 rdf:type schema:DefinedTerm
    116 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    117 schema:name Pure Mathematics
    118 rdf:type schema:DefinedTerm
    119 sg:journal.1136493 schema:issn 0209-9683
    120 1439-6912
    121 schema:name Combinatorica
    122 schema:publisher Springer Nature
    123 rdf:type schema:Periodical
    124 sg:person.012357145015.18 schema:affiliation grid-institutes:grid.430387.b
    125 schema:familyName Bhattacharyya
    126 schema:givenName Arnab
    127 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012357145015.18
    128 rdf:type schema:Person
    129 sg:person.012727410605.86 schema:affiliation grid-institutes:grid.481551.c
    130 schema:familyName Woodruff
    131 schema:givenName David P.
    132 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012727410605.86
    133 rdf:type schema:Person
    134 sg:person.01274506210.27 schema:affiliation grid-institutes:grid.29857.31
    135 schema:familyName Berman
    136 schema:givenName Piotr
    137 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27
    138 rdf:type schema:Person
    139 sg:person.014612515147.15 schema:affiliation grid-institutes:grid.169077.e
    140 schema:familyName Grigorescu
    141 schema:givenName Elena
    142 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014612515147.15
    143 rdf:type schema:Person
    144 sg:person.015277345473.26 schema:affiliation grid-institutes:grid.29857.31
    145 schema:familyName Yaroslavtsev
    146 schema:givenName Grigory
    147 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015277345473.26
    148 rdf:type schema:Person
    149 sg:person.07502404747.45 schema:affiliation grid-institutes:grid.29857.31
    150 schema:familyName Raskhodnikova
    151 schema:givenName Sofya
    152 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07502404747.45
    153 rdf:type schema:Person
    154 sg:pub.10.1007/3-540-56402-0_48 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038985030
    155 https://doi.org/10.1007/3-540-56402-0_48
    156 rdf:type schema:CreativeWork
    157 sg:pub.10.1007/978-3-540-48413-4_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049264838
    158 https://doi.org/10.1007/978-3-540-48413-4_10
    159 rdf:type schema:CreativeWork
    160 sg:pub.10.1007/978-3-642-16367-8_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009421283
    161 https://doi.org/10.1007/978-3-642-16367-8_10
    162 rdf:type schema:CreativeWork
    163 sg:pub.10.1007/978-3-642-22006-7_64 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018924561
    164 https://doi.org/10.1007/978-3-642-22006-7_64
    165 rdf:type schema:CreativeWork
    166 sg:pub.10.1007/bf00403406 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038468706
    167 https://doi.org/10.1007/bf00403406
    168 rdf:type schema:CreativeWork
    169 sg:pub.10.1007/bf01459088 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027592656
    170 https://doi.org/10.1007/bf01459088
    171 rdf:type schema:CreativeWork
    172 sg:pub.10.1007/bf01840366 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047706640
    173 https://doi.org/10.1007/bf01840366
    174 rdf:type schema:CreativeWork
    175 sg:pub.10.1007/bfb0036901 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051553095
    176 https://doi.org/10.1007/bfb0036901
    177 rdf:type schema:CreativeWork
    178 sg:pub.10.1007/s00453-007-9075-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009956801
    179 https://doi.org/10.1007/s00453-007-9075-9
    180 rdf:type schema:CreativeWork
    181 grid-institutes:grid.169077.e schema:alternateName Purdue University, West Lafayette, Indiana, USA
    182 schema:name Purdue University, West Lafayette, Indiana, USA
    183 rdf:type schema:Organization
    184 grid-institutes:grid.29857.31 schema:alternateName Pennsylvania State University, University Park, Pennsylvania, USA
    185 schema:name Pennsylvania State University, University Park, Pennsylvania, USA
    186 rdf:type schema:Organization
    187 grid-institutes:grid.430387.b schema:alternateName DIMACS and Rutgers University, Newark, New Jersey, USA
    188 schema:name DIMACS and Rutgers University, Newark, New Jersey, USA
    189 rdf:type schema:Organization
    190 grid-institutes:grid.481551.c schema:alternateName IBM Almaden Research Center, San Jose, California, USA
    191 schema:name IBM Almaden Research Center, San Jose, California, USA
    192 rdf:type schema:Organization
     




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


    ...