Sequence Hypergraphs: Paths, Flows, and Cuts View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2018-08-09

AUTHORS

Kateřina Böhmová , Jérémie Chalopin , Matúš Mihalák , Guido Proietti , Peter Widmayer

ABSTRACT

We introduce sequence hypergraphs by extending the concept of a directed edge (from simple directed graphs) to hypergraphs. Specifically, every hyperedge of a sequence hypergraph is defined as a sequence of vertices (not unlike a directed path). Sequence hypergraphs are motivated by problems in public transportation networks, as they conveniently represent transportation lines. We study the complexity of several fundamental algorithmic problems, arising (not only) in transportation, in the setting of sequence hypergraphs. In particular, we consider the problem of finding a shortestst-hyperpath: a minimum set of hyperedges that “connects” (allows to travel to) t from s; finding a minimumst-hypercut: a minimum set of hyperedges whose removal “disconnects” t from s; or finding a maximumst-hyperflow: a maximum number of hyperedge-disjoint st-hyperpaths. We show that many of these problems are APX-hard, even in acyclic sequence hypergraphs or with hyperedges of constant length. However, if all the hyperedges are of length at most 2, we show that these problems become polynomially solvable. We also study the special setting in which for every hyperedge there also is a hyperedge with the same sequence, but in reverse order. Finally, we briefly discuss other algorithmic problems such as finding a minimum spanning tree, or connected components. More... »

PAGES

191-215

References to SciGraph publications

  • 2001-10-16. Directed Hypergraphs: Problems, Algorithmic Results, and a Novel Decremental Approach in THEORETICAL COMPUTER SCIENCE
  • 2016. Computing and Listing st-Paths in Public Transportation Networks in COMPUTER SCIENCE – THEORY AND APPLICATIONS
  • 1984-03. Intersecting sperner families and their convex hulls in COMBINATORICA
  • 1997. Graph drawing and manipulation with LINK in GRAPH DRAWING
  • 2010. The Parameterized Complexity of Some Minimum Label Problems in GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE
  • 2013. Shortest Paths with Bundles and Non-additive Weights Is Hard in ALGORITHMS AND COMPLEXITY
  • 2007-11. Approximation algorithms and hardness results for labeled connectivity problems in JOURNAL OF COMBINATORIAL OPTIMIZATION
  • 2011-02. Approximation and hardness results for label cut and related problems in JOURNAL OF COMBINATORIAL OPTIMIZATION
  • Book

    TITLE

    Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications

    ISBN

    978-3-319-12567-1
    978-3-319-12568-8

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-319-98355-4_12

    DOI

    http://dx.doi.org/10.1007/978-3-319-98355-4_12

    DIMENSIONS

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


    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/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "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"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Swiss Federal Institute of Technology in Zurich", 
              "id": "https://www.grid.ac/institutes/grid.5801.c", 
              "name": [
                "Department of Computer Science, ETH Zurich, Zurich, Switzerland"
              ], 
              "type": "Organization"
            }, 
            "familyName": "B\u00f6hmov\u00e1", 
            "givenName": "Kate\u0159ina", 
            "id": "sg:person.07647062041.63", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07647062041.63"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "name": [
                "Aix-Marseille Universit\u00e9, CNRS, Universit\u00e9 de Toulon, LIS, Marseille, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Chalopin", 
            "givenName": "J\u00e9r\u00e9mie", 
            "id": "sg:person.015512567437.12", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015512567437.12"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Maastricht University", 
              "id": "https://www.grid.ac/institutes/grid.5012.6", 
              "name": [
                "Department of Data Science and Knowledge Engineering, Maastricht University, Maastricht, The Netherlands"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Mihal\u00e1k", 
            "givenName": "Mat\u00fa\u0161", 
            "id": "sg:person.012551340105.05", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012551340105.05"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Istituto di Analisi dei Sistemi ed Informatica Antonio Ruberti", 
              "id": "https://www.grid.ac/institutes/grid.419461.f", 
              "name": [
                "DISIM, Universit\u00e0 degli Studi dell\u2019Aquila, L\u2019Aquila, Italy", 
                "IASI, CNR, Rome, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Proietti", 
            "givenName": "Guido", 
            "id": "sg:person.015510625760.85", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015510625760.85"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Swiss Federal Institute of Technology in Zurich", 
              "id": "https://www.grid.ac/institutes/grid.5801.c", 
              "name": [
                "Department of Computer Science, ETH Zurich, Zurich, Switzerland"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Widmayer", 
            "givenName": "Peter", 
            "id": "sg:person.0757144477.93", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0757144477.93"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bf02579153", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003215661", 
              "https://doi.org/10.1007/bf02579153"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02579153", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003215661", 
              "https://doi.org/10.1007/bf02579153"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-63938-1_87", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006667756", 
              "https://doi.org/10.1007/3-540-63938-1_87"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10878-009-9222-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008079256", 
              "https://doi.org/10.1007/s10878-009-9222-0"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10878-007-9044-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009071033", 
              "https://doi.org/10.1007/s10878-007-9044-x"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-11409-0_8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011601013", 
              "https://doi.org/10.1007/978-3-642-11409-0_8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-11409-0_8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011601013", 
              "https://doi.org/10.1007/978-3-642-11409-0_8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-34171-2_8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015105585", 
              "https://doi.org/10.1007/978-3-319-34171-2_8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-38233-8_22", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016716670", 
              "https://doi.org/10.1007/978-3-642-38233-8_22"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-45446-2_20", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023016512", 
              "https://doi.org/10.1007/3-540-45446-2_20"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-45446-2_20", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023016512", 
              "https://doi.org/10.1007/3-540-45446-2_20"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1273496.1273615", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030757855"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0166-218x(93)90045-p", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038664859"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0020-0190(98)00034-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039574173"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.jcss.2007.06.019", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043857779"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/2591796.2591884", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051836949"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tcomm.2003.809779", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061555245"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tit.1956.1056816", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061645520"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1142/s0129626407002958", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062907353"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2018-08-09", 
        "datePublishedReg": "2018-08-09", 
        "description": "We introduce sequence hypergraphs by extending the concept of a directed edge (from simple directed graphs) to hypergraphs. Specifically, every hyperedge of a sequence hypergraph is defined as a sequence of vertices (not unlike a directed path). Sequence hypergraphs are motivated by problems in public transportation networks, as they conveniently represent transportation lines. We study the complexity of several fundamental algorithmic problems, arising (not only) in transportation, in the setting of sequence hypergraphs. In particular, we consider the problem of finding a shortestst-hyperpath: a minimum set of hyperedges that \u201cconnects\u201d (allows to travel to) t from s; finding a minimumst-hypercut: a minimum set of hyperedges whose removal \u201cdisconnects\u201d t from s; or finding a maximumst-hyperflow: a maximum number of hyperedge-disjoint st-hyperpaths. We show that many of these problems are APX-hard, even in acyclic sequence hypergraphs or with hyperedges of constant length. However, if all the hyperedges are of length at most 2, we show that these problems become polynomially solvable. We also study the special setting in which for every hyperedge there also is a hyperedge with the same sequence, but in reverse order. Finally, we briefly discuss other algorithmic problems such as finding a minimum spanning tree, or connected components.", 
        "editor": [
          {
            "familyName": "Bayro-Corrochano", 
            "givenName": "Eduardo", 
            "type": "Person"
          }, 
          {
            "familyName": "Hancock", 
            "givenName": "Edwin", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-319-98355-4_12", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-319-12567-1", 
            "978-3-319-12568-8"
          ], 
          "name": "Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications", 
          "type": "Book"
        }, 
        "name": "Sequence Hypergraphs: Paths, Flows, and Cuts", 
        "pagination": "191-215", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-319-98355-4_12"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "370d8a3befb8a219ea387efcc22378c50ac17963a48570182af17e6b091175fa"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1106070115"
            ]
          }
        ], 
        "publisher": {
          "location": "Cham", 
          "name": "Springer International Publishing", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-319-98355-4_12", 
          "https://app.dimensions.ai/details/publication/pub.1106070115"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T05:00", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000325_0000000325/records_100794_00000000.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F978-3-319-98355-4_12"
      }
    ]
     

    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-319-98355-4_12'

    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-319-98355-4_12'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-98355-4_12'

    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-319-98355-4_12'


     

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

    163 TRIPLES      23 PREDICATES      42 URIs      19 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-319-98355-4_12 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N6c72a98443ad441584a3bf3a02b10049
    4 schema:citation sg:pub.10.1007/3-540-45446-2_20
    5 sg:pub.10.1007/3-540-63938-1_87
    6 sg:pub.10.1007/978-3-319-34171-2_8
    7 sg:pub.10.1007/978-3-642-11409-0_8
    8 sg:pub.10.1007/978-3-642-38233-8_22
    9 sg:pub.10.1007/bf02579153
    10 sg:pub.10.1007/s10878-007-9044-x
    11 sg:pub.10.1007/s10878-009-9222-0
    12 https://doi.org/10.1016/0166-218x(93)90045-p
    13 https://doi.org/10.1016/j.jcss.2007.06.019
    14 https://doi.org/10.1016/s0020-0190(98)00034-9
    15 https://doi.org/10.1109/tcomm.2003.809779
    16 https://doi.org/10.1109/tit.1956.1056816
    17 https://doi.org/10.1142/s0129626407002958
    18 https://doi.org/10.1145/1273496.1273615
    19 https://doi.org/10.1145/2591796.2591884
    20 schema:datePublished 2018-08-09
    21 schema:datePublishedReg 2018-08-09
    22 schema:description We introduce sequence hypergraphs by extending the concept of a directed edge (from simple directed graphs) to hypergraphs. Specifically, every hyperedge of a sequence hypergraph is defined as a sequence of vertices (not unlike a directed path). Sequence hypergraphs are motivated by problems in public transportation networks, as they conveniently represent transportation lines. We study the complexity of several fundamental algorithmic problems, arising (not only) in transportation, in the setting of sequence hypergraphs. In particular, we consider the problem of finding a shortestst-hyperpath: a minimum set of hyperedges that “connects” (allows to travel to) t from s; finding a minimumst-hypercut: a minimum set of hyperedges whose removal “disconnects” t from s; or finding a maximumst-hyperflow: a maximum number of hyperedge-disjoint st-hyperpaths. We show that many of these problems are APX-hard, even in acyclic sequence hypergraphs or with hyperedges of constant length. However, if all the hyperedges are of length at most 2, we show that these problems become polynomially solvable. We also study the special setting in which for every hyperedge there also is a hyperedge with the same sequence, but in reverse order. Finally, we briefly discuss other algorithmic problems such as finding a minimum spanning tree, or connected components.
    23 schema:editor N6f163adfe48240e79e53f2c689aa9708
    24 schema:genre chapter
    25 schema:inLanguage en
    26 schema:isAccessibleForFree false
    27 schema:isPartOf Nf9e43edc9fc041ab909385fd7925c0dc
    28 schema:name Sequence Hypergraphs: Paths, Flows, and Cuts
    29 schema:pagination 191-215
    30 schema:productId N1f1bf7b4539e4e3e91fdb313a50ffb28
    31 N6a30a1d6d2d34fb689516fa041932de4
    32 Ncc305168115f454c8f32cfa8a1a6b9e2
    33 schema:publisher Ndb1cd7e9222f4ca7bc4e455df59a6322
    34 schema:sameAs https://app.dimensions.ai/details/publication/pub.1106070115
    35 https://doi.org/10.1007/978-3-319-98355-4_12
    36 schema:sdDatePublished 2019-04-16T05:00
    37 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    38 schema:sdPublisher Nf14303738435456aa6851067044cc710
    39 schema:url https://link.springer.com/10.1007%2F978-3-319-98355-4_12
    40 sgo:license sg:explorer/license/
    41 sgo:sdDataset chapters
    42 rdf:type schema:Chapter
    43 N1f1bf7b4539e4e3e91fdb313a50ffb28 schema:name doi
    44 schema:value 10.1007/978-3-319-98355-4_12
    45 rdf:type schema:PropertyValue
    46 N599d5f2eed2a4e429d534a089ed7847e schema:familyName Bayro-Corrochano
    47 schema:givenName Eduardo
    48 rdf:type schema:Person
    49 N5eadf5909a414711a83d1090fe36b494 rdf:first Nfee2eaa076b04a66b4dcb3521ac1652d
    50 rdf:rest rdf:nil
    51 N6a30a1d6d2d34fb689516fa041932de4 schema:name dimensions_id
    52 schema:value pub.1106070115
    53 rdf:type schema:PropertyValue
    54 N6c72a98443ad441584a3bf3a02b10049 rdf:first sg:person.07647062041.63
    55 rdf:rest Ne862a48cfb3d4878bf3df602fac40e48
    56 N6f163adfe48240e79e53f2c689aa9708 rdf:first N599d5f2eed2a4e429d534a089ed7847e
    57 rdf:rest N5eadf5909a414711a83d1090fe36b494
    58 Nbd32a6e176344f38a64236a43171c905 rdf:first sg:person.012551340105.05
    59 rdf:rest Nd324aa9e3b41459fbef74cb286d8f981
    60 Ncc305168115f454c8f32cfa8a1a6b9e2 schema:name readcube_id
    61 schema:value 370d8a3befb8a219ea387efcc22378c50ac17963a48570182af17e6b091175fa
    62 rdf:type schema:PropertyValue
    63 Nd324aa9e3b41459fbef74cb286d8f981 rdf:first sg:person.015510625760.85
    64 rdf:rest Nf8bf9ab7fcca46ba9834cc353c445a42
    65 Ndb1cd7e9222f4ca7bc4e455df59a6322 schema:location Cham
    66 schema:name Springer International Publishing
    67 rdf:type schema:Organisation
    68 Ne862a48cfb3d4878bf3df602fac40e48 rdf:first sg:person.015512567437.12
    69 rdf:rest Nbd32a6e176344f38a64236a43171c905
    70 Nf14303738435456aa6851067044cc710 schema:name Springer Nature - SN SciGraph project
    71 rdf:type schema:Organization
    72 Nf6274818b43b49a1a55b2c851ea0eb14 schema:name Aix-Marseille Université, CNRS, Université de Toulon, LIS, Marseille, France
    73 rdf:type schema:Organization
    74 Nf8bf9ab7fcca46ba9834cc353c445a42 rdf:first sg:person.0757144477.93
    75 rdf:rest rdf:nil
    76 Nf9e43edc9fc041ab909385fd7925c0dc schema:isbn 978-3-319-12567-1
    77 978-3-319-12568-8
    78 schema:name Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications
    79 rdf:type schema:Book
    80 Nfee2eaa076b04a66b4dcb3521ac1652d schema:familyName Hancock
    81 schema:givenName Edwin
    82 rdf:type schema:Person
    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.012551340105.05 schema:affiliation https://www.grid.ac/institutes/grid.5012.6
    90 schema:familyName Mihalák
    91 schema:givenName Matúš
    92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012551340105.05
    93 rdf:type schema:Person
    94 sg:person.015510625760.85 schema:affiliation https://www.grid.ac/institutes/grid.419461.f
    95 schema:familyName Proietti
    96 schema:givenName Guido
    97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015510625760.85
    98 rdf:type schema:Person
    99 sg:person.015512567437.12 schema:affiliation Nf6274818b43b49a1a55b2c851ea0eb14
    100 schema:familyName Chalopin
    101 schema:givenName Jérémie
    102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015512567437.12
    103 rdf:type schema:Person
    104 sg:person.0757144477.93 schema:affiliation https://www.grid.ac/institutes/grid.5801.c
    105 schema:familyName Widmayer
    106 schema:givenName Peter
    107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0757144477.93
    108 rdf:type schema:Person
    109 sg:person.07647062041.63 schema:affiliation https://www.grid.ac/institutes/grid.5801.c
    110 schema:familyName Böhmová
    111 schema:givenName Kateřina
    112 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07647062041.63
    113 rdf:type schema:Person
    114 sg:pub.10.1007/3-540-45446-2_20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023016512
    115 https://doi.org/10.1007/3-540-45446-2_20
    116 rdf:type schema:CreativeWork
    117 sg:pub.10.1007/3-540-63938-1_87 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006667756
    118 https://doi.org/10.1007/3-540-63938-1_87
    119 rdf:type schema:CreativeWork
    120 sg:pub.10.1007/978-3-319-34171-2_8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015105585
    121 https://doi.org/10.1007/978-3-319-34171-2_8
    122 rdf:type schema:CreativeWork
    123 sg:pub.10.1007/978-3-642-11409-0_8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011601013
    124 https://doi.org/10.1007/978-3-642-11409-0_8
    125 rdf:type schema:CreativeWork
    126 sg:pub.10.1007/978-3-642-38233-8_22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016716670
    127 https://doi.org/10.1007/978-3-642-38233-8_22
    128 rdf:type schema:CreativeWork
    129 sg:pub.10.1007/bf02579153 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003215661
    130 https://doi.org/10.1007/bf02579153
    131 rdf:type schema:CreativeWork
    132 sg:pub.10.1007/s10878-007-9044-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1009071033
    133 https://doi.org/10.1007/s10878-007-9044-x
    134 rdf:type schema:CreativeWork
    135 sg:pub.10.1007/s10878-009-9222-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008079256
    136 https://doi.org/10.1007/s10878-009-9222-0
    137 rdf:type schema:CreativeWork
    138 https://doi.org/10.1016/0166-218x(93)90045-p schema:sameAs https://app.dimensions.ai/details/publication/pub.1038664859
    139 rdf:type schema:CreativeWork
    140 https://doi.org/10.1016/j.jcss.2007.06.019 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043857779
    141 rdf:type schema:CreativeWork
    142 https://doi.org/10.1016/s0020-0190(98)00034-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039574173
    143 rdf:type schema:CreativeWork
    144 https://doi.org/10.1109/tcomm.2003.809779 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061555245
    145 rdf:type schema:CreativeWork
    146 https://doi.org/10.1109/tit.1956.1056816 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061645520
    147 rdf:type schema:CreativeWork
    148 https://doi.org/10.1142/s0129626407002958 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062907353
    149 rdf:type schema:CreativeWork
    150 https://doi.org/10.1145/1273496.1273615 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030757855
    151 rdf:type schema:CreativeWork
    152 https://doi.org/10.1145/2591796.2591884 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051836949
    153 rdf:type schema:CreativeWork
    154 https://www.grid.ac/institutes/grid.419461.f schema:alternateName Istituto di Analisi dei Sistemi ed Informatica Antonio Ruberti
    155 schema:name DISIM, Università degli Studi dell’Aquila, L’Aquila, Italy
    156 IASI, CNR, Rome, Italy
    157 rdf:type schema:Organization
    158 https://www.grid.ac/institutes/grid.5012.6 schema:alternateName Maastricht University
    159 schema:name Department of Data Science and Knowledge Engineering, Maastricht University, Maastricht, The Netherlands
    160 rdf:type schema:Organization
    161 https://www.grid.ac/institutes/grid.5801.c schema:alternateName Swiss Federal Institute of Technology in Zurich
    162 schema:name Department of Computer Science, ETH Zurich, Zurich, Switzerland
    163 rdf:type schema:Organization
     




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


    ...